Znajdowanie punktów trójkątów

Załóżmy, że mają 2D siatka składa się z zachodzących na siebie trójkąty i zbiór punktów { s I } M i = 1 ⊂ ∪ N k = 1 T K . W jaki sposób najlepiej ustalić, w którym trójkącie leży każdy z punktów?$\{T_k\}_{k=1}^N$$\{p_i\}_{i=1}^M \subset \cup_{k=1}^N T_K$

Na przykład na poniższym obrazku mamy , p 2 ∈ T 4 , , więc chciałbym, aby funkcja zwracała listę .$p_1 \in T_2$$p_2 \in T_4$$p_3 \in T_2$$f$$f(p_1,p_2,p_3)=[2,4,2]$

Matlab ma funkcję lokalizacji punktowej, która robi to, co chcę dla siatek Delaunay, ale zawodzi w przypadku siatek ogólnych.

Moją pierwszą (głupią) myślą jest, aby dla wszystkich węzłów przejść przez wszystkie trójkąty, aby dowiedzieć się, w którym trójkącie znajduje się p i . Jest to jednak wyjątkowo nieefektywne - być może trzeba będzie zapętlić każdy trójkąt dla każdego punktu, więc może zająć pracę O ( N ⋅ M ) .$p_i$$p_i$$O(N \cdot M)$

Moją kolejną myślą jest, aby dla wszystkich punktów znaleźć najbliższy węzeł siatki poprzez wyszukiwanie najbliższego sąsiada, a następnie przejrzeć trójkąty dołączone do tego najbliższego węzła. W tym przypadku praca będzie wynosić O ( a ⋅ M ⋅ l o g ( N ) ) , gdzie a jest maksymalną liczbą trójkątów przymocowanych do dowolnego węzła w siatce. Z tym podejściem wiąże się kilka problemów, które można rozwiązać, ale irytujące,$p_i$$O(a\cdot M\cdot log(N))$$a$

• Wymaga wydajnego wyszukiwania najbliższego sąsiada (lub znalezienia biblioteki, która go posiada), co może być niełatwym zadaniem.
• Wymaga to przechowywania listy trójkątów dołączonych do każdego węzła, dla których mój kod nie jest obecnie skonfigurowany - w tej chwili jest tylko lista współrzędnych węzła i lista elementów.

W sumie wydaje się to nieeleganckie i myślę, że powinien istnieć lepszy sposób. To musi być problem, który często się pojawia, więc zastanawiałem się, czy ktokolwiek mógłby zalecić najlepszy sposób znalezienia trójkątów, w których znajdują się węzły, zarówno teoretycznie, jak i pod względem dostępnych bibliotek.

Dzięki!

Powinna działać zwykła losowa metoda przeskoku krawędzi. Zasadniczo zacznij od dowolnego trójkąta siatki, a następnie określ, która krawędź punktu docelowego leży po przeciwnej stronie. To znaczy określ, która z krawędzi, gdy zostanie rozciągnięta do linii, oddziel punkt od wnętrza trójkąta. Gdy są dwie możliwości, wybierz jedną losowo i rozważ trójkąt przylegający do tej wspólnej krawędzi i powtórz. Randomizacja powinna sprawić, że metoda ta będzie zbieżna z prawdopodobieństwem 1 dla triangulacji Delaunaya i nie mogę wymyślić powodu, dla którego nie zadziałałaby dla dowolnych triangulacji.

$O(\log N)$$O(M \log N)$$M$

Edycja2 : Znalazłem ten plik PDF opisujący taki „chodzący” schemat, który gwarantuje zakończenie, i przegląda bardziej naiwne podejścia.

Inną alternatywą dla korzystania z czworokątów jest stosowanie hierarchii triangulacji. Zobacz Olivier Devillers. Poprawiona przyrostowa randomizowana triangulacja Delaunaya. W Proc. 14 Annu. Symbole ACM. Comput. Geom., Strony 106-115, 1998. Działa najlepiej w przypadku triangulacji Delaunaya, ale może również działać w przypadku innych niż Delaunay.

Zasadniczo wszystko, co zrobisz, aby przyspieszyć lokalizację punktu, będzie wymagało zbudowania pomocniczej struktury danych. W przypadku czworokątów lub innego podziału przestrzennego musisz zbudować drzewo podziału. W przypadku przeskoku krawędzi należy zbudować trójkąt przylegający do struktury topologicznej. Hierarchia triangulacji wymaga także zbudowania drzewa grubszych triangulacji.

Nie jestem przekonany, czy twoje rozwiązanie jest poprawne. Rozważ sytuację, w której masz te węzły:

• Odp .: (-3, 1)
• B: (0, 2)
• C: (3, 1)
• D: (0, -5)

Istnieją trójkąty ABC i ACD. Teraz B jest najbliższym punktem początkowym, ale początek znajduje się w trójkącie ACD, który nie zawiera B.

$O(N \cdot M)$

Rozważałbym opcję zbudowania kwadratu zawierającego same trójkąty. Tzn. Masz drzewo czwartorzędowe, które przechowuje w każdym węźle (co odpowiada obwiedni):

• Współrzędne, na których pole jest dzielone, lub, alternatywnie, pola ograniczające czterech poddrzewa;
• Wskaźniki do poddrzewa;
• Zbiór trójkątów, które całkowicie mieszczą się w obwiedni tego prostokąta, ale nie całkowicie w żadnym z czterech poddrzewa. Innymi słowy, trójkąty, które przecinają się z dowolnym z dwóch dzielących się odcinków linii kwadratu.

$\sqrt{n}$$n$$\log n$$O(N\cdot M)$

CGAL obsługuje triangulacje i lokalizację punktu (i wiele więcej). W szczególności moduł triangulacji 2D może robić, co chcesz.