Finden Kreis von bestimmtem Radius, der keine Punkte enthalten

Question

Ich bin an einem Problem arbeiten, die folgend reduziert im Wesentlichen nach unten:

Gegeben:

• einer Reihe von (x,y) Punkten. Es kann 0 Punkte in der Menge geben.
• min und max x und y Werte, wobei die Mindestwerte immer nicht negativ sind.
• ein Radius r

bestimmen, ob es möglich ist, einen Kreis mit dem Radius r Ort irgendwo auf der Ebene, so dass der Kreis in-Grenzen und enthält keine der Punkte, und wenn ja, gib diesen Ort zurück.

Schnittpunkte sind erlaubt - Punkte aus dem Satz können den Kreis schneiden, aber sie können nicht durch den Kreis enthalten sein. Der Kreis kann tangential die minimalen und maximalen x- und y-Werte berühren, aber nicht außerhalb der Grenzen liegen.

Das Ergebnis wäre ein (x,y) Punkt, wo die Mitte des Kreises gehen würde, oder ein Dummy-Ergebnis (d. H. (-1,-1))/Fehler, wenn es keinen solchen Ort gibt. Wenn es mehrere gültige Lösungen gibt, ist die Rückgabe von beliebigen in Ordnung.

Irgendwelche Ideen zu einem Algorithmus für einen solchen Ort zu lösen? Ich werde am Ende in Java implementieren, aber ich kann mit psuedocode arbeiten.

Answer 1

Antwort

ich die Lösung n >= 2 für den Fall sagen würde, wenn n die Anzahl der Punkte ist.

Sie können zwei Kreise finden, die durch ausgewählte 2 Punkte gehen.

Wenn der Kreis in einem Bereich liegt, und es enthält genau null Punkte, können Sie den Kreis ausgegeben.

So können Sie wählen, paar Punkte (p[i], p[j]) und überprüfen Sie für alle Kreise.

Wenn Sie die Lösung von zwei Kreisen nicht kennen, lesen Sie dies bitte.
Circle of given radius through two points

Sie können wie folgt implementate:

for i = 0 to n-1 
    for j = 0 to n-1 
     if dist(p[i], p[j]) <= 2 * r 
      circle c1, c2 = circle that goes through p[i] and p[j] 
      bool f1 = true 
      for k = 0 to n-1 
       if p[k] is in c1 -> f1 = false 
      if f1 is true -> return center of c1 
      bool f2 = true 
      for k = 0 to n-1 
       if p[k] is in c2 -> f2 = false 
      if f2 is true -> return center of c2 

Wenn Sie nicht finden können, können Sie Monte Carlo Algorithm verwenden.
Wenn Sie nicht in zufällig ausgewählten Tausenden von Punkten finden, denke ich, dass "nicht finden kann" ist in Ordnung.

Answer 2

Erstellen Sie eine Delaunay triangulation Ihres Pointset. Führen Sie für jeden Punkt das folgende Verfahren aus.

Zeichnen Sie einen Kreis mit Radius 2r um Ihren Punkt. Wenn alle benachbarten Punkte innerhalb des Kreises liegen, ist dieser Punkt schlecht, fahre mit dem nächsten fort.

Wenn nicht, berücksichtigen Sie alle Dreiecke mit diesem Eckpunkt. Sie bilden ein konvexes Polygon.Schneiden Sie es bei Bedarf auf die Grenzen Ihrer Region (es wird immer noch komplex sein). Jetzt müssen Sie einen Kreis mit Radius r finden, der innerhalb dieses Polygons liegt und den aktuellen Punkt nicht enthält. Dies ist eine einfache geometrische Übung (zeichne einen Kreis mit Radius r tangential zu jedem Paar benachbarter Kanten; wenn ein solcher Kreis keinen Punkt vom Punktsatz enthält, bist du fertig).

Sie können dies auf verschiedene Arten beschleunigen (z. B. wenn ein umschriebener Kreis für ein beliebiges Dreieck vollständig innerhalb Ihres Rechtecks ​​liegt und der Radius r oder größer ist, sind Sie fertig).