Dzielenie słabo prostego wielokąta na prawdziwy prosty wielokąt lub wielokąty

Question

Chcę podzielić słabo proste wielokąty w proste wielokąty.

Tło

Zastosowanie przypadku jest uproszczenie wielokątów są uproszczone (Unioned) za pomocą Javascript Clipper. Funkcja Javascript Clipper, a także original Clipper'sSimplifyPolygon() powoduje usunięcie przecinków i łączy wspólne krawędzie, ale nie jest w stanie wygenerować prawdziwych prostych wielokątów. Dane wyjściowe są używane w pliku three.js, który ma TriangulateShapes(), który wymaga prostego wielokątów. Three.js akceptuje struktury wieloboków, które mają jeden kontur i zero lub wiele otworów.

wejściowe, słabo wielokąt prosty

słabo wielokąt prosty nie może mieć sekwencyjnym Duplikat wierzchołki (true zduplikowanych punktów), ani dziur (wyspy), ani samorządy skrzyżowaniach (przejście przewagę nad drugim brzegu), ale mogą istnieć nie-sekwencyjne-wielokrotne wierzchołki (wierzchołki, które mają dokładnie taką samą współrzędną, ale nie jako sekwencyjne). Wielokąt wejściowy może mieć kolejność uzwojenia CW lub CCW, co oznacza, że ​​wejście CW jest zewnętrznym poligonem, a CCW jest otworem. Wejście jest wielokątem CW lub CCW.

Wejście jest tablicą punktów wielokąta np .:

 

// This is a true example of weakly-simple polygon: 

var input = [{"X":270,"Y":520},{"X":130,"Y":490},{"X":210,"Y":250},{"X":60,"Y":170},{"X":130,"Y":490},{"X":20,"Y":410},{"X":60,"Y":300},{"X":60,"Y":20},{"X":780,"Y":40}, {"X":680,"Y":180},{"X":460,"Y":130},{"X":210,"Y":250},{"X":320,"Y":100},{"X":220,"Y":80}, {"X":210,"Y":250},{"X":520,"Y":250},{"X":680,"Y":180},{"X":770,"Y":480},{"X":540,"Y":470}, {"X":520,"Y":250},{"X":380,"Y":280},{"X":430,"Y":390},{"X":540,"Y":470},{"X":270,"Y":520},{"X":330,"Y":350},{"X":210,"Y":250}]; 

To powyżej input wielokąt jako obraz:

I tu są numerowane punkty, gdzie można łatwo sprawdzić, które punkty są duplikaty:

Jak widać, powyższe wielokąta można podzielić na wiele sposobów, np .:
- Jeden zewnętrzny wielokąta z pięcioma otworami - pięć zewnętrznych wielokątów, z których jeden ma jeden otwór

wyjścia, wielokąt prosty jak Struktura exPolygon

Prosty wielokąt jest wielokątem, który nie ma samo-przecięć, nie ma duplikatów współrzędnych, czy były sekwencyjne czy niesekwencyjne, bez dziur. Prosty wielokąt wyjścia może mieć kolejność uzwojenia CW lub CCW. CW oznacza otwory zewnętrzne i CCW.

Dane wyjściowe mogą mieć (i wiele razy będą) otwory, ale w niektórych przypadkach wyjście nie ma żadnych otworów. Wyjście ma zawsze co najmniej jeden zewnętrzny wielokąt, ale może istnieć również wiele zewnętrznych wielokątów, które mają zero lub więcej dziur.

Dane wyjściowe powinny być tablicą obiektów exPolygon, które mają właściwości "zewnętrzny" i "otwory". "zewnętrzna" to tablica obiektów punktowych, "dziury" to tablica tablic obiektów punktowych. Jeśli "otwory" są wypełnione, otwory w nich muszą być otworami "zewnętrznego" wielokąta w obiekcie exPolygon.

Przykład wyjścia: "zewnętrzny" wielokąty

 

// This is an example of output, but the points are random: 

[ { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}], 
    "holes": [ [{"X":0,"Y":8},{"X":60,"Y":13},{"X":21,"Y":2},{"X":3,"Y":1}], 
       [{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}] ] }, 
    { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}], 
    "holes": [ [{"X":0,"Y":8},{"X":60,"Y":13},{"X":21,"Y":2},{"X":3,"Y":1}], 
       [{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}] ] }, 
    { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}], 
    "holes": [] } 
]; 

wyjściowym są CW i "dziury" są CCW.

Nie ma limitu liczby punktów w wielokątach, liczby obiektów ExPoligons ani liczby dziur.

tutaj także inne przykłady słabo prostych wielokątów:

Przykład podziału

tu przykład wielokąta wejściowych:

Oto jak można podzielić:

Niektóre inne wielokąty mogą mieć wiele możliwych alternatywy ouput zależności gdzie są pseudo-duplikat punkty.

---

Moje pytanie

Jak wielokąty mogą być podzielone w ten sposób i pożądanej struktury wyjściowej osiągnąć? Nie pytam o pełny kod (ale jeśli masz trochę wolnego czasu i chcesz pokazać, że jest to możliwe). Myśli o możliwych algorytmach są również mile widziane.

