Skąd mam wiedzieć, czy okrąg i prostokąt przecinają się w przestrzeni euklidesowej 2D? (tj. klasyczna geometria 2D)
192
Skąd mam wiedzieć, czy okrąg i prostokąt przecinają się w przestrzeni euklidesowej 2D? (tj. klasyczna geometria 2D)
Odpowiedzi:
Istnieją tylko dwa przypadki, w których okrąg przecina się z prostokątem:
Zauważ, że nie wymaga to, aby prostokąt był równoległy do osi.
(Można to zobaczyć na jeden sposób: jeśli żadna z krawędzi nie ma punktu na okręgu (jeśli wszystkie krawędzie są całkowicie „na zewnątrz” koła), wówczas jedynym sposobem, w jaki okrąg może przecinać wielokąt, jest całkowite jego położenie wewnątrz wielokąt.)
Z tego wglądu, coś jak poniżej będzie działać, gdzie okrąg ma środek
P
i promieńR
, a prostokąt ma wierzchołkiA
,B
,C
,D
w tej kolejności (nie kompletny kod):Jeśli piszesz jakąkolwiek geometrię, prawdopodobnie masz już w bibliotece powyższe funkcje. W przeciwnym razie
pointInRectangle()
można je wdrożyć na kilka sposobów; dowolny ogólny punkt w metodach wielokąta będzie działał, ale dla prostokąta możesz po prostu sprawdzić, czy to działa:I
intersectCircle()
jest również łatwy do wdrożenia: jednym ze sposobów byłoby sprawdzenie, czy stopa prostopadłejP
do linii jest wystarczająco blisko i między punktami końcowymi, a w przeciwnym razie sprawdź punkty końcowe.Fajne jest to, że ten sam pomysł działa nie tylko dla prostokątów, ale także na przecięciu koła z dowolnym prostym wielokątem - nawet nie musi być wypukły!
źródło
Oto jak bym to zrobił:
Oto jak to działa:
Pierwsza para linii oblicza bezwzględne wartości różnicy xiy między środkiem okręgu a środkiem prostokąta. To powoduje, że cztery ćwiartki dzielą się na jeden, dzięki czemu obliczenia nie muszą być wykonywane cztery razy. Obraz pokazuje obszar, w którym musi teraz leżeć środek okręgu. Zauważ, że pokazany jest tylko pojedynczy kwadrant. Prostokąt jest szarym obszarem, a czerwona ramka przedstawia obszar krytyczny, który znajduje się dokładnie jeden promień od krawędzi prostokąta. Środek koła musi znajdować się w obrębie tej czerwonej granicy, aby nastąpiło przecięcie.
Druga para linii eliminuje łatwe przypadki, w których okrąg jest wystarczająco daleko od prostokąta (w obu kierunkach), aby niemożliwe było przecięcie. Odpowiada to zielonemu obszarowi na obrazie.
Trzecia para linii obsługuje proste przypadki, w których okrąg jest wystarczająco blisko prostokąta (w dowolnym kierunku), aby zagwarantować przecięcie. Odpowiada to pomarańczowym i szarym sekcjom na obrazie. Zauważ, że ten krok musi być wykonany po kroku 2, aby logika miała sens.
Pozostałe linie obliczają trudny przypadek, w którym okrąg może przecinać róg prostokąta. Aby rozwiązać, oblicz odległość od środka koła i rogu, a następnie sprawdź, czy odległość nie jest większa niż promień koła. To obliczenie zwraca wartość false dla wszystkich kół, których środek znajduje się w obszarze zacieniowanym na czerwono, i zwraca wartość true dla wszystkich kół, których środek znajduje się w obszarze zacieniowanym na biało.
źródło
;)
circleDistance_x = abs(circle.x - (rect.x-rect.w/2)); circleDistance_y = abs(circle.y - (rect.y-rect.h/2));
Oto kolejne rozwiązanie, które jest dość proste do wdrożenia (i również dość szybkie). Złapie wszystkie przecięcia, w tym gdy kula całkowicie wejdzie w prostokąt.
Z każdą przyzwoitą biblioteką matematyczną, którą można skrócić do 3 lub 4 linii.
źródło
twoja kula i prostokąt przecinają IIF
odległość między środkiem okręgu a jednym wierzchołkiem twojej odbytnicy jest mniejsza niż promień twojej kuli
LUB
odległość między środkiem okręgu a jedną krawędzią twojej odbytnicy jest mniejsza niż promień twojej kuli ( [ odległość punkt-linia ])
LUB
środek okręgu znajduje się wewnątrz prostej odległości
punkt-punkt:
odległość punkt-linia:
środek okręgu wewnątrz
prostokąta : podejdź do osi oddzielającej: jeśli istnieje rzut na linię oddzielającą prostokąt od punktu, nie przecinają się
rzutujesz punkt na linie równoległe do boków twojej odbytnicy i możesz łatwo ustalić, czy się przecinają. jeśli nie przecinają się na wszystkich 4 rzutach, nie mogą się przecinać (punkt i prostokąt).
potrzebujesz tylko produktu wewnętrznego (x = [x1, x2], y = [y1, y2], x * y = x1 * y1 + x2 * y2)
Twój test wyglądałby tak:
nie zakłada to prostokąta wyrównanego do osi i można go łatwo rozszerzyć do testowania przecięć między zestawami wypukłymi.
źródło
To najszybsze rozwiązanie:
Zwróć uwagę na kolejność wykonywania, a połowa szerokości / wysokości jest wstępnie obliczona. Również wykonywanie kwadratu odbywa się „ręcznie”, aby zapisać niektóre cykle zegara.
źródło
Najprostsze rozwiązanie, jakie wymyśliłem, jest dość proste.
Działa poprzez znalezienie punktu w prostokącie najbliższym okręgu, a następnie porównanie odległości.
Możesz to wszystko zrobić za pomocą kilku operacji, a nawet uniknąć funkcji sqrt.
I to wszystko! Powyższe rozwiązanie zakłada początek w lewym górnym rogu świata z osią x skierowaną w dół.
Jeśli chcesz rozwiązać kolizje między ruchomym okręgiem a prostokątem, jest to o wiele bardziej skomplikowane i omówione w innej mojej odpowiedzi.
źródło
W rzeczywistości jest to o wiele prostsze. Potrzebujesz tylko dwóch rzeczy.
Najpierw musisz znaleźć cztery ortogonalne odległości od środka okręgu do każdej linii prostokąta. Wówczas twój okrąg nie przecina prostokąta, jeśli trzy z nich są większe niż promień okręgu.
Po drugie, musisz znaleźć odległość między środkiem okręgu a środkiem prostokąta, wtedy koło nie będzie w środku prostokąta, jeśli odległość będzie większa niż połowa długości przekątnej prostokąta.
Powodzenia!
źródło
Oto mój kod C do rozwiązywania kolizji między kulą a nieosiowym wyrównanym polem. Opiera się na kilku moich własnych procedurach bibliotecznych, ale dla niektórych może się przydać. Używam go w grze i działa idealnie.
źródło
Aby zwizualizować, weź klawiaturę numeryczną klawiatury. Jeśli klawisz „5” reprezentuje prostokąt, wszystkie klawisze 1-9 reprezentują 9 kwadrantów przestrzeni podzielonych przez linie tworzące prostokąt (gdzie 5 to wnętrze).
1) Jeśli środek okręgu znajduje się w ćwiartce 5 (tj. Wewnątrz prostokąta), wówczas dwa kształty przecinają się.
Poza tym istnieją dwa możliwe przypadki: a) Okrąg przecina się z dwiema lub więcej sąsiadującymi krawędziami prostokąta. b) Okrąg przecina się z jedną krawędzią prostokąta.
Pierwszy przypadek jest prosty. Jeśli okrąg przecina się z dwiema sąsiadującymi krawędziami prostokąta, musi zawierać róg łączący te dwie krawędzie. (To lub jego środek leży w kwadrancie 5, który już omówiliśmy. Zauważ również, że przypadek, w którym koło przecina się tylko z dwiema przeciwległymi krawędziami prostokąta, jest również objęty.)
2) Jeśli którykolwiek z narożników A, B, C, D prostokąta leży wewnątrz koła, wówczas dwa kształty przecinają się.
Drugi przypadek jest trudniejszy. Należy zauważyć, że może się to zdarzyć tylko wtedy, gdy środek koła znajduje się w jednej z ćwiartek 2, 4, 6 lub 8. (W rzeczywistości, jeśli środek znajduje się w którejkolwiek z ćwiartek 1, 3, 7, 8 odpowiedni róg będzie najbliżej tego punktu).
Teraz mamy przypadek, że środek koła znajduje się w jednej z ćwiartek „krawędzi” i przecina on tylko odpowiednią krawędź. Następnie punkt na krawędzi, który jest najbliżej środka koła, musi leżeć wewnątrz koła.
3) Dla każdej linii AB, BC, CD, DA skonstruuj linie prostopadłe p (AB, P), p (BC, P), p (CD, P), p (DA, P) przez środek okręgu P. Dla każdą linię prostopadłą, jeśli przecięcie z oryginalną krawędzią leży wewnątrz koła, wówczas dwa kształty przecinają się.
Istnieje skrót do tego ostatniego kroku. Jeśli środek okręgu znajduje się w ćwiartce 8, a krawędź AB jest górną krawędzią, punkt przecięcia będzie miał współrzędną y A i B oraz współrzędną x środka P.
Możesz zbudować cztery przecięcia linii i sprawdzić, czy leżą na odpowiadających im krawędziach, lub dowiedzieć się, w którym kwadrancie P jest, i sprawdzić odpowiednie przecięcie. Oba powinny uprościć to samo równanie boolowskie. Uważaj, aby powyższy krok 2 nie wykluczył, że P znajduje się w jednej z „narożnych” ćwiartek; po prostu szukał skrzyżowania.
Edycja: Jak się okazuje, przeoczyłem prosty fakt, że nr 2 jest podtekstem nr 3 powyżej. W końcu rogi też są punktami na krawędziach. Świetne wyjaśnienie znajduje się w odpowiedzi @ ShreevatsaR poniżej. W międzyczasie zapomnij o punkcie 2 powyżej, chyba że chcesz szybkiego, ale zbędnego czeku.
źródło
Ta funkcja wykrywa kolizje (przecięcia) między okręgiem a prostokątem. W swojej odpowiedzi działa jak metoda e.James, ale ta wykrywa kolizje dla wszystkich kątów prostokąta (nie tylko w prawym górnym rogu).
UWAGA:
aRect.origin.x i aRect.origin.y są współrzędnymi lewego dolnego kąta prostokąta!
aCircle.x i aCircle.y są współrzędnymi Circle Center!
źródło
Mam metodę, która w razie potrzeby pozwala uniknąć drogich pitagoras. podczas ograniczania prostokątów i koła nie przecinają się.
I będzie działać również w przypadku euklidesa:
dLat=(lat-circleY); dLon=(lon-circleX); normed=dLat*dLat+dLon*dLon
. Oczywiście, jeśli użyjesz tej metody normDist, musisz utworzyćnormedDist = dist*dist;
dla kołaZobacz pełną bbox i Okrągła kod mojego GraphHopper projektu.
źródło
Stworzyłem zajęcia do pracy z kształtami, które mam nadzieję
źródło
Oto zmodyfikowany kod działający w 100%:
Bassam Alugili
źródło
Oto szybki test jednowierszowy:
Jest to przypadek wyrównany do osi, w którym
rect_halves
wektor dodatni wskazuje od środka prostokąta do rogu. Wyrażenie w środkulength()
jest wektorem delta odcenter
najbliższego punktu prostokąta. Działa to w dowolnym wymiarze.źródło
Jest wydajny, ponieważ:
źródło
działało dla mnie (działa tylko wtedy, gdy kąt prostokąta wynosi 180)
źródło
Poprawiając nieco odpowiedź e.Jamesa:
Odejmuje to
rect.w / 2
irect.h / 2
raz zamiast do trzech razy.źródło
Dla tych, którzy muszą obliczyć kolizję koło / prostokąt we współrzędnych geograficznych z SQL,
jest to moja implementacja w oracle 11 algorytmu sugerowanego przez e.James .
Na wejściu wymaga współrzędnych okręgu, promienia okręgu w km i dwóch współrzędnych wierzchołka prostokąta:
źródło
Działa, właśnie wymyśliłem to tydzień temu i dopiero teraz przetestowałem.
źródło
źródło
Zakładając, że masz cztery krawędzie prostokąta, sprawdź odległość od krawędzi do środka koła, jeśli jest mniejsza niż promień, wówczas kształty się przecinają.
źródło
Jeśli prostokąt przecina się z okręgiem, jeden lub więcej punktów narożnych prostokąta powinno znajdować się wewnątrz koła. Załóżmy, że cztery punkty prostokąta to A, B, C, D. przynajmniej jeden z nich powinien przecinać okrąg. więc jeśli odległość od jednego punktu do środka koła jest mniejsza niż promień koła, powinna przecinać się koło. Aby uzyskać odległość, możesz użyć twierdzenia Pitagorasa,
Ta technika ma pewne ograniczenia. Ale będzie działać lepiej dla twórców gier. szczególnie wykrywanie kolizji
To dobra aktualizacja do algorytmu Arvo
źródło