Kombinierter Bereich überlappender Kreise

107

Ich bin kürzlich auf ein Problem gestoßen, bei dem ich vier Kreise (Mittelpunkte und Radius) hatte und die Fläche der Vereinigung dieser Kreise berechnen musste.

Beispielbild:

Für zwei Kreise ist es ganz einfach,

Ich kann einfach den Bruchteil jeder Kreisfläche berechnen, die nicht innerhalb der Dreiecke liegt, und dann die Fläche der Dreiecke berechnen.

Aber gibt es einen cleveren Algorithmus, den ich verwenden kann, wenn mehr als zwei Kreise vorhanden sind?

Anton Hansson
quelle
15
Dies ist ein wirklich interessantes Problem. Ich erinnere mich, dass ich es in der Geometrieklasse der High School gesehen habe, aber nie eine Lösung gefunden habe. Wenn Sie hier keine Antwort finden, versuchen Sie, sie auf mathoverflow.net zu veröffentlichen, und lassen Sie die Mathematiker einen Knaller drauf haben: P
Charles Ma
25
manchmal echte Programmierer brauchen echte Mathe
fa.
1
Wie wäre es mit der Ausarbeitung der Antwort auf diese Frage: "Wir haben Vertriebsmitarbeiter an diesen 4 Standorten, von denen jeder einen Bereich mit diesen 4 Radien bedient. Wie viel des Landes decken wir ab?" Wenn Sie eine sich ändernde Datenbank mit Vertriebsmitarbeitern hatten, wird dies zu einer Programmierfrage!
Chris Roberts
5
Eigentlich ist dies das Problem, über das echte Programmierer gerne nachdenken.
MAK
2
@zvolkov: Leiterplatten werden mit einer Sprache beschrieben, die Quadrate und Kreise nach unten plumpst und sie optional zieht. "Berechnen Sie die Kupferfläche". (Dies kann erforderlich sein, um Ätzzeiten zu berechnen und zu wissen, ob
Spülgrafiken hinzugefügt werden sollen

Antworten:

97

Suchen Sie alle Kreisschnittpunkte am Außenumfang (z. B. B, D, F, H im folgenden Diagramm). Verbinden Sie sie mit den Mittelpunkten der entsprechenden Kreise, um ein Polygon zu bilden. Die Fläche der Vereinigung der Kreise ist die Fläche des Polygons + die Fläche der Kreisscheiben, die durch aufeinanderfolgende Schnittpunkte und den dazwischen liegenden Kreismittelpunkt definiert sind. Sie müssen auch alle Löcher berücksichtigen.

Kreisüberlappung

Ameisen Aasma
quelle
17
Was passiert, wenn sich in der Mitte ein Loch befindet?
John Gietzen
3
Sie müssen das mittig verbundene Polygon für das Loch von der Summe subtrahieren und die Kreisschnitte für dieses Polygon zur Summe hinzufügen.
Ants Aasma
3
schön, aber ich denke, dies erfordert viele Implementierungsdetails, um alle Sonderfälle zu behandeln (Kreis innerhalb des anderen, keine Kreuzung, Löcher, Einpunktkontakt ...)
fa.
1
Die Sonderfälle sind ziemlich einfach. Kreise in anderen werden verworfen, indem keine Umfangskreuzungen vorhanden sind. Ein Punktkontakt besteht praktisch aus zwei Kreuzungen mit einem Abstand von Null. Getrennte Formen können über den Algorithmus für verbundene Komponenten über dem Diagramm gefunden werden, wobei zwei Kreise verbunden sind, wenn der Abstand der Zentren kleiner als die Summe der Radien ist. Löcher sind alle Polygone außer dem mit der größten Fläche. Perimeter-Schnittpunkte sind alle Schnittpunkte, die sich nicht ausschließlich innerhalb eines Kreises befinden.
Ants Aasma
4
Ja, aber die Ränder der Löcher sind auch (kleine) Bögen. Ich denke immer noch, dass dies viel Code benötigt, um gut zu funktionieren.
fa.
32

Ich bin mir sicher, dass es einen cleveren Algorithmus gibt, aber hier ist ein dummer, um nicht danach suchen zu müssen.

  • lege einen Begrenzungsrahmen um die Kreise;
  • zufällige Punkte innerhalb des Begrenzungsrahmens erzeugen;
  • Finden Sie heraus, ob sich der zufällige Punkt innerhalb eines der Kreise befindet.
  • Berechnen Sie den Bereich durch einfaches Hinzufügen und Teilen (Anteil_der_Punkte_Innen * Bereich_der_Begrenzungsbox).

Sicher ist es dumm, aber:

  • Sie können eine so genaue Antwort erhalten, wie Sie möchten. Generieren Sie einfach mehr Punkte.
  • Es funktioniert für alle Formen, für die Sie die Unterscheidung zwischen Innen und Außen berechnen können.
  • Es wird wunderschön parallelisiert, sodass Sie alle Ihre Kerne verwenden können.
Hochleistungsmarke
quelle
2
Dies wird funktionieren, aber Monte-Carlo-Methoden wie diese, die einfach auf einer einheitlichen Stichprobe basieren, weisen im Allgemeinen nicht die besten Konvergenzraten auf.
ShreevatsaR
2
Entschuldigung, aber obwohl ich Ihre Bemühungen schätze und denke, dass Ihre Lösung "praktisch verwendbar" ist, halte ich Ihren Ansatz für sehr falsch. Dies ist ein Problem, das durch Mathematik und nicht durch rohe Gewalt gelöst werden kann und sollte. Bei solchen Problemen Energie und Kerne zu verschwenden, ist verschwenderisch und verschwenderisch.
Mafu
5
Sie haben Recht, ich schäme mich, aber ich habe einen Cluster mit 12.000 Kernen, den ich mir leisten kann, verschwenderisch zu sein. Und ich kann nicht herausfinden, wie die elegante mathematische Lösung auf so viele Prozessoren skaliert werden kann.
High Performance Mark
8
An einem Monte-Carlo-Ansatz (oder einem randomisierten Ansatz) ist an sich nichts auszusetzen, vorausgesetzt, er bietet das erforderliche Maß an Genauigkeit und dies in angemessener Zeit.
MAK
@mafutrct, du hast sicherlich recht. Es ist jedoch leicht, kleine Fehler in der Mathematik zu machen. Diese Lösung bietet eine einfache Möglichkeit, die Richtigkeit zu testen.
Richard
18

Die Antwort von Ants Aasma gab die Grundidee wieder, aber ich wollte sie etwas konkreter machen. Schauen Sie sich die fünf Kreise unten an und wie sie zerlegt wurden.

Beispiel

  • Die blauen Punkte sind Kreismittelpunkte.
  • Die roten Punkte sind Kreisgrenzschnittpunkte.
  • Die roten Punkte mit weißem Innenraum sind Kreisgrenzschnittpunkte, die in keinem anderen Kreis enthalten sind .

Das Identifizieren dieser 3 Arten von Punkten ist einfach. Erstellen Sie nun eine Diagrammdatenstruktur, in der die Knoten die blauen und die roten Punkte mit dem weißen Innenraum sind. Setzen Sie für jeden Kreis eine Kante zwischen der Kreismitte (blauer Punkt) und jedem seiner Schnittpunkte (rote Punkte mit weißem Innenraum) an seiner Grenze.

Dadurch wird die Kreisvereinigung in eine Reihe von Polygonen (blau schattiert) und kreisförmigen Tortenstücken (grün schattiert) zerlegt, die paarweise getrennt sind und die ursprüngliche Vereinigung (dh eine Trennwand) abdecken. Da jedes Stück hier leicht zu berechnen ist, können Sie die Fläche der Vereinigung berechnen, indem Sie die Flächen der Stücke summieren.

Timothy Shields
quelle
Ich denke, ich kann einen Satz der rot / weißen Punkte ziemlich einfach berechnen, aber meine Graphentheorie ist nicht allzu groß: Wie kommt man algorithmisch von einer Liste von Knoten + Kanten zu einem berechneten Bereich?
user999305
1
Der Algorithmus kann vereinfacht werden, indem ein Satz nicht überlappender Dreiecke anstelle von Polygonen verwendet wird. Die Bögen (grüne Bereiche) sind Bereiche, die nur in einem Kreis enthalten sind. Erweitern Sie die Größe eines Polygons, wenn Sie weitere Kreise hinzufügen. (Am Ende können Sie vergessen, dass Sie sogar über Polygone sprechen). Es macht boolesche Eigenschaften und die Bereiche sind auch einfacher zu berechnen. Wenn ein hohler roter Punkt zu einem festen roten Punkt wird, fügen Sie einfach mehr Dreiecke zu Ihrem Satz hinzu und passen den Bogen an, der von immer mehr sich kreuzenden Kreisen "weggefressen" wird.
Steve
16

Für eine andere Lösung als die vorherige können Sie mit einem Quadtree eine Schätzung mit beliebiger Genauigkeit erstellen.

Dies funktioniert auch für jede Formverbindung, wenn Sie feststellen können, ob sich ein Quadrat innerhalb oder außerhalb befindet oder die Form schneidet.

Jede Zelle hat einen der Zustände: leer, voll, teilweise

Der Algorithmus besteht darin, die Kreise im Quadtree beginnend mit einer niedrigen Auflösung (4 Zellen zum Beispiel als leer markiert) zu "zeichnen". Jede Zelle ist entweder:

  • innerhalb von mindestens einem Kreis, dann markieren Sie die Zelle als voll,
  • Markieren Sie die Zelle außerhalb aller Kreise als leer.
  • Andernfalls markieren Sie die Zelle als teilweise.

Wenn dies erledigt ist, können Sie eine Schätzung der Fläche berechnen: Die vollständigen Zellen geben die Untergrenze an, die leeren Zellen geben die Obergrenze an, die Teilzellen geben den maximalen Flächenfehler an.

Wenn Ihnen der Fehler zu groß ist, verfeinern Sie die Teilzellen, bis Sie die richtige Genauigkeit erhalten.

Ich denke, dies wird einfacher zu implementieren sein als die geometrische Methode, die möglicherweise viele Sonderfälle behandelt.

Fa.
quelle
3
Ich vermute, dass dies auch schneller konvergiert als der Monte-Carlo-Innen- / Außenpunkt-Algorithmus.
Frank Krueger
Dies scheint viel einfacher zu implementieren zu sein. Auf jeden Fall die beste vorgeschlagene Brute-Force-Methode. Vielen Dank!
Anton Hansson
Brute Force heißt hier Squeeze Theorem
fa.
Das ist die Art von Algorithmus, die Sie in der Intervallarithmetik verwenden. en.wikipedia.org/wiki/Interval_arithmetic
rjmunro
13

Ich liebe die Herangehensweise an den Fall von 2 sich kreuzenden Kreisen - hier ist, wie ich eine geringfügige Variation derselben Herangehensweise für das komplexere Beispiel verwenden würde.

Dies könnte einen besseren Einblick in die Verallgemeinerung des Algorithmus für eine größere Anzahl von halb überlappenden Kreisen geben.

Der Unterschied besteht darin, dass ich zunächst die Zentren verbinde (es gibt also einen Eckpunkt zwischen der Mitte der Kreise und nicht zwischen den Stellen, an denen sich die Kreise schneiden). Ich denke, dies lässt es besser verallgemeinern.

(In der Praxis lohnt sich vielleicht die Monte-Carlo-Methode)

Alt-Text
(Quelle: secretGeek.net )

Leon Bambrick
quelle
1
Ich denke, die von Ihrem Bild vorgeschlagene Art der Polygonteilung wäre wahrscheinlich ein sehr guter Ansatz. Es gibt viele Details zu erarbeiten, um es zu codieren. Wie würde es mit einer Kette von zwanzig Kreisen umgehen, von denen jeder nur den letzten und den nächsten in der Kette überlappt? Leicht von Hand herauszufinden, aber was ist Ihr Algorithmus?
PeterAllenWebb
4

Wenn Sie eine diskrete (im Gegensatz zu einer kontinuierlichen) Antwort wünschen, können Sie etwas Ähnliches wie einen Pixel-Malalgorithmus tun.

Zeichnen Sie die Kreise auf ein Raster und färben Sie dann jede Zelle des Rasters, wenn sie größtenteils in einem Kreis enthalten ist (dh mindestens 50% der Fläche befinden sich in einem der Kreise). Führen Sie dies für das gesamte Raster aus (wobei sich das Raster über den gesamten von den Kreisen abgedeckten Bereich erstreckt), und zählen Sie dann die Anzahl der farbigen Zellen im Raster.

David R Tribble
quelle
3

Hmm, sehr interessantes Problem. Mein Ansatz wäre wahrscheinlich wie folgt:

  • Erarbeiten Sie eine Methode, um die Schnittbereiche zwischen einer beliebigen Anzahl von Kreisen zu ermitteln. Wenn ich also drei Kreise habe, muss ich in der Lage sein, den Schnittpunkt zwischen diesen Kreisen zu ermitteln. Die "Monte-Carlo" -Methode wäre eine gute Möglichkeit, dies zu approximieren ( http://local.wasp.uwa.edu.au/~pbourke/geometry/circlearea/ ).
  • Beseitigen Sie alle Kreise, die vollständig in einem anderen größeren Kreis enthalten sind (siehe Radius und Modul des Abstands zwischen dem Mittelpunkt der beiden Kreise). Ich halte dies nicht für obligatorisch.
  • Wählen Sie 2 Kreise (nennen Sie sie A und B) und berechnen Sie die Gesamtfläche mit dieser Formel:

(Dies gilt für jede Form, sei es Kreis oder auf andere Weise)

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

Wobei A ∪ BA Vereinigung B A ∩ Bbedeutet und A B schneidet (Sie können dies vom ersten Schritt an herausfinden.

  • Fügen Sie nun weitere Kreise hinzu und berechnen Sie den hinzugefügten Bereich als Summe / Subtraktion von Kreisbereichen und Schnittflächen zwischen Kreisen. Zum Beispiel für 3 Kreise (nennen Sie den zusätzlichen Kreis C) berechnen wir den Bereich mit dieser Formel:

(Dies ist das gleiche wie oben, wo Adurch ersetzt wurde A∪B)

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

Wo area(A∪B)wir gerade trainiert haben und area((A∪B)∩C)zu finden sind:

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)

Wo wieder finden Sie Bereich (A∩B∩C) von oben.

Das Knifflige ist der letzte Schritt - je mehr Kreise hinzugefügt werden, desto komplexer wird es. Ich glaube, es gibt eine Erweiterung, um den Bereich einer Kreuzung mit einer endlichen Vereinigung zu berechnen, oder Sie können ihn alternativ rekursiv berechnen.

Auch im Hinblick auf die Verwendung von Monte-Carlo zur Annäherung des Querschnittsbereichs halte ich es für möglich, den Schnittpunkt einer beliebigen Anzahl von Kreisen auf den Schnittpunkt von 4 dieser Kreise zu reduzieren, der genau berechnet werden kann (keine Ahnung, wie dies zu tun ist) jedoch).

Es gibt wahrscheinlich einen besseren Weg, dies zu tun - die Komplexität nimmt für jeden zusätzlichen hinzugefügten Kreis erheblich zu (möglicherweise exponentiell, aber ich bin mir nicht sicher).

Justin
quelle
Was ist mit der Formatierung los? Auch entschuldigen Sie die Verwendung von n und u für Schnittmenge und Vereinigung, es gibt wahrscheinlich einen besseren Weg ...
Justin
1
Einige Unicode-Vereinigungszeichen (∪) und Schnittzeichen (∩) wurden hinzugefügt. hoffentlich funktionieren sie.
Spoike
3

Ich habe an einem Problem der Simulation überlappender Sternfelder gearbeitet und versucht, die tatsächlichen Sternzahlen aus den tatsächlichen Scheibenbereichen in dichten Feldern abzuschätzen, in denen die größeren hellen Sterne schwächere maskieren können. Auch ich hatte gehofft, dies durch strenge formale Analyse erreichen zu können, konnte aber keinen Algorithmus für die Aufgabe finden. Ich löste es, indem ich die Sternfelder auf einem blauen Hintergrund als grüne Scheiben erzeugte, deren Durchmesser durch einen Wahrscheinlichkeitsalgorithmus bestimmt wurde. Eine einfache Routine kann sie koppeln, um festzustellen, ob es eine Überlappung gibt (das Sternpaar wird gelb). dann erzeugt eine Pixelanzahl der Farben den beobachteten Bereich, um ihn mit dem theoretischen Bereich zu vergleichen. Dies erzeugt dann eine Wahrscheinlichkeitskurve für die wahren Zählungen. Brute Force vielleicht, aber es scheint in Ordnung zu funktionieren. (Quelle: 2from.com )

user213660
quelle
2

Hier ist ein Algorithmus, der in der Praxis einfach zu implementieren sein sollte und angepasst werden kann, um einen beliebig kleinen Fehler zu erzeugen:

  1. Approximieren Sie jeden Kreis durch ein reguläres Polygon, das am selben Punkt zentriert ist
  2. Berechnen Sie das Polygon, das die Vereinigung der angenäherten Kreise darstellt
  3. Berechnen Sie die Fläche des zusammengeführten Polygons

Die Schritte 2 und 3 können unter Verwendung von Standardalgorithmen aus der Rechengeometrie ausgeführt werden, die leicht zu finden sind.

Je mehr Seiten Sie für jedes approximierende Polygon verwenden, desto genauer wäre Ihre Antwort. Sie können sich mit eingeschriebenen und umschriebenen Polygonen annähern, um die genaue Antwort zu begrenzen.

PeterAllenWebb
quelle
2

Es gibt effiziente Lösungen für dieses Problem unter Verwendung sogenannter Leistungsdiagramme. Dies ist jedoch eine sehr schwere Mathematik und nichts, was ich sofort angehen möchte. Suchen Sie nach einer "einfachen" Lösung nach Line-Sweep-Algorithmen. Das Grundprinzip hierbei ist, dass Sie die Figur in Streifen aufteilen, wobei die Berechnung der Fläche in jedem Streifen relativ einfach ist.

Zeichnen Sie also auf der Figur, die alle Kreise enthält, ohne dass etwas ausgerieben wurde, an jeder Position eine horizontale Linie, die entweder die Oberseite eines Kreises, die Unterseite eines Kreises oder der Schnittpunkt von zwei Kreisen ist. Beachten Sie, dass innerhalb dieser Streifen alle Bereiche, die Sie berechnen müssen, gleich aussehen: ein "Trapez" mit zwei Seiten, die durch kreisförmige Segmente ersetzt sind. Wenn Sie also herausfinden können, wie eine solche Form berechnet wird, tun Sie dies einfach für alle einzelnen Formen und addieren Sie sie. Die Komplexität dieses naiven Ansatzes ist O (N ^ 3), wobei N die Anzahl der Kreise in der Figur ist. Mit einer cleveren Verwendung der Datenstruktur könnten Sie diese Line-Sweep-Methode auf O (N ^ 2 * log (N)) verbessern, aber wenn Sie es nicht wirklich brauchen, ist es wahrscheinlich nicht die Mühe wert.

Steve Thomas
quelle
1

Ich habe diesen Link gefunden, der nützlich sein kann. Es scheint jedoch keine endgültige Antwort zu geben. Google antwortet . Eine weitere Referenz für drei Kreise ist der Satz von Haruki . Dort gibt es auch ein Papier.

Greg Reynolds
quelle
1

Je nachdem, welches Problem Sie lösen möchten, kann es ausreichen, eine Ober- und Untergrenze zu erhalten. Eine Obergrenze ist einfach, nur die Summe aller Kreise. Für eine Untergrenze können Sie einen einzelnen Radius so auswählen, dass sich keiner der Kreise überlappt. Um dies zu verbessern, finden Sie für jeden Kreis den größten Radius (bis zum tatsächlichen Radius), damit er sich nicht überlappt. Es sollte auch ziemlich trivial sein, vollständig überlappende Kreise zu entfernen (alle diese Kreise erfüllen | P_a - P_b | <= r_a), wobei P_a der Mittelpunkt von Kreis A ist, P_b der Mittelpunkt von Kreis B ist und r_a der Radius von A ist ) und dies verbessert sowohl die Ober- als auch die Untergrenze. Sie könnten auch eine bessere Obergrenze erhalten, wenn Sie Ihre Paarformel für beliebige Paare anstelle der Summe aller Kreise verwenden. Es könnte einen guten Weg geben, die "besten" auszuwählen

