Punkt w wielokącie
W geometrii obliczeniowej problem punktu w wielokącie ( PIP ) polega na pytaniu, czy dany punkt na płaszczyźnie leży wewnątrz, na zewnątrz lub na granicy wielokąta . Jest to szczególny przypadek lokalizacji punktów i znajduje zastosowanie w obszarach zajmujących się przetwarzaniem danych geometrycznych, takich jak grafika komputerowa , wizja komputerowa , systemy informacji geograficznej (GIS), planowanie ruchu i projektowanie wspomagane komputerowo (CAD).
Wczesny opis problemu w grafice komputerowej pokazuje dwa popularne podejścia ( odlewanie promieni i sumowanie kątów) stosowane już w 1974 roku.
Próbę prześledzenia historii problemu przez weteranów grafiki komputerowej i kilka sztuczek jego rozwiązania można znaleźć w numerze Ray Tracing News .
Algorytm rzucania promieni
Prostym sposobem ustalenia, czy punkt znajduje się wewnątrz, czy na zewnątrz wielokąta prostego, jest sprawdzenie, ile razy promień rozpoczynający się od punktu i biegnący w dowolnym ustalonym kierunku przecina krawędzie wielokąta. Jeśli punkt znajduje się na zewnątrz wielokąta, promień przetnie jego krawędź parzystą liczbę razy. Jeśli punkt znajduje się po wewnętrznej stronie wielokąta, to przetnie on krawędź nieparzystą liczbę razy. Status punktu na krawędzi wielokąta zależy od szczegółów algorytmu przecięcia promieni.
Algorytm ten jest czasami znany również jako algorytm liczb przecinających się lub algorytm reguł parzystych i nieparzystych i był znany już w 1962 r. Algorytm opiera się na prostej obserwacji, że jeśli punkt porusza się wzdłuż promienia od nieskończoności do punktu sondy i jeśli przekroczy granicę wielokąta, być może kilka razy, to na przemian idzie z zewnątrz do wewnątrz, potem z wewnątrz na zewnątrz itd. W rezultacie po każdych dwóch „przejściach granicznych” ruchomy punkt wychodzi na zewnątrz. Obserwację tę można udowodnić matematycznie za pomocą twierdzenia o krzywej Jordana .
Ograniczona precyzja
Jeśli zostanie zaimplementowany na komputerze z arytmetyką skończonej precyzji , wyniki mogą być nieprawidłowe, jeśli punkt leży bardzo blisko tej granicy, z powodu błędów zaokrągleń. W przypadku niektórych aplikacji, takich jak gry wideo lub inne produkty rozrywkowe, nie stanowi to dużego problemu, ponieważ często przedkładają szybkość nad precyzję. Jednak dla formalnie poprawnego programu komputerowego należałoby wprowadzić tolerancję numeryczną ε i sprawdzić w linii, czy P (punkt) leży w obrębie ε od L (linii), w którym to przypadku algorytm powinien się zatrzymać i zgłosić „ P leży bardzo blisko granicy”.
Większość implementacji algorytmu rzutowania promieni kolejno sprawdza przecięcia promienia ze wszystkimi bokami wielokąta. W takim przypadku należy rozwiązać następujący problem. Jeśli promień przechodzi dokładnie przez wierzchołek wielokąta, to przetnie 2 segmenty w ich punktach końcowych. O ile w przypadku najwyższego wierzchołka w przykładzie lub wierzchołka między skrzyżowaniami 4 i 5 jest OK, o tyle w przypadku prawego wierzchołka (w przykładzie) do poprawnego działania algorytmu wymagane jest policzenie jednego przecięcia. Podobny problem pojawia się w przypadku segmentów poziomych, które przypadkowo spadają na promień. Problem jest rozwiązany w następujący sposób: Jeśli punkt przecięcia jest wierzchołkiem testowanego boku wielokąta, to przecięcie liczy się tylko wtedy, gdy drugi wierzchołek boku leży poniżej półprostej. Jest to faktycznie równoważne rozważeniu wierzchołków na promieniu jako leżącego nieco powyżej promienia.
Po raz kolejny przypadek promienia przechodzącego przez wierzchołek może stwarzać problemy numeryczne w arytmetyce o skończonej precyzji : dla dwóch boków sąsiadujących z tym samym wierzchołkiem proste obliczenie przecięcia z promieniem może nie dać wierzchołka w obu przypadkach. Jeśli wielokąt jest określony przez jego wierzchołki, problem ten można wyeliminować, sprawdzając współrzędne y promienia i końce testowanego boku wielokąta przed faktycznym obliczeniem przecięcia. W innych przypadkach, gdy boki wielokątów są obliczane na podstawie innych typów danych, należy zastosować inne sztuczki, aby zapewnić numeryczną niezawodność algorytmu.
Algorytm liczby uzwojeń
Inną techniką używaną do sprawdzania, czy punkt znajduje się wewnątrz wielokąta, jest obliczenie liczby zwojów danego punktu w odniesieniu do wielokąta. Jeśli numer uzwojenia jest różny od zera, punkt leży wewnątrz wielokąta. Algorytm ten jest czasami znany jako algorytm reguły niezerowej .
Jednym ze sposobów obliczenia liczby zwojów jest zsumowanie kątów leżących naprzeciw każdego boku wielokąta. Wiąże się to jednak z kosztownymi odwrotnymi funkcjami trygonometrycznymi , co generalnie sprawia, że ten algorytm jest nieefektywny (wolniejszy) w porównaniu z algorytmem rzucania promieni. Na szczęście tych odwrotnych funkcji trygonometrycznych nie trzeba obliczać. Ponieważ wynik, suma wszystkich kątów, może sumować się do 0 lub wielokrotności ) wystarczy prześledzić, przez które ćwiartki wije się wielokąt, obracając się wokół badanego punktu, co sprawia, że algorytm liczby zawijania jest porównywalny pod względem szybkości do liczenia przejść granicznych.
Ulepszony algorytm do obliczania liczby uzwojeń został opracowany przez Dana Sundaya w 2001 roku. Nie wykorzystuje on kątów w obliczeniach ani żadnej trygonometrii i działa dokładnie tak samo, jak opisane powyżej algorytmy rzucania promieni. Niedzielny algorytm działa na podstawie nieskończonego rzutu promienia poziomego z sprawdzanego punktu. Ilekroć ten promień przecina krawędź wielokąta, algorytm przekraczania krawędzi Juana Pinedy (1988) jest używany do określenia, w jaki sposób skrzyżowanie wpłynie na liczbę uzwojeń. Jak opisuje to Sunday, jeśli krawędź przecina promień idąc „w górę”, numer uzwojenia jest zwiększany; jeśli przecina promień „w dół”, liczba jest zmniejszana. Algorytm z niedzieli daje poprawną odpowiedź dla nieprostych wielokątów, podczas gdy algorytm przekraczania granic w tym przypadku zawodzi.
Implementacje
SVG
Podobne metody są stosowane w SVG do definiowania sposobu wypełniania kolorem różnych kształtów (takich jak ścieżka, polilinia, wielokąt, tekst itp.). Na algorytm wypełniania ma wpływ atrybut „fill-rule”. Wartość może być różna od zera lub parzysta . Na przykład na niewypukłej regularnej pięciokątnej powierzchni znajduje się centralna „dziura” (widoczne tło) o parzystości i żadna nie ma atrybutu niezerowego .
W przypadku prostych wielokątów algorytmy dadzą ten sam wynik. Jednak w przypadku złożonych wielokątów algorytmy mogą dawać różne wyniki dla punktów w regionach, w których wielokąt się przecina, gdzie wielokąt nie ma jasno określonej wewnętrznej i zewnętrznej strony. Jednym z rozwiązań wykorzystujących regułę parzysto-nieparzystą jest przekształcenie (złożonych) wielokątów w prostsze, które są równoważne parzysto-nieparzyste przed sprawdzeniem przecięcia. Jest to jednak kosztowne obliczeniowo. Tańsze jest użycie szybkiego algorytmu niezerowej liczby uzwojeń, który daje poprawny wynik nawet wtedy, gdy wielokąt się pokrywa.
Punkt w zapytaniach dotyczących wielokątów
Problem punktu w wielokącie można rozpatrywać w ogólnym ustawieniu powtarzanego zapytania geometrycznego: biorąc pod uwagę pojedynczy wielokąt i sekwencję punktów zapytania, szybko znajdź odpowiedzi dla każdego punktu zapytania. Oczywiście można zastosować dowolne z ogólnych podejść do lokalizacji punktu płaskiego. Dla niektórych specjalnych wielokątów dostępne są prostsze rozwiązania.
Przypadki specjalne
Prostsze algorytmy są możliwe dla wielokątów monotonicznych , wielokątów w kształcie gwiazdy , wielokątów wypukłych i trójkątów .
Przypadek trójkąta można łatwo rozwiązać za pomocą barycentrycznego układu współrzędnych , równania parametrycznego lub iloczynu skalarnego . Metoda iloczynu skalarnego rozciąga się naturalnie na dowolny wielokąt wypukły.
Zobacz też
- Java Topology Suite (JTS)
- Dyskusja: http://www.ics.uci.edu/~eppstein/161/960307.html
- Metody nawijania i numerowania krzyżowania: http://geomalgorithms.com/a03-_inclusion.html