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?
Antworten:
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.
quelle
Ich bin mir sicher, dass es einen cleveren Algorithmus gibt, aber hier ist ein dummer, um nicht danach suchen zu müssen.
Sicher ist es dumm, aber:
quelle
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.
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.
quelle
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:
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.
quelle
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)
(Quelle: secretGeek.net )
quelle
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.
quelle
Hmm, sehr interessantes Problem. Mein Ansatz wäre wahrscheinlich wie folgt:
(Dies gilt für jede Form, sei es Kreis oder auf andere Weise)
Wobei
A ∪ B
A Vereinigung BA ∩ B
bedeutet und A B schneidet (Sie können dies vom ersten Schritt an herausfinden.(Dies ist das gleiche wie oben, wo
A
durch ersetzt wurdeA∪B
)Wo
area(A∪B)
wir gerade trainiert haben undarea((A∪B)∩C)
zu finden sind: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).
quelle
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 )
quelle
Hier ist ein Algorithmus, der in der Praxis einfach zu implementieren sein sollte und angepasst werden kann, um einen beliebig kleinen Fehler zu erzeugen:
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.
quelle
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.
quelle
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.
quelle
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.
quelle
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.
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!!!
Hier ist der GitHub-Link zu meinem C ++ - Code
quelle
Der Pixel-Painting-Ansatz (wie von @Loadmaster vorgeschlagen) ist der mathematischen Lösung in vielerlei Hinsicht überlegen:
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.
quelle