Stworzyłem funkcję, która przechodzi przez listę2d pól granicznych i znajduje te, które zawierają dany punkt 2d. Niestety jest to dość powolne, więc szukałem sposobu na zoptymalizowanie go za pomocą jakiejś struktury drzewa.
Widziałem wiele pytań na podstawie znalezieniapunkty w polach, ale żadne dla znalezienia skrzynek z punktu. Wiem, jak zrobić skrzyżowanie, więc to tylko struktura drzewa, którą jestem zainteresowany. Myślałem, że quadtree może pasować, ale nie jestem pewny, jak poradziłby sobie ze skriningiem pudełek powielanych w różnych węzłach.
Czy byłoby lepiej użyć jakiegoś binarnego drzewa wyszukiwania, w którym rekurencyjnie dzieliłem osie x i y (jak przeciętne cięcie)?
Odpowiedzi:
0 dla odpowiedzi № 1Proponuję użyć drzewa segmentów.
Obejrzyj te slajdy:
http://algo.kaust.edu.sa/Documents/cs372l07.pdf
szczególnie poszukujesz rozwiązania problemu przeszywających zapytań o wyższych wymiarach (slajd 25)