Oblicz połączenie dwóch dowolnych kształtów

Pracuję nad aplikacją, muszę móc łączyć dwa zachodzące na siebie dowolne kształty rysowane przez użytkownika. Byłaby to operacja unijna na dwóch kształtach. Powstały kształt będzie sylwetką dwóch zachodzących na siebie kształtów.Oblicz połączenie dwóch dowolnych kształtów

Kształty są zapisywane jako sekwencja punktów zgodnie z ruchem wskazówek zegara.

Idealnie chciałbym algorytm, który zajmie dwie tablice punktów (x, y) i zwróci pojedynczą tablicę wynikowego kształtu.

Czytałem Wikipedia na Boolean operations on polygons, która wspomina o Sweep line algorithm, ale nie mogę utworzyć powiązania między tym a moim celem, niestety nie jestem matematykiem.

Zajmuję się tworzeniem aplikacji w języku ActionScript 3, ale znam język C#, Javę i ja potrafię wybierać między C i C++.

Źródło

2010-01-26 Greg B

Prawidłowe wykonanie operacji boolowskich nie jest proste; na szczęście istnieją biblioteki, które już implementują tę funkcjonalność.

W jakim języku się posługujesz? Jeśli to C++, spójrz na CGAL, Computational Geometry Algorithms Library.

Źródło

2010-01-26 14:48:47

Dzięki, jestem wykonawczych w AS3 ale zaznajomieni z C#, Java –

Ach ... cóż, nie jestem pewien, jeśli kod źródłowy CGAL jest tak zabawny, że można go rozróżniać i portować, ponieważ wyraża on swoje algorytmy w dość ogólny sposób, wzorowany na STL (IIRC, to już dawno). Lepszym rozwiązaniem może być przeniesienie jednej z bardziej specyficznych bibliotek połączonych z dnem strony Wikipedii. Alternatywnie, możesz uciec po prostu renderując oba poligony do bitmapy, a następnie wykonując operacje boolean na tym? –

Znalazłem ten (częściowy) port AS3 portu Java GPC http://code.google.com/p/gpcas/ który obsługuje operacje UNION. Dzięki za wkład. –

Biorąc pod uwagę dwa wykazy punktów (A i B)
- [1] dla każdego wiersza w to przecinają linię w B
-.- [2] jeśli nie (więcej) linie przecinają się, nie ma brak nakładania się
-.- [3] jeśli linia w (A) przecina linię w B to
-.-.- [4] dodać punkt przecięcia na wyjściu
-.-.- [5] czy następna linia od A przecina B
-.-.-.- [6] jeśli nie, dodaj to do wyjścia (jest w środku B) goto 5
-.-.-.- [7] jeśli tak, to dodaj przecinają się z wyjściami i przełączają listy A & B goto 2

Zobacz także Intersection Point Of Two Lines. Nie piszę kodu przepraszam :)

Źródło

2010-01-26 15:07:04

+1: Brzmi jak przyzwoite podejście do mnie –

dziękuję Jon ... powinien również powiedzieć "dodaj logikę, aby uniknąć nieskończonej pętli" –

Uwaga - ten problem nie jest tak proste, jak myślisz. Pewne jedzenie do przemyślenia: Jedna linia (lub "krawędź") w A może przecinać więcej niż jedną krawędź w B. Dwa pierwotne wielokąty mogą być rozłączne; lub A może leżeć całkowicie w obrębie B; lub B może leżeć całkowicie wewnątrz A (chociaż te trzy przypadki wyglądają tak samo, jeśli patrzysz tylko na przecięcia między liniami). Wielokąty nie muszą być wypukłe, a połączenie dwóch nie wypukłych wielokątów może mieć dziury. I tak dalej ... Geometria obliczeniowa jest znana ze wszystkiego, o czym nie myśli się na początku. –

Czy dla ciebie byłby this algorithm?

Źródło

2010-01-26 15:10:04

+1 Dałbym temu pierwsze tbh! –

Algorytm ten oblicza przecięcie; Greg B szuka związku. Algorytm ten działa również wtedy, gdy zarówno wielokąty, jak i ich przecięcia są wypukłe; Greg B mówi o "arbitralnych kształtach", więc zakładam, że chce on również obsługiwać nie wypukłe wielokąty. –

Fair point Martin. Zakładałem, że są to wypukłe kształty i sugerują ten algorytm jako punkt wyjścia do znalezienia dwóch skrzyżowań. –

Jak o:

Odbiór lewy-najbardziej punkt dwóch kształtach. Nazwij ten Kształt A i nadaj mu aktualny kształt.
Nawij zgodnie z ruchem wskazówek zegara wzdłuż bieżącego kształtu do następnego punktu i sprawdź, czy jedna lub więcej linii przecinają się.
- Jeśli którekolwiek linie przecinają się, znajdź pierwszy punkt przecięcia i dodaj go do nowego kształtu. Przełącz na nawijanie wzdłuż innego kształtu.
- Jeśli żadne linie nie przecinają się, przejdź do następnego punktu w kształcie A i dodaj go jako punkt w nowym kształcie. Kontynuuj nawijanie wzdłuż bieżącego kształtu.
Powtórz Krok 2.

myślę, że jeśli wciąż uzwojenie wzdłuż dowolny kształt jest prąd, patrząc na skrzyżowaniach, które należy zrobić, co chcesz. Myślę, że to powinno również poradzić sobie z wklęsłymi kształtami ...

Jestem pewna, że istnieje wiele optymalizacji, które możesz dodać, gdy tylko zaczniesz działać.

Źródło

2010-01-26 17:22:13