Znajdowanie punktów trójkątów

16

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 = 1N k = 1 T K . W jaki sposób najlepiej ustalić, w którym trójkącie leży każdy z punktów?{Tk}k=1N{pi}i=1Mk=1NTK

Na przykład na poniższym obrazku mamy , p 2T 4 , , więc chciałbym, aby funkcja zwracała listę .p1T2p2T4p3T2ff(p1,p2,p3)=[2,4,2]

wprowadź opis zdjęcia tutaj

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 ) .pipiO(NM)

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,piO(aMlosol(N.))za

  • 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!

Nick Alger
źródło

Odpowiedzi:

16

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(logN)O(MlogN)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.

Victor Liu
źródło
Victor - czy znasz jakiś kod typu open source, który sugeruje podejście przeskakujące do krawędzi? Wygląda na to, że to może być bardzo dobre rozwiązanie dla mojej sprawy. (model śledzenia cząstek napędzany przez bieżące pola w siatce traingualr)
Chris Barker
Mam do tego kod i mogę ci go wysłać; jest w C / C ++. Nie miałem jeszcze czasu, aby go wyczyścić i opublikować na Github. Musiałem to napisać co najmniej dwa razy w życiu, raz ze strukturą danych o wartości połowy, ponownie z kwadrantem, ale można go łatwo użyć, gdy nie są one dostępne i trzeba samodzielnie zbudować strukturę topologiczną. Poszukaj na mojej stronie profilu mojej witryny, na której można znaleźć dane kontaktowe. Możemy to omówić dalej w trybie offline.
Victor Liu
Jestem prawie gotowy, aby zaimplementować to w Matlabie, używając porządkowania krzywej Hilberta i losowego przejścia po trójkącie. To kod badawczy: niezoptymalizowany, nieudokumentowany itp., Ale wciąż dość szybki - mogę ci dać kod, jeśli jesteś zainteresowany.
Nick Alger
2
About: „” „hopping edge powinien być O (logN)” „” „Nie widzę tego. Na przykład w przypadku patologicznym dużego długiego paska trójkąta (jak wąski kanał tylko na szerokości trójkąta), w najgorszym przypadku trzeba przeskakiwać od jednego trójkąta do drugiego aż do końca. W przeciętnym przypadku w połowie drogi. Więc jeśli podwoisz liczbę trójkątów, będzie to O (N) W bardziej normalnym przypadku kwadratowego układu trójkątów, oczekiwałbym O (sqrt (N)). A może coś mi brakuje? -Chris
Chris Barker,
@Chris - Witamy w scicomp! W ramach prac domowych Scicompa zmigrowałem twoje odpowiedzi i późniejszą rozmowę jako komentarze do odpowiedzi Victora. Czekamy na Twój udział w witrynie.
Aron Ahmadia
8

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.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.

nnlognO(N.M.)

Erik P.
źródło
Hmm, masz rację. Z drugiej strony, jeśli triangulacją byłby Delaunay, myślę, że najbliższy sąsiad działałby. Jest to zbyt restrykcyjne w stosunku do tego, co próbuję zrobić, ale w przypadku Delaunaya rozważ podwójny schemat Voronoi - komórki Voronoi to zbiór punktów najbliższych węzłu, a wszystkie krawędzie trójkątów delaunay spotykają się z krawędziami Voronoi komórki pod kątem prostym, więc dowolny punkt musi znajdować się w trójkącie połączonym z najbliższym węzłem. Zastanawiam się, czy tak działa funkcja pointLocation Matlaba pod maską ..?
Nick Alger
1

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

Ronaldo Carpio
źródło