Algorithmus, um zu prüfen, ob ein Kreis vollständig im Bereich anderer Kreise enthalten ist

Question

Welcher Algorithmus wäre zu prüfen, ob ein Kreis wie der blaue TOTAL im Bereich anderer Kreise enthalten ist (die Kreise). Ich möchte einen TRUE für den blauen Kreis und einen FALSE für den roten Kreis.

Der Eingang für alle Kreise ist ihre Koordinaten und ihr Radius.

Answer 1

Diese einfache scheint (EDIT: ist aber nicht): wenn jeder Punkt eines jeden Bogen eines gegebenen Kreises in mindestens einer der anderen Kreise enthalten ist, dann wird der ganze Kreis enthalten ist. Sie müssten dann alle Kreuzungen finden (algorithm to detect if a Circles intersect with any other circle in the same plane) und eine Überprüfung für alle Bögen durchführen, die durch diese Kreuzungen spezifiziert sind. Wenn irgendein "innerer" Punkt eines Bogens A1-A2 von Kreis A für gegebene zwei Schnittpunkte mit Kreis B (Bogen B1-B2, wo Punkte A1 = B1 und A2 = B2 sind) in dem Kreis B enthalten ist, dann ist der gesamte Bogen in Kreis B enthalten und umgekehrt. Bitte korrigieren Sie mich, wenn ich falsch liege.

EDIT: Ok ich weiß schon, dass ich falsch lag, wie maxim1000 gezeigt hat. Das ist komplizierter als ich dachte. Ich denke daran, etwas zu meiner Antwort hinzuzufügen, aber ich bin mir nicht sicher, ob das eine Lösung ist. Ich hoffe es hilft aber. Nämlich: Ich denke darüber nach, die Gesamtfläche der Überschneidungen zwischen unserem Kreis und allen anderen zu bestimmen. Wir finden alle getrennten Schnittpunkte innerhalb unseres Kreises - alle Teile, die die gleichen Punkte enthalten, die durch alle sich schneidenden Bögen getrennt sind - und finden ihre Bereiche. Wu summiere sie. Wenn es gleich der Fläche unseres Kreises ist, dann ist unser Kreis in anderen Kreisen enthalten. Die Bestimmung dieses Bereichs kann ein Problem für sich sein, aber wie gesagt, es kann in die richtige Richtung führen. Lassen Sie mich denken zu ..

EDIT: Nach einer Weile des Denkens. Die Bestimmung aller Bereiche in (mehreren) sich überschneidenden Kreisen ist nur eine Frage des Hinzufügens oder Abziehens von Dreiecken oder ... hmmm ... wie man sie nennt? ... gelb Teile wie hier auf dem Bild :)

Answer 2

Ich glaube nicht, gibt es eine einfache Lösung.

Ich würde das ansprechen, indem ich jeden Kreis der Reihe nach nehme und eine Boolesche Subtraktion aller anderen Kreise vornehme. (Die Kreise, die weit genug sind - R 0 + R1 < D12 - stören nicht.)

Nachdem Stücke gegessen worden sind, wird ein Kreis ein krummliniges Polygon, das von den Kreisbögen oder von einer Reihe solcher Polygone, als connexity Dose gebildet wird erledigt sein. Ein Polygon kann durch die Liste von Kreisen dargestellt werden, die einen Bogen seines Umrisses liefern, und die Bogenendpunkte werden durch den gemeinsamen Schnittpunkt zweier aufeinanderfolgender Nachbarn oder des Zielkreises und eines Nachbarn definiert. Beachten Sie, dass derselbe Nachbar mehrmals angezeigt werden kann.

Um die Dinge ein wenig blutiger zu machen, können die Polygone Löcher haben, die Sie ebenfalls darstellen müssen.

Dann ist eine entscheidende Operation die Subtraktion eines Kreises von einem krummlinigen Polygon. Sie müssen die Bögen erkennen, die sich vollständig innerhalb des neuen Kreises befinden und diejenigen, die ihn kreuzen. Nachdem Sie die restlichen Teile der Bögen erhalten haben, müssen Sie die verbleibenden Bögen und die neuen Bögen neu anordnen.

Ich denke, dass alle diese Operationen aus einem einzigen Grundelement, das den Teil eines Bogens (definiert durch drei Kreise) innerhalb einer Festplatte findet, erstellt werden können.

Answer 3

Hier ist eine rohe Lösung:

• alle Kreise nehmen und alle Schnittpunkte, die entweder auf oder in der Testkreis T. Teilen Sie die entsprechenden Kanten finden und bauen ein Kantengraph:

Für jede Kante verfolgen Sie den Kreis, der sie erstellt hat.

• Finden Sie alle nicht überlappende Regionen innerhalb des Kreises, die Minimum-Zyklus Algorithmus (Find all non-overlapping polygons in a list of edges/vertices).

• Für jede Begrenzungskante E jeden Bereich R Sie finden, nehmen Sie den Kreis C, die E gehört. Wenn C nicht T (rot) - dh E blau ist, prüfen Sie, ob die Punkte auf den anderen Kanten von R in der C:

  • Wenn sie dann C deckt R. auf die nächste Region weiter .
  • Wenn sie nicht sind, dann ist R nicht durch C. Schleife über die anderen blauen Kanten bedeckt begrenzt R.
  • Wenn am Ende R noch nicht bedeckt ist, dann ist T nicht vollständig abgedeckt - Rückkehr falsch.

in dem obigen Diagramm, enthält C B, R so bedeckt ist; aber C nicht enthält A, so nicht S decken

• Wenn Sie noch nicht in diesem Stadium zurück dann wahr zurückzukehren.

---

Seitenkoffer:

• Wenn ein bestimmter Kreis T enthält, dann ignorieren.
• Wenn T enthält es, dann defer den Schnittpunkt Test durch Speichern in einer Liste. Am Ende wiederholen Sie den Test und teilen Sie seine Kanten.

Dieser Algorithmus ist hoch ineffizient, und ich bin nicht 100% sicher, ob es noch mehr degenerierte Fälle sind; Wenn jemand irgendwelche Vorschläge hat, lass es mich wissen.