Połączony obszar nakładających się okręgów


107

Niedawno natknąłem się na problem, w którym miałem cztery okręgi (punkty środkowe i promień) i musiałem obliczyć powierzchnię sumy tych okręgów.

Przykładowe zdjęcie:

Dla dwóch kręgów to całkiem proste,

Mogę po prostu obliczyć ułamek powierzchni każdego koła, który nie znajduje się wewnątrz trójkątów, a następnie obliczyć pole powierzchni trójkątów.

Ale czy istnieje sprytny algorytm, którego mogę użyć, gdy jest więcej niż dwa okręgi?


15
To naprawdę interesujący problem, pamiętam, że widziałem go na zajęciach z geometrii w liceum, ale nigdy nie znalazłem rozwiązania. Jeśli nie możesz znaleźć odpowiedzi tutaj, spróbuj opublikować ją na mathoverflow.net i pozwól matematykom się na to zastanowić : P
Charles Ma

25
czasami prawdziwi programiści potrzebują prawdziwej matematyki
fa.

1
Co powiesz na odpowiedź na to pytanie - „Mamy przedstawicieli handlowych mieszkających w tych 4 lokalizacjach, z których każdy obsługuje obszar o tych 4 promieniach. Jak duży obszar kraju obejmujemy?” Jeśli masz zmieniającą się bazę przedstawicieli handlowych, staje się to kwestią programistyczną!
Chris Roberts

5
Właściwie to jest problem, o którym lubią myśleć prawdziwi programiści.
MAK

2
@zvolkov: płytki drukowane są opisane językiem, który przesuwa kwadraty i kółka w dół i opcjonalnie je przeciąga. „Oblicz obszar miedzi”. (Może to być potrzebne, aby obliczyć czasy wytrawiania, wiedzieć, czy dodać grafikę oczyszczającą, różne rzeczy).
DigitalRoss

Odpowiedzi:


97

Znajdź wszystkie przecięcia okręgów na zewnętrznym obwodzie (np. B, D, F, H na poniższym diagramie). Połącz je ze środkami odpowiednich okręgów, aby utworzyć wielokąt. Obszar sumy okręgów to obszar wielokąta + obszar wycinków koła określony przez kolejne punkty przecięcia i środek okręgu pomiędzy nimi. Musisz również uwzględnić wszelkie dziury.

koło nakłada się


17
Co się dzieje, gdy w środku jest dziura?
John Gietzen

3
Będziesz musiał odjąć środkowo połączony wielokąt dla otworu od sumy i dodać wycinki koła dla tego wielokąta do sumy.
Ants Aasma

3
fajnie, ale myślę, że będzie to wymagało wielu szczegółów implementacyjnych, aby obsłużyć wszystkie specjalne przypadki (kółko wewnątrz drugiego, bez przecięcia, dziury, jeden punkt kontaktowy ...)
fa.

1
Przypadki specjalne są dość łatwe. Okręgi wewnątrz innych są odrzucane, ponieważ nie mają żadnych przecięć na obwodzie. Kontakt jednopunktowy to w efekcie dwa przecięcia z zerową odległością. Odłączone kształty można znaleźć za pomocą algorytmu połączonych komponentów na wykresie, na którym dwa okręgi są połączone, jeśli odległość środków jest mniejsza niż suma promieni. Wszystkie otwory są wielokątami z wyjątkiem tego o największym obszarze. Skrzyżowania na obwodzie to wszystkie skrzyżowania, które nie znajdują się ściśle wewnątrz żadnego okręgu.
Ants Aasma

4
tak, ale granice dziur to także (małe) łuki. Nadal uważam, że to wymaga dużej ilości kodu, aby działało dobrze.
fa.

32

Jestem pewien, że istnieje sprytny algorytm, ale tutaj jest głupi, aby oszczędzić konieczności szukania go;

  • umieść obwiednię wokół okręgów;
  • generować losowe punkty w obwiedni;
  • dowiedzieć się, czy losowy punkt znajduje się wewnątrz jednego z okręgów;
  • oblicz obszar przez proste dodawanie i dzielenie (proporcja_punktów_wewnątrz * obszar_obramowania_obramowania).

