Jak mogę dodawać i odejmować wypukłe wielokąty?

Mam dwa nachodzące na siebie wielokąty 2D . Szukam algorytmu do odejmowania i dodawania ich. Rezultatem musi być pojedynczy wklęsły wielokąt lub (jeszcze lepiej) zestaw największych wypukłych tworzących wynik wklęsły (np. Trójkąty).

(Po lewej: Początkowe zachodzące na siebie wielokąty. Środek: Powstały wielokąt wklęsły po dodaniu. Po prawej: Zestaw wielokątów wypukłych tworzących wklęsły wynik. W tym przypadku lepiej byłoby uzyskać wypukłe wielokąty większe niż trójkąt ze względów wydajnościowych. Odejmowanie dwa zachodzące na siebie wielokąty doprowadziłyby do tego samego obrazu, co po lewej, ale z nakładającym się obszarem nie będącym częścią wynikowego wielokąta.)

W jaki sposób mogę to zrobić?

TL; DR Musisz zaimplementować operacje boolowskie przy użyciu drzew BSP.

Wygląda na to, że mówimy tutaj o konstruktywnej geometrii bryły . Wdrożyłem CSG na poziomie komercyjnym, więc wiem coś na ten temat.

Klasyczny artykuł na temat CSG nazywa się Scalanie drzew BSP Daje wielościenne operacje na zestawach , szczerze mówiąc, to zbyt wiele do wyjaśnienia tutaj, ale w skrócie algorytm zajmuje się wielokątami, które leżą na tej samej płaszczyźnie co podział przestrzeni binarnej, w zasadzie konstruowanie drzewo BSP z każdej siatki wielokątnej. Drugim krokiem jest połączenie tych drzew BSP; po prostu bierzesz jedno drzewo i wkładasz je do drugiego. Algorytm następnie wyjaśnia, jak postępować z każdym węzłem liścia do dzielenia i odejmowania węzłów, węzły, które nie są potrzebne w ostatecznym kształcie, zostaną usunięte, inne otrzymają odpowiedni rodzic.

Ale poczekaj! Ten artykuł zasadniczo mówi o siatkach wielokątnych i płaszczyznach 3D, NIE?

Algorytm można uogólnić na dowolny wymiar, więc w przypadku 2D łatwo jest używać segmentów linii zamiast płaszczyzny jako partycji binarnych. Tak więc każdy wielokąt zostanie przekonwertowany na drzewo BSP, a następnie zostaną połączone. Na koniec przejdziesz przez powstałe drzewo, aby wygenerować końcowy wielokąt,

Zauważ, że ten algorytm i CSG w ogóle nie radzą sobie bezpośrednio z renderowaniem i siatkami ścian i nie są tak naprawdę gotowe do renderowania, więc musisz wyodrębnić ściany ostatecznych drzew BSP. Uważam również, że śledzenie promieni jest łatwiejszym podejściem do renderowania wyniku CSG, wystarczy, że promienie przemierzają drzewo zamiast wyodrębniać i faktycznie dzielić twarze (pamiętaj, że mamy do czynienia tylko z partycjami binarnymi).

Odnośnie solidności numerycznej. Warto zauważyć, że istnieją dwa rodzaje obliczeń geometrycznych,

• Te, które są oparte na konstrukcji, budujesz kształt na podstawie wyniku poprzedniej operacji. Na przykład, y = sqrt(x)a następnie użyj yw nowej operacji. Nazywa się to budową; problemem jest to, że błędy numeryczne będą się szybko kumulować.
• Alternatywnie istnieją operacje, które zamiast tego używają predykatów , w zasadzie zamiast konstrukcji, po prostu pytasz, czy warunek jest prawdziwy / fałszywy i używasz tej samej wartości w różnych operacjach. Klasyczne testy obejmują okrążenie i test orientacji; jest to również podejrzane o błędy numeryczne, szczególnie jeśli używasz pojedynczej lub podwójnej precyzji, ale zwykle daje to znacznie lepsze wyniki. istnieją inne rozwiązania, które różnią się szybkością i dokładnością. Oto jeden z najnowszych artykułów, w którym unika się budowy, stosując geometrię opartą na płaszczyźnie, aby uzyskać dokładne wyniki. Zacytuję również z artykułu:

