Przecięcie okręgu z algorytmem linii przeciągnięcia

15

Niestety nadal nie jestem tak silny w zrozumieniu algorytmu linii przeciągania . Wszystkie artykuły i podręczniki na ten temat są już przeczytane, jednak ich zrozumienie jest wciąż bardzo odległe. Aby to wyjaśnić, próbuję rozwiązać jak najwięcej ćwiczeń. Ale naprawdę interesujące i ważne zadania wciąż stanowią dla mnie wyzwanie.

Poniższe ćwiczenie znalazłem w notatkach z wykładu przecięcia segmentów liniowych przez wszechmocnego Jeffa Ericksona.

Ćwiczenie 2. Opisz i przeanalizuj algorytm linii prostej, aby określić, biorąc pod uwagę okręgów na płaszczyźnie, czy dowolne dwa się przecinają, w czasie . Każde koło jest określone przez jego środek i promień, więc wejście składa się z trzech tablic i . Uważaj, aby poprawnie zaimplementować operacje podstawowe niskiego poziomu. $n$ $O(n \log n)$ $X[1.. n], Y [1.. n]$ $R[1.. n]$

Spróbujmy uczynić skomplikowaną rzecz łatwiejszą. Co wiemy o przecięciu kół? Jaki analog można znaleźć przy przecięciu linii. Dwie linie mogą się przecinać, jeśli sąsiadują, która właściwość powinna mieć dwa kółka, aby się przecinać? Niech będzie odległością między środkami kół, i środkami kół. Rozważ kilka przypadków: $d$ $r_{0}$ $r_{1}$

Przypadek 1: Jeśli nie ma rozwiązań, koła są osobne. $d > r_{0} + r_{1}$
Przypadek 2: Jeśli wtedy nie ma rozwiązań, ponieważ jedno koło jest zawarte w drugim. $d < |r_{0} - r_{1}|$
Przypadek 3: Jeżeli i wówczas koła są zbieżne i istnieje nieskończona liczba rozwiązań. $d = 0$ $r_{0} = r_{1}$

Wygląda więc na to, że warunki skrzyżowania są gotowe, oczywiście mogą to być złe warunki. Proszę poprawić, jeśli tak jest.

Algorytm. Teraz musimy znaleźć coś wspólnego między dwoma przecinającymi się okręgami. W przypadku przecięcia linii analogowej do linii musimy wprowadzić warunek wstawiania i usuwać warunek do kolejki zdarzeń. Powiedzmy, że punktem zdarzenia jest współrzędna x pierwszego i ostatniego punktu, którego dotyka pionowa linia przeciągnięcia. W pierwszym punkcie wstawiamy okrąg do statusu i sprawdzamy przecięcie (3 przypadki do sprawdzenia są wspomniane powyżej) z najbliższymi okręgami, w ostatnim punkcie usuwamy koło ze statusu .

Wygląda na to, że wystarczy dla algorytmu linii przeciągnięcia. Jeśli coś jest nie tak lub może być coś, co należy zrobić inaczej, podziel się z nami swoimi przemyśleniami.

Dodatek :

Wstawiam okrąg, gdy pionowa linia przeciągnięcia dotyka koła po raz pierwszy, i usuwam okrąg ze stanu, gdy linia przeciągnięcia dotyka go po raz ostatni. Sprawdzanie skrzyżowania należy wykonać dla najbliższego poprzedniego okręgu. Gdybyśmy dodali krąg do statusu i istniał już inny krąg, który dodaliśmy wcześniej, i nadal tam był, dlatego przepadający krąg nie został „zamknięty”, więc może istnieć skrzyżowanie.

algorithms computational-geometry

— com
źródło

4

wszechmocny [potrzebne źródło]

— JeffE

@com, co rozumiesz przez „najbliższy poprzedni krąg”?

— Joe

1

Zakładam, że statusutrzymuje kółka przecinające linię przeciągnięcia? Załóżmy, że masz obecnie 100 kręgów status, przetwarzasz zdarzenie wstawiania i wstawiasz 101. krąg. Ile kręgów porównujesz, aby sprawdzić skrzyżowanie? Jak wybrać kręgi do porównania?

— Joe

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

y

$y$

5

Jesteś zdecydowanie na dobrej drodze. Główne pytanie brzmi: kiedy wstawiasz koło, które inne kręgi sprawdzasz pod kątem przecięcia? Jak przeprowadzasz tę kontrolę?

W przypadku przecięcia segmentu linii segmenty linii na dowolnej współrzędnej x są całkowicie uporządkowane. (Możesz je wymienić od najniższej do najwyższej współrzędnej Y). W ten sposób możesz utrzymywać segmenty linii w drzewie wyszukiwania binarnego, a kiedy dodajesz nowy segment, musisz tylko dowiedzieć się, gdzie należy on do drzewa wyszukiwania binarnego, i sprawdzić jego sąsiadów pod kątem zdarzeń przecięcia.

W przypadku kręgów nie jest od razu jasne, które kręgi sprawdzić. Jeśli twoja odpowiedź brzmi „wszystkie”, algorytm wymaga trochę pracy.

Czy potrafisz znaleźć sposób na reprezentowanie kręgów, aby były one całkowicie uporządkowane, podobnie jak segmenty linii?

Spróbuj przedstawić kręgi jako dwa półokręgi. Każde zdarzenie wstawiania to tak naprawdę dwa zdarzenia: wstaw górną połowę i wstaw dolną połowę.

— Joe
źródło

Niestety nie mam pojęcia o półkolach, być może uważasz półkole za minimalną jednostkę okręgu, którą można przecinać (3 przypadki przecięcia: przecięcie jest na górnym półkolu, na dole lub na obu z nich). Na początku wszystkie koła są uporządkowane według współrzędnej x ich lewej i prawej granicy. Nie powinniśmy więc uważać x koordynatora w statusie , ponieważ wszystkie kręgi są już w kolejności współrzędnych x. Dlatego bardziej logiczne wydaje się rozważenie współrzędnej y środka (półkola) lub dowolnej kombinacji y i promieni. Twoja opinia?

— com

@com Potrzebujesz punktu środkowego i promienia, aby ustalić, czy dwa okręgi przecinają się, tak jak w przypadku własnych kontroli przecięcia. Tylko współrzędna y i sam promień nie określają w pełni granicy okręgu. Wydaje się, że jest coś fundamentalnego w algorytmach linii wymiatania, którego nie rozumiesz, ale trudno mi powiedzieć, co to jest.

— Joe

0

Mógłbym pomyśleć o takim podejściu analogicznym do przemiatania Bentleya Ottmanna, który działa w czasie O ((n + k) logn).

Mógłbym zredukować problem przecięcia okręgu do przecięcia odcinka linii. Rozważę średnicę pionową równoległą do osi Y dla każdego z okręgów. Algorytm wykorzystuje poziomą linię, która przesuwa płaszczyznę od dołu do góry.

Teraz mamy Górny punkt końcowy, dolny punkt końcowy dla każdego z okręgów. Musimy również zmodyfikować predykat Przecięcie, aby powiedzieć, że dwa odcinki przecinają się wtedy i tylko wtedy, gdy linia przeciągnięcia przecina oba koła w jednym punkcie.

Ponieważ problem przecięcia linii można rozwiązać w czasie O ((n + k) logn), to samo ograniczenie obowiązuje również dla przecięcia okręgu.

Jestem przekonany, że to zadziała, ale jeśli moglibyście wskazać jakikolwiek przypadek, że ogólnie nie będzie to możliwe, dajcie mi znać.

— TheGT
źródło