---

Szukałem godziny rozwiązanie i próbowałem znaleźć algorytm.

Jeśli chcesz wypróbować rozwiązanie, mam tutaj kod, którego użyłem do znalezienia duplikatów: http://jsbin.com/unuyev/7/edit. Pokazuje wielobok w SVG i pokazuje punkty jako czerwone kółka i indeks tablicy każdego punktu (po naciśnięciu przycisku "Uruchom z JS").

Tutaj jest ten sam, ale z 12 Przykład wielokątów (zmiana pindex w oknie JavaScript, żeby zmienić wielokąt): http://jsbin.com/unuyev/4/edit

---

EDIT: Javascript Clipper 6 jest już dostępny i nie ma wsparcia dla StrictlySimple. Ale zgodnie z dokumentacją "Obecnie nie ma gwarancji, że wielokąty będą bardzo proste, ponieważ" upraszczanie "jest nadal w toku". Przetestowałem StrictlySimple i nie działa w niektórych przypadkach: Orientation problems i lack of rotation invariance. Mamy nadzieję, że zostaną one wkrótce naprawione, a StrictlySimple działa zgodnie z oczekiwaniami.

---

Answer 1

Może być coś, czego mi brakuje, ale wygląda to na klasyczny problem ze znalezieniem wierzchołka przegubu wykresu. Zasadniczo próbujesz znaleźć najsłabszy punkt na wykresie, tak, że po przecięciu wykresu w tym momencie kończy się on dwoma oddzielnymi wykresami. W twoim przykładzie, jeśli przecinałeś wielokąt w tym wierzchołku, otrzymujesz wiele wielokątów. Możesz przedstawiać swoje wielokąty całkiem łatwo jako wykres, z każdym wierzchołkiem reprezentującym wierzchołek wykresu, a krawędzie wielokątu jako krawędzie wykresu.

Gdybym musiał rozwiązać problem, to podejście, które brałbym.Możesz sprawdzić następujące zasoby:

• Articulation vertices from the Algorithm Design Manual - To jest twój najlepszy zakład. Wyjaśnia algorytm w prostych słowach, a także daje kod C, który można łatwo przetłumaczyć na JavaScript. Gdybym miał zacząć pisać algorytm, to tutaj zacznę.
• Biconnected component
• Detection of Articulation Points (szukaj "przegubu")

UPDATE

Postaram i daje krótki opis problemu oraz rozwiązania do punktu, w prawo kierunek. Implementacja tego algorytmu za pomocą wykresów będzie musiała przejść do terminologii algorytmów graficznych, więc jeśli nie jesteś zaznajomiony z wykresami, możesz chcieć je przeczytać.

Podejście brute-force w twoim przypadku polegałoby na przejściu przez wykres, tymczasowym usunięciu każdego werteksa, a następnie sprawdzeniu, czy wykres jest podłączony podczas przejścia przez DFS/BFS na zmodyfikowanym wykresie. To nie jest zbyt wydajne i będzie działać w systemie kwadratowym O(n(m + n)). Ale istnieje algorytm liniowy, który opiera się na klasyfikacji krawędzi wynikowego drzewa DFS utworzonego podczas przejścia przez DFS.

W drzewie DFS, które nie zawiera żadnych tylnych krawędzi (krawędzie łączące "niższy" węzeł z węzłem "wyższe" w drzewie [zakładając "wyższe" węzły to te bliżej korzenia]) węzły liści nie są węzłami przegubowymi, ponieważ usunięcie któregokolwiek z nich nadal pozostawi wykres połączony. Jednak usunięcie dowolnego z wewnętrznych węzłów spowoduje rozłączenie wszystkich węzłów, które nastąpią po nim z katalogu głównego.

Usunięcie katalogu głównego drzewa zależy od tego, czy ma jedno lub więcej dzieci. Jeśli ma tylko jedno dziecko, to jest mniej więcej liście, więc usunięcie go nie przyniesie efektu. Jednak usunięcie węzła głównego, który ma więcej niż jedno dziecko, spowoduje odłączenie wykresu.

Ale na ogólnym wykresie możesz mieć tylne krawędzie, więc usunięcie żadnego z węzłów pośrednich nie spowoduje odłączenia wykresu. Tak więc ustalenie wierzchołków przegubowych sprowadza się do ustalenia, które sekcje drzewa są połączone z węzłami nadrzędnymi tylnymi krawędziami (tj. Ustalenie "osiągalnego przodka" wierzchołka).

Na stronie, do której podłączyłem się w Podręczniku projektowania algorytmów, Skiena opisuje trzy przypadki, w których wierzchołek może być wierzchołkiem przegubowym (węzłem głównym, mostem i węzłem nadrzędnym). Używając opisanego przez siebie algorytmu, możesz dowiedzieć się, czy przetwarzany przez ciebie wierzchołek spełnia którykolwiek z tych warunków. Jeśli tak, jest węzłem artykulacyjnym.

Mam nadzieję, że to pomoże Ci zacząć!