Jasne, że to głupie, ale:

  • możesz uzyskać tak dokładną odpowiedź, jak chcesz, po prostu wygeneruj więcej punktów;
  • będzie działać dla dowolnych kształtów, dla których możesz obliczyć rozróżnienie wewnętrzne / zewnętrzne;
  • będzie pięknie pracować równolegle, dzięki czemu będziesz mógł używać wszystkich swoich rdzeni.

2
To zadziała, ale metody Monte-Carlo, takie jak ta, oparte po prostu na jednorodnym próbkowaniu, generalnie nie mają najlepszych współczynników konwergencji.
ShreevatsaR

2
Przepraszamy, ale mimo że doceniam Twój wysiłek i uważam, że Twoje rozwiązanie jest „praktycznie użyteczne”, uważam Twoje podejście za bardzo złe. Jest to problem, który można i należy rozwiązać za pomocą matematyki, a nie brutalnej siły. Marnowanie energii i rdzenia na takie problemy jest rozrzutne i rozrzutne.
mafu

5
Masz rację, wstydzę się siebie, ale mam klaster z 12 000 rdzeni, mogę sobie pozwolić na rozrzutność. I nie potrafię wymyślić, jak sprawić, by eleganckie matematyczne rozwiązanie obejmowało tak wiele procesorów.
Znak wysokiej wydajności

8
Nie ma nic złego w podejściu Monte-Carlo (lub jakimkolwiek innym losowym) podejściu, pod warunkiem, że zapewnia wymagany stopień dokładności i robi to w rozsądnym czasie.
MAK

@mafutrct, z pewnością masz rację. Jednak łatwo popełnić małe błędy w matematyce. To rozwiązanie zapewnia prosty sposób na sprawdzenie poprawności.
Richard

18

Odpowiedź Antsa Aasmy dała podstawową ideę, ale chciałem uczynić ją trochę bardziej konkretną. Spójrz na pięć kręgów poniżej i sposób, w jaki zostały rozłożone.

Przykład

  • Niebieskie kropki to centra kół.
  • Czerwone kropki to okrągłe przecięcia granic.
  • Czerwone kropki z białym wnętrzem to przecięcia na granicy okręgów, które niezawarte w żadnych innych okręgach .

Rozpoznanie tych 3 rodzajów kropek jest łatwe. Teraz skonstruuj graficzną strukturę danych, w której węzły to niebieskie kropki i czerwone kropki z białym wnętrzem. Dla każdego okręgu umieść krawędź między środkiem koła (niebieska kropka) a każdym z jego przecięć (czerwone kropki z białym wnętrzem) na jego granicy.

To rozkłada sumę koła na zestaw wielokątów (zacieniowane na niebiesko) i okrągłe fragmenty koła (zacieniowane na zielono), które są rozłączne parami i zakrywają oryginalną sumę (czyli partycję). Ponieważ każdy element tutaj jest czymś, co jest łatwe do obliczenia pola powierzchni, możesz obliczyć pole sumy powierzchni elementów.


Myślę, że mogę dość łatwo obliczyć zbiór czerwonych / białych kropek, jednak moja teoria grafów nie jest zbyt dobra: algorytmicznie, jak przejść z listy węzłów + krawędzi do obliczonego obszaru?
user999305

1
Algorytm można uprościć, używając zestawu nienakładających się trójkątów zamiast wielokątów. Łuki (obszary zielone) to obszary zawarte tylko w jednym okręgu. Zwiększ rozmiar wielokąta, dodając więcej okręgów. (w końcu możesz zapomnieć, że mówisz nawet o wielokątach). To sprawia, że ​​właściwości boolowskie, a obszary są łatwiejsze do obliczenia. Gdy pusta czerwona kropka staje się ciągłą czerwoną kropką, po prostu dodajesz więcej trójkątów do zestawu i dostosowujesz łuk, który jest „zjadany” przez coraz więcej przecinających się okręgów.
Steve

16

W przypadku innego rozwiązania niż poprzednie można oszacować oszacowanie z dowolną dokładnością przy użyciu drzewa czwórkowego.

Działa to również w przypadku dowolnej unii kształtu, jeśli możesz stwierdzić, czy kwadrat znajduje się wewnątrz, czy na zewnątrz, czy też przecina kształt.

