Najpierw wiem, że podobne pytanie już jest zadawane, ale używa innej struktury i jest w C (Podziel wielokąt własny, który przecina się z sobą (kod C)), moje pytanie jest trochę inne.
Mam punkty przecinającego się wielokąta, jego krawędzie, a także jestem w stanie znaleźć punkty, w których przecina się on sam za pomocą algorytmu Bentleya-Ottmanna.
Planowałem zbudować nieparzystujące wielokątyedytując krawędzie wokół punktów przecięcia, ale problem występuje, gdy przecinają się dwie krawędzie, nie wiesz, które dwie z czterech stron znajdują się wewnątrz i które znajdują się poza polem.
Mógłbym użyć algorytmu przecinania promieni w celu rozwiązaniato, ale jest zbyt wolne. Jego złożoność czasowa to O (n), a ja dwa razy robię to co najmniej dwa razy dla każdego punktu przecięcia, więc byłby bardzo powolny z około 200k punktów wielokąta.
Pytam więc, czy istnieje szybszy sposób podziału przecinającego się siebie wielokąta na wielokąty, które nie są przecinane przez siebie.
Potrzebuję tego, ponieważ robię wielokąttriangulacja. Zrobiłem już algorytm triangulacji liniowej dla triangulacji nie-siebie przecinających się wielokątów z dziurami. Po prostu potrzebuję, aby tablica tych wielokątów była wejściowa.
Odpowiedzi:
1 dla odpowiedzi № 1Jako etap wstępnego przetwarzania możesz obliczyćkażda krawędź, która strona krawędzi określa zewnętrzną część wieloboku. Jest to znacznie tańsze niż czas O (n) dla każdego punktu przecięcia. Następnie, gdy dwie krawędzie przecinają się, możesz określić, które dwa segmenty linii znajdują się na zewnątrz, a które dwa są wewnątrz.