Prosty algorytm przecięcia wielokątów

Możesz użyć algorytmu obcinania wielokątów , aby znaleźć przecięcie między dwoma wielokątami. Jednak te wydają się być skomplikowane algorytmy, gdy wszystkie przypadki krawędzi są brane pod uwagę.

Jedną z implementacji obcinania wielokątów, której możesz użyć swojej ulubionej wyszukiwarki, jest Weiler-Atherton . artykuł na Wikipedii O Weiler-Atherton

Alan Murta ma kompletną implementację obcinacza wielokątów GPC .

Edit:

Innym podejściem jest najpierw podzielenie każdego wielokąta na zbiór trójkątów, z którymi łatwiej sobie radzić. Twierdzenie o dwóch uszach autorstwa Gary ' ego H. Meistersa rozwiązuje ten problem. Ta strona w McGill dobrze wyjaśnia podział trójkąta.

Jeśli używasz C++ i nie chcesz tworzyć algorytmu samodzielnie, możesz użyć Boost.Geometria . Wykorzystuje zaadaptowaną wersję wspomnianego powyżej algorytmu weilera-Athertona.

Nie dałeś nam swojej reprezentacji wielokąta. Więc wybieram (raczej sugeruję) jeden dla Ciebie:)

Reprezentuj każdy wielokąt jako jeden duży wielokąt wypukły oraz listę mniejszych wielokątów wypukłych, które należy 'odjąć' od tego dużego wielokąta wypukłego.

Teraz biorąc pod uwagę dwa wielokąty w tej reprezentacji, można obliczyć przecięcie jako:

Oblicz przecięcie dużych wielokątów wypukłych, aby utworzyć duży wielokąt przecięcia. Następnie "odjąć" przecięcia wszystkich mniejszych z obu, aby uzyskać listę podkategorii wielokątów.

Otrzymujesz nowy wielokąt po tej samej reprezentacji.

Ponieważ przecięcie wielokątów wypukłych jest łatwe, znalezienie przecięcia również powinno być łatwe.

Wydaje się, że to powinno zadziałać, ale nie myślałem o tym głębiej, jeśli chodzi o poprawność/złożoność czasu/przestrzeni.

Oto podejście oparte na triangulacji, które jest dość proste do wdrożenia i może być uruchomione w O (N²).

BTW, O (N²) jest optymalny dla tego problemu. Wyobraź sobie dwa wielokąty w kształcie łopatek widełek przecinających się pod kątem prostym. Każdy z nich ma liczbę segmentów proporcjonalną do liczby zębów; liczba wielokątów na przecięciu jest proporcjonalna do kwadratu liczby zębów.

1. Po pierwsze, triangulować każdy wielokąt.

2. Porównaj wszystkie trójkąty z P parami ze wszystkimi trójkątami z Q, aby wykryć przecięcia. Każda para przecinających się trójkątów może być podzielona na mniejsze Trójkąty, z których każdy jest w P, W Q lub w przecięciu. (Cokolwiek zostało użyte w kroku 1, można ponownie wykorzystać w tym celu.) Zachowaj tylko Trójkąty znajdujące się na skrzyżowaniu.

3. Oblicz sąsiadów każdego trójkąta, porównując je parami, i zbuduj Wykres przyległości. Ten wykres będzie zawierać jeden połączony podgraf dla każdego wielokąta na przecięciu P I Q.

4. Dla każdego takiego podgrafu wybierz Trójkąt, przejdź do krawędzi, a następnie przejdź wokół krawędzi, tworząc segmenty obwiedni odpowiadające wielokątowi wyjściowemu.

Oto proste i głupie podejście: przy wejściu dyskrecjonuj swoje wielokąty w bitmapę. Przecinać i bitmapy razem. Aby wytworzyć wielokąty wyjściowe, wyznaczaj poszarpane granice bitmapy i wygładzaj je za pomocą algorytmu przybliżania wielokątów . (Nie pamiętam, czy ten link daje najbardziej odpowiednie algorytmy, to tylko pierwszy hit Google. Możesz sprawdzić jedno z dostępnych narzędzi do konwersji obrazów bitmapowych na reprezentacje wektorowe. Może mógłbyś zadzwonić na nich bez ponownego wdrożenia algorytmu?)