Każda komórka ma jeden ze stanów: pusta, pełna, częściowa

Algorytm polega na „rysowaniu” okręgów w drzewie czwórnym zaczynając od małej rozdzielczości (np. 4 komórki oznaczone jako puste). Każda komórka to:

  • wewnątrz co najmniej jednego okręgu, a następnie oznacz komórkę jako pełną,
  • poza wszystkimi okręgami, oznacz komórkę jako pustą,
  • w przeciwnym razie zaznacz komórkę jako częściową.

Kiedy skończysz, możesz obliczyć oszacowanie powierzchni: pełne komórki dają dolną granicę, puste komórki dają wyższą granicę, częściowe komórki dają maksymalny błąd powierzchni.

Jeśli błąd jest dla Ciebie zbyt duży, udoskonalaj częściowe komórki, aż uzyskasz odpowiednią precyzję.

Myślę, że będzie to łatwiejsze do wdrożenia niż metoda geometryczna, która może wymagać obsługi wielu specjalnych przypadków.


3
Moje przypuszczenie jest, że będzie to zbieżne niż wewnętrzna algorytmu punktu Monte Carlo / zewnątrz też szybciej.
Frank Krueger

Wydaje się, że jest to dużo łatwiejsze do wdrożenia. Zdecydowanie sugerowana najlepsza metoda brutalnej siły. Dzięki!
Anton Hansson

brutalna siła nazywana jest tutaj twierdzeniem o ściskaniu
fa.

To rodzaj algorytmu, którego używasz w arytmetyce przedziałów. en.wikipedia.org/wiki/Interval_arithmetic
rjmunro

13

Uwielbiam podejście do przypadku 2 przecinających się okręgów - oto jak użyłbym niewielkiej odmiany tego samego podejścia dla bardziej złożonego przykładu.

Może to dać lepszy wgląd w uogólnianie algorytmu dla większej liczby częściowo nakładających się okręgów.

Różnica polega na tym, że zaczynam od połączenia centrów (więc między środkami okręgów jest wierzchołek, a nie między miejscami, w których przecinają się okręgi). Myślę, że to pozwala lepiej uogólnić.

(w praktyce może metoda Monte-Carlo się opłaca)

tekst alternatywny
(źródło: secretGeek.net )


1
Myślę, że podział na wielokąty sugerowany przez obraz będzie prawdopodobnie bardzo dobrym podejściem. Aby go zakodować, trzeba opracować wiele szczegółów. Jak poradzi sobie z łańcuchem dwudziestu okręgów, z których każde zachodzi tylko na ostatnie i następne w łańcuchu? Łatwo to rozgryźć ręcznie, ale jaki jest twój algorytm?
PeterAllenWebb

4

Jeśli chcesz uzyskać dyskretną (a nie ciągłą) odpowiedź, możesz zrobić coś podobnego do algorytmu malowania pikseli.

Narysuj okręgi na siatce, a następnie pokoloruj każdą komórkę siatki, jeśli jest w większości zawarta w okręgu (tj. Co najmniej 50% jej powierzchni znajduje się wewnątrz jednego z okręgów). Zrób to dla całej siatki (gdzie siatka obejmuje cały obszar pokryty okręgami), a następnie policz liczbę kolorowych komórek w siatce.


3

Hmm, bardzo ciekawy problem. Moje podejście byłoby prawdopodobnie podobne do następujących:

  • Opracuj sposób na ustalenie, jakie są obszary przecięcia dowolnej liczby okręgów, tj. Jeśli mam 3 okręgi, muszę być w stanie ustalić, jakie jest przecięcie między tymi okręgami. Metoda „Monte-Carlo” byłaby dobrym sposobem na przybliżenie tego ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ ).
  • Wyeliminuj wszystkie okręgi zawarte w całości w innym większym okręgu (spójrz na promień i moduł odległości między środkami dwóch okręgów) Nie sądzę, że jest to obowiązkowe.
  • Wybierz 2 okręgi (nazwij je A i B) i oblicz całkowitą powierzchnię za pomocą tego wzoru:

(dotyczy to dowolnego kształtu, czy to koła, czy innego)