Bei einer oberen und unteren Grenze können Sie möglicherweise einen Monte-Carlo-Ansatz besser einstellen, aber es fällt Ihnen nichts Spezielles ein. Eine andere Option (wiederum abhängig von Ihrer Anwendung) besteht darin, die Kreise zu rastern und die Pixel zu zählen. Es ist im Grunde der Monte-Carlo-Ansatz mit einer festen Verteilung.

Fryguybob
quelle
0

Dies kann mit dem Greenschen Theorem mit einer Komplexität von n ^ 2log (n) gelöst werden . Wenn Sie mit dem Satz des Grünen nicht vertraut sind und mehr wissen möchten, finden Sie hier das Video und die Notizen der Khan Academy. Aber für unser Problem denke ich, dass meine Beschreibung ausreichen wird.

Entschuldigen Sie die Links zu den Fotos, da ich keine Bilder posten kann. (Nicht genügend Reputationspunkte)

Allgemeine Gleichung des Satzes von Green

Wenn ich L und M so setze

Bedingung

dann ist die RHS einfach die Fläche der Region R und kann durch Lösen des geschlossenen Integrals oder der LHS erhalten werden, und genau das werden wir tun.

Alle Gewerkschaften können in solche disjunkten Kreissätze aufgeteilt werden, die sich schneiden

