Algorytm - Część wspólna kół

[Platyna]

Ma ktoś może jakiś pomysł na algorytm wyznaczający część wspólną n kół? Może zwracać na przykład otoczkę wypukłą złożoną z punktów przecięć okręgów. Chociaż mi wystarczy by zwróciło dowolny punkt z tej części wspólnej. Satysfakcjonująca mnie złożoność to coś koło O(n*log n), chociaż fajnie by było jakby się znalazło O(n), ale w sumie nawet O(n*sqrt(n)) mnie zadowoli. Byle nie kwadratówka, bo takową już mam. I to nawet znacznie zoptymalizowaną.

[Dawidds]

http://www.google.com/search?sourceid=chro...le+intersection

Jest co czytać.

[Platyna]

W razie jakbyś nie zauważył to tam są tylko algorytmy znajdujące punkty przecięcia. Okręgu z okręgiem, okręgu z prostą, z prostokątem...

Znaleźć punkty przecięcia dwóch okręgów to ja umiem, to trudne nie jest. Ale jak mam tych okręgów n? Nie mogę przecież próbować każdego z każdym przecinać i z tego coś stworzyć. Każde 2 okręgi stworzą mi 2 punkty przecięcia. to daje nam 2n^2 punktów. Poza tym wątpię by mając te punkty mógłbym coś fajnego z nimi zrobić.

 

EDIT:

To trzeba jakoś w taki sposób by mając część wspólną kół od 1 do x móc potrafić znaleźć od 1 do x+1. Czyli aktualną część wspólną przecinać z kolejnym okręgiem.

Ale muszę przelecieć po wszystkich punktach aktualnej części wspólnej by wiedzieć z jakimi 2 okręgami mam przecinać ten nowy.

 

EDIT2:

Zastanawiałem się też nad tym by zrezygnować trochę z precyzji. Zrobić sobie takie wielkie piksele i dla każdego pamiętać ile okręgów na nie nachodzi. I później im bardziej ograniczam płaszczyznę tym te pikselki robię coraz mniejsze. Ale to raczej też dobre rozwiązanie nie jest.

[Will]

Spróbowałbym drzewo czwórkowe.

[Platyna]

Ale do tego pomysłu z pikselkami?

Jakoś konkretniej jak byś chciał je zastosować?

 

Zapomniałem dodać, że wszystkie okręgi mają taki sam promień. Może to jakoś ułatwi?

[Will]

W sumie to można by do tego podciągnąć. Dzielić całość while(in current block are n circles) ustalić jakąś min wielkość, która można traktować jako jeden piksel po całym przejściu dostajesz zbiór takich regionów. Można też zostawić większe bloczki i wyliczać przybliżoną część wspólną w danym bloczku. Na pewno lepsze rozwiązanie niż sprawdzanie każdy z każdym.

[Platyna]

No dobra, ale jeżeli w taki duży kwadrat przecina n okręgów to dziele go na 4. I teraz każdy z tych 4 musiał bym ponownie sprawdzić z każdym z n okręgów.

Jeszcze jak do tego dochodzi fakt, że potrzebuje precyzji do 0.000001 to te kwadraciki będą maciupkie i będzie ich niemało.

[Will]

Sprawdzenie czy okrąg jest w kwadracie to minimalny narzut. Zawsze możesz ograniczyć wielkość bloczków i obliczać część wspólną w danym bloczku a potem dodać wszystkie wyniki z każdego sektora. Napisz sobie prosty prototyp drzewo czwórkowe jest proste w implementacji więc szybko sobie sprawdzisz jak to się sprawuje.

[Platyna]

Przykro mi, ale ja nadal nie rozumiem twojego pomysłu.

Mam sobie kwadracik o którym wiem, że każdy okrąg na niego nachodzi. Ale to jeszcze nie znaczy, że to okręgi na siebie nachodzą. Teraz zmieniając go na 4 mniejsze nie mam jak skorzystać z poprzednich wyliczeń. Muszę dla każdego sprawdzić czy przecina się ze wszystkimi okręgami. Teraz może wyjść na to, że 3 z nich przecinają sie z każdym z okręgów. Teraz dla tych 3 muszę sprawdzić przecięcie z każdym okręgiem. I tych kwadracików się namnaża, a dla każdego muszę wykonać n przecięć. To daje koszmarną złożoność.

 

Poza tym ma to niewiele z drzewem czwórkowym więc pewnie masz na myśli co innego, ale ja nie rozumiem co.

[Will]

Jeśli jutro znajdę trochę czasu to napisze prototyp. Tylko podrzuć kilka przykładów z danymi wejściowymi.

[Platyna]

Proszę bardzo:

https://gmclan.org/up348_4_input.html

 

Pierwsza liczba oznacza ilość okręgów, druga ich promień.

Kolejne n wierszy to pary liczb oznaczających współrzędne środków.

 

Niech program wyznaczy dowolny punkt znajdujący się w części wspólnej kół od 1 do x dla takiego x, że koła od 1 do x+1 nie mają już części wspólnej. Czyli, że okrąg x+1 nie przecina części wspólnej kół od 1 do x.