area(A∪B) = area(A) + area(B) - area(A∩B)

Gdzie A ∪ Boznacza A związek B i A ∩ Boznacza A przecina B (możesz to rozwiązać od pierwszego kroku.

  • Teraz kontynuuj dodawanie okręgów i kontynuuj obliczanie obszaru dodanego jako suma / odejmowanie obszarów okręgów i obszarów przecięć między okręgami. Na przykład dla 3 okręgów (nazwij dodatkowe kółko C) obliczamy pole według następującego wzoru:

(To jest to samo, co powyżej, gdzie Azostało zastąpione A∪B)

area((A∪B)∪C) = area(A∪B) + area(C) - area((A∪B)∩C)

Gdzie area(A∪B)właśnie wypracowaliśmy i area((A∪B)∩C)można znaleźć:

area((A∪B)nC) = area((A∩C)∪(B∩C)) = area(A∩C) + area(A∩B) - area((A∩C)∩(B∩C)) = area(A∩C) + area(A∩B) - area(A∩B∩C)

Gdzie znowu można znaleźć obszar (A∩B∩C) z góry.

Najtrudniejszy jest ostatni krok - im więcej okręgów zostanie dodanych, tym bardziej się to skomplikuje. Uważam, że istnieje rozszerzenie umożliwiające obliczenie obszaru przecięcia ze skończoną sumą lub alternatywnie można to rozwiązać rekursywnie.

Również w odniesieniu do użycia metody Monte-Carlo do przybliżenia obszaru itersekcji, uważam, że możliwe jest zredukowanie przecięcia dowolnej liczby okręgów do przecięcia 4 z tych okręgów, które można dokładnie obliczyć (nie mam pojęcia, jak to zrobić jednak).

Przy okazji prawdopodobnie istnieje lepszy sposób na zrobienie tego - złożoność znacznie wzrasta (prawdopodobnie wykładniczo, ale nie jestem pewien) dla każdego dodanego dodatkowego koła.


Co się dzieje z formatowaniem? Przepraszam również za użycie n i u dla skrzyżowania i unii, prawdopodobnie jest lepszy sposób ...
Justin

1
dodano kilka znaków unii Unicode (∪) i skrzyżowań (∩). miejmy nadzieję, że działają.
Spoike

3

Pracowałem nad problemem symulacji zachodzących na siebie pól gwiazd, próbując oszacować rzeczywistą liczbę gwiazd na podstawie rzeczywistych obszarów dysku w gęstych polach, gdzie większe jasne gwiazdy mogą maskować słabsze. Ja również miałem nadzieję, że uda mi się to zrobić poprzez rygorystyczną analizę formalną, ale nie mogłem znaleźć algorytmu do tego zadania. Rozwiązałem to, generując pola gwiazdowe na niebieskim tle w postaci zielonych dysków, których średnica została określona przez algorytm prawdopodobieństwa. Prosta procedura może sparować je, aby sprawdzić, czy zachodzą na siebie (zmiana koloru pary gwiazd na żółty); następnie liczba pikseli kolorów generuje obserwowany obszar w celu porównania z obszarem teoretycznym. To następnie generuje krzywą prawdopodobieństwa dla prawdziwych zliczeń. Może brutalna siła, ale wydaje się, że działa OK. (źródło: 2from.com )


2

Oto algorytm, który powinien być łatwy do wdrożenia w praktyce i można go dostosować tak, aby powodował dowolnie mały błąd:

  1. Przybliż każdy okrąg regularnym wielokątem wyśrodkowanym w tym samym punkcie
  2. Oblicz wielokąt będący sumą przybliżonych okręgów
  3. Oblicz obszar scalonego wielokąta

Kroki 2 i 3 można przeprowadzić za pomocą standardowych, łatwych do znalezienia algorytmów z geometrii obliczeniowej.

Oczywiście im więcej stron użyjesz dla każdego przybliżającego się wielokąta, tym bliższa byłaby dokładna odpowiedź. Możesz przybliżyć użycie wpisanych i opisanych wielokątów, aby uzyskać granice dokładnej odpowiedzi.


2

Istnieją skuteczne rozwiązania tego problemu przy użyciu tak zwanych schematów mocy. To jest jednak naprawdę ciężka matematyka i nie jest to coś, czym chciałbym się zająć od ręki. Aby uzyskać „łatwe” rozwiązanie, wyszukaj algorytmy przeglądania linii. Podstawową zasadą jest tutaj podzielenie figury na paski, gdzie obliczenie powierzchni w każdym pasku jest stosunkowo łatwe.

Tak więc na rysunku zawierającym wszystkie okręgi, na których nic nie zostało wytarte, narysuj poziomą linię w każdej pozycji, która jest albo górą, albo dolną częścią okręgu, albo przecięciem 2 okręgów. Zauważ, że wewnątrz tych pasków wszystkie obszary, które musisz obliczyć, wyglądają tak samo: „trapez” z dwoma bokami zastąpionymi okrągłymi segmentami. Jeśli więc potrafisz obliczyć taki kształt, po prostu zrób to dla wszystkich indywidualnych kształtów i zsumuj je. Złożoność tego naiwnego podejścia to O (N ^ 3), gdzie N to liczba okręgów na rysunku. Mając sprytne wykorzystanie struktury danych, możesz ulepszyć tę metodę zamiatania linii do O (N ^ 2 * log (N)), ale jeśli naprawdę nie musisz, prawdopodobnie nie jest to warte zachodu.



1

W zależności od problemu, który próbujesz rozwiązać, może wystarczyć określenie górnej i dolnej granicy. Górna granica jest łatwa, po prostu suma wszystkich okręgów. W przypadku dolnej granicy możesz wybrać pojedynczy promień, tak aby żadne z okręgów się nie nakładały. Aby lepiej to znaleźć, znajdź największy promień (aż do rzeczywistego promienia) dla każdego okręgu, aby się nie nakładał. Powinno być również dość trywialne usunięcie wszelkich całkowicie nakładających się okręgów (wszystkie takie okręgi spełniają | P_a - P_b | <= r_a), gdzie P_a jest środkiem okręgu A, P_b jest środkiem okręgu B, a r_a jest promieniem A ), co poprawia zarówno górną, jak i dolną granicę. Możesz również uzyskać lepszą Górną granicę, jeśli użyjesz wzoru na pary na dowolnych parach, a nie tylko na sumie wszystkich okręgów. Może istnieć dobry sposób na wybranie „najlepszych”

