Algorytm Point in Wielobok dla wielu wielokątów

Mam mapę Google z kilkoma wielobokami.

Oto problem, który mnie interesuje: Biorąc pod uwagę punkt, jaki jest najlepszy sposób na określenie wszystkich wielokątów, w których ten punkt się znajduje?

Oczywistym sposobem jest iteracyjne uruchomienie algorytmu „punkt w wielokącie” dla każdego wielokąta, ale zastanawiałem się, czy istnieje skuteczny algorytm odpowiadający na takie zapytania, zwłaszcza jeśli masz tysiące wielokątów.

Podobnie jak w przypadku prawie wszystkich takich pytań, optymalne podejście zależy od „przypadków użycia” i sposobu reprezentacji funkcji. Przypadki użycia są zazwyczaj rozróżniane przez (a) czy w każdej warstwie jest wiele lub kilka obiektów i (b) czy jedna (lub obie) warstwy pozwalają na wstępne obliczenie niektórych struktur danych; to znaczy, czy jedno lub oba są wystarczająco statyczne i niezmienne, aby inwestycja w obliczenia wstępne była opłacalna.

W niniejszym przypadku daje to następujące scenariusze. Zazwyczaj punkty są dynamiczne: to znaczy, że nie są one dawane wcześniej. (Jeśli są dostępne z góry lub w bardzo dużych grupach, dostępne będą pewne optymalizacje oparte na ich sortowaniu.) Niech Q będzie liczbą punktów zapytania, a P liczbą wierzchołków wielokąta .

Dane wektora wielokąta

(1) Kilka punktów, kilka wierzchołków wielokąta w całości . Użyj procedury brutalnej siły, takiej jak klasyczny algorytm dźgania linii . Dla każdej przyzwoitej metody koszt wynosi O (P * Q), ponieważ kosztuje O (1) czas na porównanie punktu z krawędzią wielokąta i należy dokonać wszystkich takich porównań.

(2) Prawdopodobnie wiele wierzchołków wielokątów, ale są one dynamiczne: za każdym razem, gdy w zapytaniu jest używany punkt, wielokąty mogą się zmienić. Ponownie użyj algorytmu brutalnej siły. Koszt nadal wynosi O (P * Q), który będzie duży, ponieważ P będzie duży, ale nic na to nie poradzę. Jeśli zmiany są niewielkie lub kontrolowane ( np . Wielokąty nieznacznie zmieniają kształt lub po prostu poruszają się powoli), być może będziesz mógł użyć wersji następnego rozwiązania i znaleźć skuteczny sposób na aktualizację struktur danych wraz ze zmianą wielokątów. To prawdopodobnie byłaby kwestia oryginalnych badań.

(3) Wiele wierzchołków wielokątów i wielokątów statycznych (to znaczy warstwa wielokąta rzadko się zmienia). Oblicz wstępnie strukturę danych w celu obsługi wyszukiwania (która może być oparta na przemiataniu linii lub algorytmie quadtree ). Koszt wstępnego obliczenia dla tych algorytmów wynosi O (P * log (P)), ale koszt zapytań staje się O (Q * log (P)), więc całkowity koszt to O ((P + Q) * log ( P)).

Niektóre ulepszenia są dostępne w szczególnych przypadkach , takich jak

(a) Wszystkie wielokąty są wypukłe ( wstępne przetwarzanie wielokątów można wykonać szybciej ),

(b) Wszystkie wnętrza wielokątów są rozłączne , w takim przypadku możesz myśleć o ich połączeniu jako pojedynczym wielokącie (co pozwala na proste, wydajne algorytmy, takie jak te oparte na triangulacji, i

(c) Większość wielokątów nie jest zbyt kręta - to znaczy, że zajmują duże części swoich obwiedni - w takim przypadku możesz wykonać wstępny test oparty tylko na obwiedniach, a następnie udoskonalić to rozwiązanie. To popularna optymalizacja.

(d) Liczba punktów jest duża. Sortowanie ich może poprawić czas. Na przykład podczas implementacji algorytmu przeciągania linii od lewej do prawej wielokątów posortujesz punkty na ich pierwszej współrzędnej, umożliwiając przeciąganie po punktach w tym samym czasie, gdy przeciągniesz po krawędziach wielokąta. Nie wiem, czy taka optymalizacja została opublikowana. Jedną z opublikowanych jest jednak wykonanie ograniczonej triangulacji połączenia wszystkich punktów i wierzchołków wielokąta: po zakończeniu triangulacji identyfikacja punktów wewnętrznych powinna być szybka. Koszt obliczeniowy będzie skalowany jako O (Q * log (Q) + (P + Q) * log (P + Q)).

Dane wielokąta rastrowego

Jest to niezwykle proste: wyświetl warstwę wielokąta jako binarny wskaźnik rastrowy (1 = wewnątrz wielokąta, 0 = na zewnątrz). (Może to wymagać tabeli przeglądowej do konwersji wartości rastrowych na wskaźniki wewnętrzne / zewnętrzne.) Każda sonda punktowa wymaga teraz wysiłku O (1) w celu zindeksowania komórki rastrowej i odczytania jej wartości. Całkowity wysiłek wynosi O (Q).

Ogólnie

Ładne rozwiązanie hybrydowew przypadku wielu statycznych wielokątów wektorowych (przypadek wektorowy 3 powyżej) jest początkowo rasteryzacja wielokątów, być może nawet z grubą rozdzielczością, tym razem rozróżniając wszelkie komórki przecinające dowolną część granicy wielokąta (powiedzmy, że mają wartość 2, powiedzmy) . Użycie sondy rastrowej (koszt: O (1)) zazwyczaj daje jednoznaczną odpowiedź (wiadomo, że punkt znajduje się wewnątrz lub na zewnątrz), ale czasami skutkuje nieokreśloną odpowiedzią (punkt wpada do komórki, przez którą co najmniej jedna krawędź passs), w którym to przypadku powstaje droższe zapytanie o wektor O (log (P)). Ta metoda wiąże się z dodatkowymi kosztami przechowywania dla rastra, ale w wielu przypadkach nawet mały raster (jeden MB pozwoli na raster 2000 na 2000, który przechowuje wartości {0,1,2, null}) może przynieść ogromne korzyści w czasie obliczeń . Asymptotycznie

Jeśli masz pola ograniczające wielokąty zapisane w czymś w rodzaju drzewa quad, możesz użyć tego do szybkiego określenia, które wielokąty mają zostać sprawdzone. Przynajmniej można było zobaczyć, czy punkt znajduje się wewnątrz każdej ramki granicznej wielokąta, w przeciwieństwie do wykonywania pełnego punktu w wielokącie dla każdego wielokąta. Osobiście skonfigurowałbym serwis internetowy, który buforowałby wielokąty w pamięci i używałby czegoś takiego jak JTS lub pakiet NetTopology, aby wykonać dla mnie zapytanie o przecięcie.

W Postgis ST_Intersects używa indeksów, aby najpierw sprawdzić, czy punkt znajduje się w obwiedni wielokąta, a następnie ponownie sprawdza, czy naprawdę znajduje się wewnątrz wielokąta. To jest szybkie, często bardzo szybkie.

Jeśli przechowujesz swoje dane w PostGIS, nie powinno być wątpliwości, że baza danych jest właściwym miejscem do obliczeń. W innych przypadkach będziesz musiał wysłać swoje wielokąty do jakiegoś programu środkowego lub klienta. To samo w sobie zajmie znacznie więcej czasu niż wykonanie obliczeń i uzyskanie odpowiednich wielokątów.

/ Nicklas