Algoritmo di ricerca con suggerimenti di coordinate (x, y)?

Quello che stai cercando si chiama indice spaziale e il problema che stai cercando di risolvere è rilevamento delle collisioni .

Più specificamente userei una quadtree struttura dati, che suddivide il tuo spazio in quattro sottospazi ogni volta che discendi di un livello nell'albero. Questo è in 2D, se stai cercando di risolvere il problema in 3D la struttura appropriata sarebbe un ottavo.

Probabilmente dovrei deviare dal tradizionale quadruplo e suddividere la tua area a livello di pixel e cancellarne i nodi, così puoi ottenere il nodo di rilascio corrispondente per (x, y) più velocemente. L'algoritmo sarebbe approssimativamente:

1. Durante l'inizializzazione, crea l'albero e l'hash.
2. Quando inserisci un nuovo oggetto nella tua collezione, calcoli l'area di successo e la memorizzi nel nodo che rappresenta il quadrante più piccolo possibile che contiene ancora l'intera hit box .
3. Se si riceve un clic su (x, y), si cerca la foglia per x, y usando l'hash. Una volta che hai la foglia, tutto ciò che devi fare è passare alla radice e confrontare la hitbox di ogni oggetto che incontri incontrando la tua (x, y)

Una tecnica alternativa che potresti prendere in considerazione (dipende dalle tue esigenze) consiste nell'utilizzare una bitmap fuori dallo schermo per memorizzare un riferimento agli elementi di testo. L'approccio di base consiste nel disegnare il rettangolo di delimitazione sulla bitmap fuori schermo con un colore unico per ciascun elemento. La ricerca è costante, basta indicizzare la bitmap con la coordinata (x, y) di interesse (ad esempio, la posizione del mouse).

Lo svantaggio di questa tecnica sono i requisiti di memoria. La bitmap deve essere grande quanto l'area di visualizzazione sullo schermo.

Se non parli di molte migliaia di elementi, provalo prima senza algoritmi speciali. Un semplice hit test per un rettangolo è molto economico , per quanto riguarda il processore. Dubito seriamente che vedresti un qualsiasi miglioramento percettibile su schemi più efficienti.

Fondamentalmente, sebbene in teoria grandioso, questo è un posto dove non c'è bisogno di ottimizzare prematuramente.

Inoltre, assicurati di andare all'indietro (dall'alto verso il basso), in modo da colpire l'elemento in alto se due sono sovrapposti.

Come menzionato da sebastiangeiger, gli indici spaziali aiutano. Ho trovato quad alberi per essere semplice da implementare. Un'altra alternativa che potrebbe anche essere più semplice è semplicemente dividere il tuo spazio in una griglia e inserire ciascun rettangolo nella serie di spazi con cui si interseca (questo è in realtà simile a ciò che fa ogni nodo di un albero quad, dato che ogni nodo è una griglia 2x2).

In definitiva, trova l'approccio più semplice che soddisfi i requisiti delle tue prestazioni.