Kolizja koła z łukiem

Witam. Męczę się z następującym problemem:

Mam koło i okrąg o identycznym promieniu R. Bardzo łatwo mogę sprawdzić kolizje tych obiektów
na podstawie odległości między środkami. Gorzej jeśli z okręgu wytnę sobie łuk. Taki łuk może mieć długość
od 0 (punkt) do pełnego okręgu.

Jak mogę szybko wykryć kolizje między tymi obiektami ?

Mam środki i mam promień.

Chodzi o koło (a nie okrąg) i łuk (a nie wycinek koła).

Na oko potrzebne są 2 kryteria:

1. Klasyczne kryterium które opisałeś, czyli sprawdzenie czy cały okrąg przeciąłby nasze koło
2. Dodatkowe kryterium które sprawdza czy łuk który mamy przecina koło: trzeba wyznaczyć równania 2 prostych pomiędzy środkiem okręgu a krańcami łuku i sprawdzić czy któraś z tych prostych przecina koło (czyli czy odległość środa koła od prostej jest <= promieniowi koła)

Przecinanie się tych prostych z kołem może oznaczać zupełnie nic. Te same proste mogą obydwie przecinać koło i łuk będzie przecinał koło a potem odwracamy łuk i proste dalej przecinają koło a łuk już nie przecina.

To by się dało załatwić przez sprawdzenie czy środek okręgu i koniec łuku są po tej samej stronie prostej prostopadłej to prostej która daje nam punkt przecięcia.
Ale w sumie zastanowiło mnie teraz -> nie da sie zwyczajnie rozwiązać równania 2 okręgów z dodatkowymi ograniczeniami wynikającymi z tego że bierzesz tylko wycinek koła?

Shalom napisał(a):

Na oko potrzebne są 2 kryteria:

1. Klasyczne kryterium które opisałeś, czyli sprawdzenie czy cały okrąg przeciąłby nasze koło
2. Dodatkowe kryterium które sprawdza czy łuk który mamy przecina koło: trzeba wyznaczyć równania 2 prostych pomiędzy środkiem okręgu a krańcami łuku i sprawdzić czy któraś z tych prostych przecina koło (czyli czy odległość środa koła od prostej jest <= promieniowi koła)

Może zastąpmy drugie kryterium na:
Czy przecinają się odcinki pomiędzy środkami (jeden odcinek) oraz pomiędzy krawędziami luku (drugi odcinek) - zły pomysł, czytaj komentarz.

_13th_Dragon napisał(a):

Shalom napisał(a):

Na oko potrzebne są 2 kryteria:
2. Dodatkowe kryterium które sprawdza czy łuk który mamy przecina koło: trzeba wyznaczyć równania 2 prostych pomiędzy środkiem okręgu a krańcami łuku i sprawdzić czy któraś z tych prostych przecina koło (czyli czy odległość środa koła od prostej jest <= promieniowi koła)

Może zastąpmy drugie kryterium na:
Czy przecinają się odcinki pomiędzy środkami (jeden odcinek) oraz pomiędzy krawędziami luku (drugi odcinek)

Co to jest krawędź łuku ? Dla mnie krawędź łuku to sam łuk. Jeśli chodzi natomiast o połączenie końców łuku to NIE. Jest 9129487926141 przypadków kiedy to nie pasuje.

Sprawdzenie czy punkt należy do koła jest banalne - wystarczy tylko teraz sprawdzić czy wszystkie punkty łuku zawierają się w kole - tutaj jest ten problem, że nie możesz poprzestać tylko na granicznych punktach łuku bo gdy promień łuku będzie mniejszy od promienia koła oba końce łuku mogą być w środku koła a część wewnętrzna łuku poza nim.

//dopisane
Nie trzeba wszystkich tylko oba skrajne punkty łuku oraz trzeci punkt dwusiecznej łuku

tak jak na rysunku musisz sprawdzić czy wszystkie czerwone pkt. są w środku koła.

//dopisane 2 raz xD
Nie no niestety trzeba sprawdzić wszystkie punkty, albo rozbić to na różne przypadki

Potestowałem kolejne pomysły i dalej nic. Zawsze jest jakiś przypadek kiedy działa źle. A znowu rozbijać tego na 10 przypadków nie chce bo to jest mnóstwo przeliczania niepotrzebnych rzeczy.

Może tak:

1. obliczamy punkty przecięcia dwóch kół
2. dla każdego (z max dwóch) sprawdzamy czy ten punkt przecięcia leży po innej stronie cięciwy niż środek kola na którym leży luk. (Po innej -> mamy przecięcie)

Po której stronie jest punkt:
Prosta przez dwa punkty A(Ax,Ay) - B(Bx,By)
Sprawdzamy czy punkty P(Px,Py) oraz C(Cx,Cy) są po różnych stronach prostej

