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?
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
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 .
źródło
Oto co robię.
źródło