Algoritmo per l'hit test in rettangoli non sovrapposti

Question

Ho una raccolta di rettangoli non sovrapposti che coprono un rettangolo che li racchiude.Qual è il modo migliore per trovare il rettangolo contenente con un clic del mouse?

La risposta ovvia è avere un array di rettangoli e cercarli in sequenza, effettuando la ricerca O(n).Esiste un modo per ordinarli per posizione in modo che l'algoritmo sia inferiore a O(n), ad esempio O(log n) o O(sqrt(n))?

Answer 1

Puoi organizzare i tuoi rettangoli in un quad o kd-tree.Questo ti dà O(log n).Questo è il metodo tradizionale.

Un'altra struttura dati interessante per questo problema sono gli R-tree.Questi possono essere molto efficienti se devi gestire molti rettangoli.

http://en.wikipedia.org/wiki/R-tree

E poi c'è il metodo O(1) per generare semplicemente una bitmap della stessa dimensione dello schermo, riempirla con un segnaposto per "nessun rettangolo" e disegnare gli indici del rettangolo colpito in quella bitmap.Una ricerca diventa semplice come:

  int id = bitmap_getpixel (mouse.x, mouse.y)
  if (id != -1)
  {
    hit_rectange (id);
  }
  else
  {
    no_hit();
  }

Ovviamente questo metodo funziona bene solo se i tuoi rettangoli non cambiano così spesso e se puoi risparmiare memoria per la bitmap.

Answer 2

Crea un albero di intervalli.Interrogare l'albero degli intervalli.Consultare "Algoritmi" della stampa del MIT.

Un albero a intervalli viene implementato al meglio come albero rosso-nero.

Tieni presente che è consigliabile ordinare i tuoi rettangoli solo se intendi fare clic su di essi più di quanto non cambi la loro posizione, di solito.

Dovrai tenere presente che hai costruito i tuoi indici per i diversi assi separatamente.Ad esempio, devi vedere se sovrapponi un intervallo su X e su Y.Un'ottimizzazione ovvia consiste nel verificare solo la sovrapposizione su uno degli intervalli X, quindi verificare immediatamente la sovrapposizione su Y.

Inoltre, la maggior parte degli alberi di intervalli azionari o "di libri di classe" controllano solo un singolo intervallo e restituiscono solo un singolo intervallo (ma hai detto "non sovrapposto", vero?)

Answer 3

Infilateli in a quadtree.

Answer 4

Usare un BSP albero per memorizzare i rettangoli.