Najbardziej złożoną częścią byłoby wytyczanie granic, tak myślę.

Na początku lat 90-tych miałem do czynienia z czymś takim w pracy, tak przy okazji. Wymyśliłem (zupełnie inny) algorytm, który działałby na współrzędnych liczb rzeczywistych, ale wydawało się, że natknie się na zupełnie nieosiągalną masę zdegenerowanych przypadków w obliczu rzeczywistości zmiennoprzecinkowej (i hałaśliwego wejścia). Być może z pomocą internet zrobiłbym lepiej!

Nie mam bardzo prostego rozwiązania, ale oto główne kroki dla prawdziwego algorytmu:

1. wykonaj custom double linked list for the polygon vertices and krawędzie. Użycie std::list nie da rady, ponieważ musisz zamienić następny i poprzednie wskaźniki / przesunięcia się do specjalnej operacji na węzły. Jest to jedyny sposób, aby mieć prosty kod, a to da dobry występ.
2. znajdź punkty przecięcia, porównując każdą parę krawędzi. Uwaga że porównując każdy para krawędzi da Czas O (N2), ale poprawa algorytm do O (N * logN) będzie później łatwy. Dla jakiejś pary krawędziach (powiedzmy A→b I c → d), punkt przecięcia znajduje się za pomocą parametr (od 0 do 1) na krawędzi a→b, który jest dany przez tₐ=d₀/(d₀-d₁), gdzie d₀ (Z-A)×(B-A) i d₁ E (D-A)×(W-a). × jest iloczyn krzyżowy 2D, np. p×q=pₓ * qᵧ-pᵧ * qₓ. Po znalezieniu tₐ, znalezienie punktu przecięcia to użycie go jako interpolacji liniowej parametr na segmencie a→b: P = a + tₐ (b-a)
3. Podziel każdą krawędź dodając wierzchołki (i węzły na liście połączonych) gdzie przecinają się segmenty.
4. Następnie musiszprzekroczyć węzły w punktach przecięcia. To jest operacja, dla której trzeba było wykonać niestandardowe podwójne połączenie lista. Musisz zamienić parę następny wskaźnik (i zaktualizować poprzednie odpowiednio).

Następnie masz nieprzetworzony wynik algorytmu rozwiązywania przecięć wielokątów. Zwykle będziesz chcesz wybrać jakiś region zgodnie z numerem uzwojenia każdego regionu. Poszukaj Liczby uzwojenia wielokąta, aby uzyskać wyjaśnienie na ten temat.

Jeśli chcesz zrobić algorytm O(N·logN) z tego o(N2), musisz zrobić dokładnie to samo, z wyjątkiem tego, że robisz to wewnątrz algorytmu zamiatania linii. Poszukaj algorytmu Bentleya Ottmana . Wewnętrzny algorytm będzie taki sam, z tą tylko różnicą, że będziesz miał zmniejszoną liczbę krawędzi do porównania, wewnątrz pętla.

Sposób, w jaki pracowałem nad tym samym problemem

1. rozbicie wielokąta na odcinki linii
2. znajdź przecinającą się linię używając IntervalTrees LUB LineSweepAlgo
3. znajdowanie zamkniętej ścieżki używając GrahamScanAlgo, aby znaleźć zamkniętą ścieżkę z sąsiednimi wierzchołkami
4. Odsyłacz 3. z DinicAlgo aby je rozpuścić

Uwaga: mój scenariusz był inny, ponieważ wielokąty miały wspólny wierzchołek. Ale mam nadzieję, że to może pomóc

Może to być ogromne przybliżenie w zależności od twoich wielokątów, ale oto jeden:

• Oblicz środek masy dla każdego wielokąt.
• Oblicz min lub max lub średnią odległość od każdego punktu wielokąt do środka masy.
• Jeśli C1C2 (gdzie C1/2 jest środkiem pierwszego/drugiego wielokąta) >= D1 + D2 (gdzie D1 / 2 jest odległością obliczoną dla pierwszego / drugiego wielokąta), to dwa wielokąty "przecinają się".

Chociaż powinno to być bardzo skuteczne, ponieważ każda transformacja do wielokąta odnosi się w ten sam sposób do środka masy, A odległości środek-węzeł można obliczyć tylko raz.