Pojęcie płaskiej reprezentacji siatek wielokątnych zostało po raz pierwszy opisane przez Sugihara i Iri [SI89]. Ten rodzaj reprezentacji zapewnia jedną ważną zaletę, jeśli chodzi o zadania polegające na zmianie topologii brył reprezentowanych przez siatki, takie jak ocena wyrażeń logicznych: nie trzeba konstruować żadnych nowych informacji o podstawowej geometrii, aby uzyskać wynikowy wielościan

Na koniec chciałbym dodać, jeśli chcesz rozpocząć wdrażanie BSP CSG, polecam zacząć od BSP Faqs .

Idąc za przykładem:

Wybierz wierzchołek początkowy na wielokącie A, a następnie rozpocznij sprawdzanie przecinających się krawędzi zgodnie z ruchem wskazówek zegara (lub przeciwnie do ruchu wskazówek zegara). Jeśli nie ma przecięcia, dodaj poprzedni wierzchołek do wynikowego wielokąta. Jeśli istnieje przecięcie, dodaj punkt, w którym przecinają się do powstałego wielokąta, a następnie rozpocznij iterację nad wielokątem B, w tej samej kolejności nawijania. Zrób to samo, ponownie przełączając się na wielokąt A, jeśli dojdzie do przecięcia.

Po zgromadzeniu wszystkich wierzchołków dla nowego wielokąta, wykonaj na nim algorytm triangulacji. Metoda przycinania uszu jest łatwa do wdrożenia, ale istnieją szybsze opcje.

Ważne: upewnij się, że wierzchołek, od którego zaczynasz, nie znajduje się w drugim wielokącie (sprawdź w tym artykule punkt w testach wielokąta).

Iteracja po każdej krawędzi w celu sprawdzenia przecięcia byłaby algorytmem O (n ^ 2). Możesz to przyspieszyć, najpierw znajdując wierzchołki znajdujące się w drugim wielokącie, ponieważ krawędzie połączone z tymi wierzchołkami będą przecinające się.

Jeśli chcesz wielokąt wklęsły , po prostu wybierz najbliższą krawędź między dwoma wielokątami wejściowymi i dodaj dwie nowe krawędzie:

Wypukły staje się nieco bardziej skomplikowany:

Jedno podejście jest iteracyjne, ponieważ dodaje wierzchołki od drugiego wielokąta do pierwszego, jeden po drugim, przekształcając pierwszy wielokąt w pojemnik, który obejmuje wszystko.

Gruntownie:

• Iteruj przez wierzchołki drugiego wielokąta.
• Dla każdego wierzchołka V, iteruj przez krawędzie pierwszego wielokąta:
• Znajdź „zakres” krawędzi skierowanych w stronę wierzchołka
• weź zewnętrzną parę wierzchołków, które definiują ten zakres, i usuń wszystkie krawędzie w zakresie, który je łączy
• Narysuj dwa nowe segmenty od tych zewnętrznych wierzchołków do nowego wierzchołka (od drugiego wielokąta), upewniając się, że nowe krawędzie są skierowane we właściwym kierunku.
• Przejdź do następnego wierzchołka od drugiego wielokąta

Oto schemat ilustrujący proces dla pierwszego wierzchołka:

Szybszą metodą jest znalezienie listy krawędzi na każdym wielokącie, które nie są skierowane do drugiego wielokąta, usunięcie całej reszty i połączenie punktów końcowych pozostałych pasków linii ze sobą.

Być może ktoś inny może wprowadzić jakieś porady dotyczące odejmowania.