if(((Ax-Cx)*(By-Cy)-(Ay-Cy)*(Bx-Cx))<0)==((Ax-Px)*(By-Py)-(Ay-Py)*(Bx-Px))>0)) // jeżeli po innej stronie

Ewentualnie trzeba jeszcze rozpatrzyć kiedy A==C lub B==C

Nie do końca podoba mi się rozwiązanie z kątami bo korzystam z funkcji ArcCos które nie są chyba za szybkie i nie wiem jak z dokładnością. Ale może inne rozwiązania są jeszcze gorsze.

W każdym razie na razie tak to zrobiłem i u mnie nawet chyba całość wyszła prościej niż wynikało z opisów. Środek łuku traktuje jako punkt 0,0 i liczę 4 kąty pomiędzy osią X a 4 punktami (2 końce łuku, 2 przecięcia). Jeśli Y danego punktu jest mniejszy niż 0 to robię 'kąt = 360 - kąt' żeby otrzymać pełny zakres kąta. A potem mam dwa przypadki: kąt "końcowego" punktu łuku jest większy od kąta "początkowego" - wtedy którykolwiek z kątów do przecięć musi wypaść pomiędzy tymi kątami, lub kąt "końcowy" jest mniejszy od "początkowego" - wtedy któryś z kątów do przecięć musi miec wartość 0 do kąta "końcowego" lub od kąta "początkowego" do 360 (to ten szczególny przypadek przejścia przez kąt 360). Jest jeszcze jeden przypadek kiedy cały łuk znajduje się wewnątrz koła. Ten przypadek należy wykryć czy odległość środka koła od któregoś z końców łuku nie jest mniejsza lub równa od promienia. Pewnie rysunek byłby bardziej zrozumiały...

Wyznaczasz przecięcie dwóch okręgów, masz dwa punkty (to na pewno masz zrobione), teraz pozostaje zrobić test czy jeden z tych dwóch punktów znajduje się w granicach łuku, a to można sprawdzać (A,B początek i koniec łuku, O środek łuku X badany punkt:
Jeśli (nie więcej niż pełny półokrąg) to muszą być spełnione warunki:

W przeciwnym wypadku (więcej niż pełny półokrąg) sprawdzamy warunek:

Druga metoda faktycznie też działa (PRAWIE). Czy waszym zdaniem taki przypadek powinien również działać ?

Przecież nie ma kolizji.

Nie ma tu nic do roboty.

Obliczasz punkty przecięcia okręgów.
Jeśli nie ma to end.

Gdy jest jakiś punkt przecięcia, wtedy sprawdzasz dodatkowo, czy leży na tym łuku... no i to wszystko.
Łuk reprezentujemy w postaci: punktu środkowy, oraz dwa kąty: start i end, od 0 do 2pi każdy.

@etet100 Jeśli odległość między środkami < |r1-r2| to jedno koło zawiera się w drugim, jeśli jest >= to znaczy że musisz sprawdzić czy okręgi się przecinają - czy odległość między środkami jest mniejsza od sumy promieni. Jeśli nie jest to nie ma przecięć. Jeśli jest to liczysz przecięcia a potem sprawdzasz kąty.

Mamy 3 punkty łuku, sprawdzamy ile z nich jest wewnątrz okręgu: jak 3 to koliduje z kołem, jak jeden lub dwa to z kołem i okręgiem, a jak żaden to z niczym.

Wyznaczasz punkty X1, X2 przeciecia się okręgu z kołem. Przynajmniej jeden z tych punktów musi należeć do łuku okręgu. Za punkty A i B przyjmijmy punkty krańcowe okręgu.
Warunek: Bx >= X1x >= Ax, By >= X1y >= Ay. To samo z punktem X2. Warunki nie zadziałają, kiedy całość łuku należy do koła. Bardzo łatwo to sprawdzic - sprawdzasz, czy jeden z punktow kracowych leży wewnetrz koła.

Takie proste zadanie wydawać by się mogło a tyle problemów :P w sam raz na jakąś olimpiadę.

To tylko opłakane skutki drastycznie niskiego poziomu nauczania - zero wiedzy z podstaw matematyki.

Przed wojną to był poziom ! Nie to co teraz

Na pewno był wyższy, bo musieli wszystko samodzielnie obliczać.

Moja koncepcja.

1. Jeśli co najmniej jeden z punktów granicznych łuku (nie wiem jak to się fachowo nazywa, chodzi mi o jego 'zakończenia') zawiera się w kole to kolizja występuje.
2. Przyjmujemy łuk o promieniu r jako koło o promienu r i sprawdzamy, czy przecina sie z drugim.
3. Jeśli nie, to kolizji nie ma.
4. Jeśli tak to wyliczamy punkty przecięcia się tych kół.
5. Wyliczamy kąt od środka łuku do tych punktów i jeśli co najmniej jeden z tych kątów zawiera się w kącie łuku to kolizja występuje.

teraz jak tak patrze to coś podobnego chyba gdfhjkl napisał.