Biorąc pod uwagę górną i dolną granicę, możesz być w stanie lepiej dostroić podejście Monte-Carlo, ale nic konkretnego nie przychodzi na myśl. Inną opcją (ponownie w zależności od aplikacji) jest rasteryzacja okręgów i zliczanie pikseli. Jest to w zasadzie metoda Monte-Carlo ze stałym rozkładem.


0

Można to rozwiązać za pomocą twierdzenia Greena ze złożonością n ^ 2log (n). Jeśli nie znasz Twierdzenia Greena i chcesz dowiedzieć się więcej, oto film i notatki z Khan Academy. Ale ze względu na nasz problem myślę, że mój opis wystarczy.

Przepraszamy za linki do zdjęć, ponieważ nie mogę publikować zdjęć (za mało punktów reputacji)

Ogólne równanie twierdzenia Greena

Jeśli wstawię L i M takie, że

Stan: schorzenie

wtedy RHS jest po prostu obszarem Regionu R i można go uzyskać rozwiązując całkę zamkniętą lub LHS i to jest dokładnie to, co zamierzamy zrobić.

Wszystkie związki można rozbić na takie rozłączne zbiory okręgów, które się przecinają

Tak więc całkowanie wzdłuż ścieżki w kierunku przeciwnym do ruchu wskazówek zegara daje nam Obszar regionu, a całkowanie zgodnie z ruchem wskazówek zegara daje nam ujemny obszar . Więc

AreaOfUnion = (Integracja wzdłuż czerwonych łuków w kierunku przeciwnym do ruchu wskazówek zegara + Integracja wzdłuż niebieskich łuków w kierunku zgodnym z ruchem wskazówek zegara)

