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

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?

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.

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.

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.

• 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 nie są zawarte 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.

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.

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)

_{(źródło: secretGeek.net )}

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.

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.

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 )}

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.

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.

Znalazłem ten link, który może być przydatny. Wydaje się jednak, że nie ma ostatecznej odpowiedzi. Odpowiedzi Google . Innym odniesieniem dla trzech okręgów jest twierdzenie Harukiego . Tam też jest gazeta.

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.

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 ++

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);