Mam wielokąt (czasem wypukły, ale często wklęsły) i kilka kół o różnych promieniach. Jak mogę się dowiedzieć, czy okrąg przecina się / zachodzi na wielokąt?
Mógłbym podzielić mój wklęsły wielokąt na wypukłe kawałki. Czy to pomogłoby?
Jak sprawdzić, czy krzyż i wielokąt wklęsły przecinają się?
Odpowiedzi:
są dwa przypadki tego problemu. Pierwszy to skrzyżowanie, a drugi zachodzi na siebie (zawiera).
Po pierwsze (przecięcie / wielokąt wewnątrz koła):
Znajdź najbliższy punkt na każdej krawędzi wielokąta od środka okręgu. Jeśli jakakolwiek odległość między najbliższym punktem do środka jest mniejsza niż promień, oznacza to, że przecięcie lub zakładka się pokrywają.
Po drugie (okrąg jest cały w wielokącie): Strzelaj promieniem od środka okręgu w prawo (lub w lewo / w górę / w dół) i policz przecięcia promienia / segmentu (krawędzie wielokąta). Jeśli liczba przecięć jest parzysta, okrąg jest poza wielokątem. Jeśli to dziwny krąg, jest w środku.
Podzielę się picter z wykładu dla tej sprawy:
I zajmij się pojedynczymi przypadkami.
Mam nadzieję, że to pomoże.
edycja: Myślę, że dodawanie napisów do zdjęcia jest sprawiedliwe. Autorem jest Petr Felkel, adiunkt na Politechnice Czeskiej w Pradze
Nie sądzę, że to zadziała, po prostu „wystrzeliwując” promień w prawo. Może źle odczytałem twoje podejście, ale z tego, co zrozumiałem, zakończy się niepowodzeniem z konfiguracją przedstawioną tutaj: imgur.com/Whg2u
—
bummzack
Tak, ale opisano to w pierwszym przypadku. Promień strzału rozwiąże tylko okrąg zawierający wielokąt (drugi przypadek w moim opisie). Musisz przetestować oba przypadki. Jest szybki, łatwy do wdrożenia i nie wymaga pamięci.
—
Notabene
Przykro mi, że pomyliłem „edge” z „vertex” i dlatego źle zinterpretowałem twój pierwszy czek. Przy prawidłowym odczycie działa :)
—
bummzack,
Pierwszym krokiem, jak się domyślacie, jest podzielenie wklęsłego wielokąta na wiele wypukłych. Powodem tego jest to, że użyjesz twierdzenia o osi oddzielającej , które działa tylko na wypukłych wielokątach.
SAT per se działa tylko na dwóch wypukłych wielokątach. „Oś oddzielająca” w nazwie odnosi się do osi prostopadłych do krawędzi wielokąta. Kręgi mają niestety nieskończoną liczbę. Okazuje się jednak, że jest dość łatwy sposób, aby dowiedzieć się, które z tych osi są istotne, patrząc na to, które wystają na zewnątrz, aby przeciąć wierzchołki wielokąta.
Zamiast omawiać tutaj cały algorytm, Metanet Software (twórcy N / N +) ma dobry samouczek na temat wykrywania kolizji za pomocą SAT , którego trzecia sekcja obejmuje SAT, gdy jeden z obiektów jest okręgiem .
Czy masz odniesienie do dzielenia wielokąta wklęsłego na wielokąty wypukłe? Podany link SAT nie wspomina nic takiego.
—
ehsanul
W rzeczywistości jest to bardzo złożony problem w zależności od geometrii wielokąta, ale robią to wszystkie silniki 3D, ponieważ sprzęt może generować tylko czterokąty i trójkąty współpłaszczyznowe, a nie wielokąty.
—
SplinterReality
@ehsanul: en.wikipedia.org/wiki/Polygon_triangulation opisuje kilka popularnych podejść.
Oto co robię.
- Użyj testu linii poziomej, aby sprawdzić, czy środek okręgu znajduje się wewnątrz wielokąta. Jeśli tak, to przecinają się.
- Jeśli nie, sprawdź następujący przypadek. Dla każdej strony wielokąta
- Znajdź nachylenie strony wielokąta
- Oblicz nachylenie prostopadłe
- (UWAŻNIE PRZECZYTAJ) Znajdź przecięcie między linią ze spadkiem strony wielokąta przecinającym się z dowolnym wierzchołkiem tworzącym bok, a linią nachylenia prostopadłą do linii boku, która przecina środek okręgu.
- Jeśli ustalony punkt przecięcia leży wewnątrz koła, oznacza to, że koło w pewnym punkcie przecina dany bok, a zatem przecina wielokąt
- Na koniec, jeśli nic więcej nie jest rozstrzygające, sprawdź, czy jakieś wierzchołki wielokąta leżą wewnątrz koła (ze względu na poprzednie testy, musisz sprawdzić tylko raz). Jeśli tak, przecinają się. Jeśli nie, możesz jednoznacznie powiedzieć, że nie.