Wenn wir also gegen den Uhrzeigersinn entlang des Pfades integrieren, erhalten wir den Bereich der Region, und wenn wir im Uhrzeigersinn integrieren, erhalten wir einen negativen Wert für den Bereich . So

AreaOfUnion = (Integration entlang roter Bögen gegen den Uhrzeigersinn + Integration entlang blauer Bögen im Uhrzeigersinn)

Aber der coole Trick ist, wenn wir für jeden Kreis, wenn wir die Bögen integrieren, die sich nicht in einem anderen Kreis befinden, unseren erforderlichen Bereich erhalten, dh wir erhalten die Integration gegen den Uhrzeigersinn entlang aller roten Bögen und die Integration entlang aller blauen Bögen entlang der Richtung im Uhrzeigersinn. JOB ERLEDIGT!!!

Auch die Fälle, in denen sich ein Kreis nicht mit einem anderen kreuzt, werden behandelt.

Hier ist der GitHub-Link zu meinem C ++ - Code

Deepesh Thakur
quelle
-1

Der Pixel-Painting-Ansatz (wie von @Loadmaster vorgeschlagen) ist der mathematischen Lösung in vielerlei Hinsicht überlegen:

  1. Die Implementierung ist viel einfacher. Das obige Problem kann in weniger als 100 Codezeilen gelöst werden, wie diese JSFiddle-Lösung zeigt (hauptsächlich, weil es konzeptionell viel einfacher ist und keine Randfälle oder Ausnahmen zu behandeln hat).
  2. Es passt sich leicht an allgemeinere Probleme an. Es funktioniert mit jeder Form, unabhängig von der Morphologie, solange es mit 2D-Zeichnungsbibliotheken (dh „alle von ihnen!“) Rendern kann - Kreise, Ellipsen, Splines, Polygone, wie Sie es nennen. Verdammt, sogar Bitmap-Bilder.
  3. Die Komplexität der Pixel-Painting-Lösung beträgt ~ O [n] im Vergleich zu ~ O [n * n] für die mathematische Lösung. Dies bedeutet, dass es mit zunehmender Anzahl von Formen eine bessere Leistung erbringt.
  4. Apropos Leistung: Sie erhalten häufig eine kostenlose Hardwarebeschleunigung, da die meisten modernen 2D-Bibliotheken (wie HTML5s Canvas, glaube ich) die Rendering-Arbeit auf Grafikbeschleuniger verlagern.

Der einzige Nachteil beim Pixelmalen ist die endliche Genauigkeit der Lösung. Dies lässt sich jedoch durch einfaches Rendern auf größere oder kleinere Leinwände einstellen, je nach Situation. Beachten Sie auch, dass Anti-Aliasing im 2D-Rendering-Code (häufig standardmäßig aktiviert) eine Genauigkeit auf Pixelebene liefert. Wenn Sie beispielsweise eine 100 x 100-Figur in eine Leinwand mit denselben Abmessungen rendern, sollte dies meiner Meinung nach eine Genauigkeit in der Größenordnung von 1 / (100 x 100 x 255) = 0,000039% ergeben ... was wahrscheinlich „gut genug“ ist. für alle außer den anspruchsvollsten Problemen.

<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);
Broofa
quelle
Diese Lösung berücksichtigt keine mathematischen Berechnungen mit den Bereichen der Kreise. Es verfehlt den Punkt der OP-Frage. Sehr oft ist die Rendering-Geometrie nur die halbe Miete, wenn es um geometrische Formen geht
Steve