Ale fajna sztuczka polega na tym, że dla każdego okręgu, jeśli scałkujemy łuki, które nie znajdują się wewnątrz żadnego innego okręgu, otrzymamy wymagany obszar, tj. Uzyskamy całkowanie w kierunku przeciwnym do ruchu wskazówek zegara wzdłuż wszystkich czerwonych łuków i całkowanie wzdłuż wszystkich niebieskich łuków wzdłuż kierunku zgodnego z ruchem wskazówek zegara. ZADANIE WYKONANE!!!

Pod uwagę brane są nawet przypadki, gdy koło nie przecina się z żadnym innym.

Oto łącze GitHub do mojego kodu C ++


-1

Podejście do malowania pikseli (zgodnie z sugestią @Loadmaster) przewyższa rozwiązanie matematyczne na wiele sposobów:

  1. Wdrożenie jest znacznie prostsze. Powyższy problem można rozwiązać w mniej niż 100 wierszach kodu, jak pokazuje to rozwiązanie JSFiddle (głównie dlatego, że jest koncepcyjnie znacznie prostsze i nie ma przypadków skrajnych ani wyjątków, z którymi można by sobie poradzić).
  2. Łatwo dostosowuje się do bardziej ogólnych problemów. Działa z każdym kształtem, niezależnie od morfologii, o ile można go renderować za pomocą bibliotek rysunków 2D (tj. „Wszystkie!”) - okręgi, elipsy, splajny, wielokąty, możesz to nazwać. Heck, nawet obrazy bitmapowe.
  3. Złożoność rozwiązania do malowania pikseli wynosi ~ O [n], w porównaniu z ~ O [n * n] dla rozwiązania matematycznego. Oznacza to, że będzie działać lepiej wraz ze wzrostem liczby kształtów.
  4. A mówiąc o wydajności, często otrzymujesz akcelerację sprzętową za darmo, ponieważ większość nowoczesnych bibliotek 2D (jak sądzę, takich jak płótno HTML5) przenosi renderowanie na akceleratory graficzne.

Jedyną wadą malowania pikseli jest ograniczona dokładność rozwiązania. Ale można to dostroić, po prostu renderując na większe lub mniejsze płótna, w zależności od sytuacji. Zwróć też uwagę, że wygładzanie krawędzi w kodzie renderowania 2D (często domyślnie włączone) zapewni dokładność lepszą niż na poziomie piksela. Na przykład renderowanie figury 100x100 na płótnie o tych samych wymiarach powinno, moim zdaniem, dać dokładność rzędu 1 / (100 x 100 x 255) = 0,000039% ... co jest prawdopodobnie „wystarczająco dobre” do wszystkich problemów oprócz najbardziej wymagających.

<p>Area computation of arbitrary figures as done thru pixel-painting, in which a complex shape is drawn into an HTML5 canvas and the area determined by comparing the number of white pixels found in the resulting bitmap.  See javascript source for details.</p>

<canvas id="canvas" width="80" height="100"></canvas>

<p>Area = <span id="result"></span></p>
// Get HTML canvas element (and context) to draw into
var canvas = document.getElementById('canvas');
var ctx = canvas.getContext('2d');

// Lil' circle drawing utility
function circle(x,y,r) {
  ctx.beginPath();
  ctx.arc(x, y, r, 0, Math.PI*2);
  ctx.fill();
}

// Clear canvas (to black)
ctx.fillStyle = 'black';
ctx.fillRect(0, 0, canvas.width, canvas.height);

// Fill shape (in white)
ctx.fillStyle = 'white';
circle(40, 50, 40);
circle(40, 10, 10);
circle(25, 15, 12);
circle(35, 90, 10);

// Get bitmap data
var id = ctx.getImageData(0, 0, canvas.width, canvas.height);
var pixels = id.data; // Flat array of RGBA bytes

// Determine area by counting the white pixels
for (var i = 0, area = 0; i < pixels.length; i += 4) {
  area += pixels[i]; // Red channel (same as green and blue channels)
}

// Normalize by the max white value of 255
area /= 255;

// Output result
document.getElementById('result').innerHTML = area.toFixed(2);

To rozwiązanie nie uwzględnia wykonywania obliczeń matematycznych na obszarach kół. To mija się z celem pytania PO. Bardzo często geometria renderowania to tylko połowa sukcesu, jeśli chodzi o kształty geometryczne
Steve
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.