Finden Sie die am besten geeignete Größe für den Kreis

Unten ist ein Beispielbild, wenn ich einen Punkt mit dem weißen Punkt in der Mitte habe und den nächstmöglichen Ort für den blauen Kreis (der sich offensichtlich an dem Ort befindet, an dem ich ihn platziert habe) suchen möchte, wenn bereits alle roten Kreise vorhanden sind . Wie finde ich diesen Ort?

Leistung ist für mich kein großes Problem für diese Anwendung.

Dies ist keine allgemeine Lösung, da es mehrere Situationen gibt, in denen die Position des blauen Kreises nicht mit dem kürzesten Abstand zum weißen Punkt angegeben wird. Wenn Sie beispielsweise 100 rote Kugeln gruppiert haben und der weiße Punkt weit von dieser Gruppe roter Kugeln entfernt ist, hat keine der roten Kugeln Einfluss auf die Position des blauen Kreises, der nur auf dem weißen Punkt zentriert werden kann . Es werden auch nicht alle Berechnungsdetails angezeigt. Für eine Untergruppe von Konfigurationen, in denen die Lösung (blauer Kreis) zwei rote Kreise berührt, sollte Folgendes funktionieren:
1) Sei R der Radius des blauen Kreises.
2) Machen Sie eine Schleife über alle roten Kreispaare. Ja Ich weiß, das ist O (n2).
3) Berechnen Sie für jedes Kreispaar i, j mit Mittelpunkten bei (xi, yi) und (xj, yj) mit dem jeweiligen Radius ri und rj das Quadrat des Abstands zwischen dem Kreispaar

d_ij^2=(xi-xj)^2+(yi-yj)^2  

4) Setze alle Kreise die

dij^2<R^2

in eine Liste.

5) Durchlaufen Sie die Liste und finden Sie die beiden Lösungen der Kreise mit dem Radius R, die beide Kreise i und j berühren. Verwenden Sie dazu diese Gleichungen zusammen mit diesem Bild

a = R+ri  
b = R+rj  
c = dij  
α = arccos((b^2+c^2-a^2)/(2bc)  

Mit den obigen Informationen können Sie (X1ij, Y1ij) und (X2ij, Y2ij) die Zentren der 2 Kreise finden, die die Kreise i und j tangieren. Führen Sie für jeden Kandidaten einen blauen Kreis über alle anderen roten Kreise und prüfen Sie, ob er sich nicht überlappt. Wenn dies nicht der Fall ist, überprüfen Sie den Abstand zum weißen Kreis. Wenn Sie den Abstand halten, haben Sie wahrscheinlich die Lösung, wenn Sie die Liste der Kreispaare durchlaufen haben. Der Algorithmus scheint wie O (n3).

Die dem Punkt am nächsten liegende Position befindet sich entweder auf dem Punkt oder sie berührt einen Kreis.

Überprüfen Sie daher zuerst den Punkt, und rollen Sie dann den neuen Kreis um die Kante jedes vorhandenen Kreises. Berechnen Sie dabei den Abstand zum Punkt, und achten Sie bei Überlappungen auf den Mindestabstandspunkt. Stoppen Sie, wenn Sie jeden Kreis durchlaufen haben.

dh Überprüfen Sie alle Punkte auf den grünen Linien sowie den weißen Kreis. Dabei ist die grüne Linie ein Kreis mit dem Radius von Rot und Blau

Sie müssen die gesamte grüne Linie und nicht nur die Schnittpunkte überprüfen, um diese Randfälle abzudecken.

Offensichtlich wird die Schrittgröße Ihrer Traversierung für die Leistung wichtig sein. Da Sie jedoch angeben, dass die Leistung kein Problem darstellt, wählen Sie den Wert, der der Auflösung Ihres Ausgabewerts entspricht. dh schweben, lange?

Klärung:

Mein Vorschlag ist, alle Punkte um jeden Kreis herum zu zwingen und auf Überlappung mit allen anderen Kreisen an jedem Punkt zu prüfen . keine klugheit.

Wenn das Beispielbild die Anzahl der Kreise und die Auflösung angibt, sollte dies für einen Standard-PC kein Problem darstellen

Wir haben 20 Kreise mit einem durchschnittlichen Radius von 200, dh ungefähr 20 * 2 π * 200 Punkte * 20 Schnittpunkttests = 4800000 Iterationen

Hinweis:

Iterative Ansätze wie dieser haben den Nachteil, dass Ihre Schrittweite, in diesem Fall die Auflösung Ihrer Ausgabe, das Ergebnis stark beeinflussen kann.

Angenommen, ich habe zwei rote Kreise, die 2 Pixel voneinander entfernt sind, und einen blauen Kreis mit einem Radius von 1 Pixel, der zwischen ihnen gedrückt werden soll. Es ist klar, dass eines der beiden Pixel als Mittelpunkt des blauen Kreises eines der Rottöne überlappt. aber offensichtlich ist Platz für den Kreis, wenn der Mittelpunkt zwischen den beiden Pixeln liegt.

Daher mein Kommentar zur Auflösung der Ausgabe. Was du gesagt hast, könnte alles sein.

Sie können auch die Simultangleichung für jedes Kreispaar lösen, wobei sich der Radius um den Radius des blauen Kreises erhöht.

Auf diese Weise erhalten Sie die Punkte, an denen der blaue Kreis die beiden roten Kreise genauer berührt als bei der Iteration.

Jedoch. Es gibt verschiedene Situationen, in denen Sie die falsche oder keine Antwort erhalten, wenn Sie dies nur tun. dh

1 oder keine Kreise

2 oder mehr Kreise, aber mit einem weit entfernten und außerhalb davon liegenden Zielpunkt.

viele Kreise, aber mit einem Zielpunkt nahe an der Oberfläche

Dieser Plunk enthält Arbeitscode ,

Konzept

Gegebene Kreise sind C1, C2 .... Cn

und die Koordinaten des Kreises Cn sind Cnx, Cny und der Radius ist Cr

und der Radius des erforderlichen Kreises ist R

Befindet sich der blaue Kreis an der Position X, Y und widerspricht er keinem anderen Kreis, gelten die folgenden Gleichungen

(C1x - X)^2 + (C1y - Y)^2 > (C1r + R)^2
(C2x - X)^2 + (C2y - Y)^2 > (C2r + R)^2
....
(Cnx - X)^2 + (Cny - Y)^2 > (Cnr + R)^2

Ändern der ersten Gleichung,

C1x^2 - 2C1x*X + X^2 + C1y^2 - 2C1y*Y + Y^2 > C1r^2 + 2C1r*R + R^2
X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2

so können Gleichungen neu schreiben,

X^2 + Y^2 - 2C1x*X - 2C1y*Y > C1r^2 + 2C1r*R + R^2 - C1x^2 - C1y^2
X^2 + Y^2 - 2C2x*X - 2C2y*Y > C2r^2 + 2C2r*R + R^2 - C2x^2 - C2y^2
....
X^2 + Y^2 - 2Cnx*X - 2Cny*Y > Cnr^2 + 2Cnr*R + R^2 - Cnx^2 - Cny^2

Implementierung

ausgehend von der Koordinate des weißen Punktes (Xw, Yw),

    var isValidLocation = function(x,y,r){
       var valid = true;
       for (var i = 0; i< circles.length; i++){
          var circle = circles[i];
          valid = valid && ((x*x + y*y - 2*circle.x*x - 2*circle.y*y) > (circle.radius*circle.radius + 2*circle.radius*r + r*r - circle.x*circle.x - circle.y*circle.y));
       }
       return valid;
      };

      var find = function(Xw,Yw,Rw){
        var radius = 0;
        while(true){
          for (var x=-1 * radius ;x <= radius; x++) {
            for (var y=-1 * radius;y <= radius; y++) {
               if (isValidLocation(Xw + x,Yw + y, Rw)){
                 drawCircle(Xw + x,Yw + y,Rw,"#0000FF");
                 return;
               }
            }   
          } 
          radius++;
        }
     }; 

Die erste gefundene Koordinate, die alle Gleichungen erfüllt, ist die Position des blauen Kreises

• O der Punkt zu sein, dem du nahe sein willst
• P ist der Punkt, den Sie suchen (der Mittelpunkt des blauen Kreises)
• r ist der Radius des blauen Kreises
• C0 .. Cn sind die Zentren aller Kreise, die die Platzierung des Blaus einschränken

• Der erweiterte Kreis ist einer der Kreise, deren Radius um r erweitert ist

  Es gibt etwas zusätzliche Arbeit, wenn O nicht in einem Kreismittelpunkt liegt. Nehmen wir jetzt also O == C0 an

Berechnen Sie alle Schnittpunkte aller Kreise mit C0, indem Sie ihre jeweiligen Radien plus das r verwenden . Dh, schneiden Sie die Erstreckungskreise mit dem erweiterten C0. Wenn es keine Schnittpunkte gibt, befindet sich der gesuchte Punkt an einer beliebigen Stelle auf C0. Wenn es Schnittpunkte gibt, überprüfen Sie für jeden Schnittpunkt, ob er sich innerhalb eines anderen erweiterten Kreises befindet (Sie können sich auf die Kreise beschränken, die Schnittpunkte mit C0 hatten). Nehmen Sie die erste Kreuzung, die sich nicht in einem anderen erweiterten Kreis befindet, als P, es könnten andere sein.

Wenn es keine Schnittpunkte zwischen den erweiterten Kreisen und C0 gibt, die sich nicht innerhalb eines anderen erweiterten Kreises befinden, berechnen Sie die Schnittpunkte aller erweiterten Kreise miteinander. Überprüfen Sie dann diese Schnittpunkte in der Reihenfolge des Abstands zu O. Überprüfen Sie erneut, ob einer der Schnittpunkte innerhalb eines weiteren erweiterten Kreises liegt. Wenn ja, verwerfen Sie, wenn nein, ist dies Ihr Ergebnis.

Wenn Sie sich das vorstellen, ziehen Sie eine Linie um alle Kreise, die einen möglichen Ort für Ihren blauen Kreis angeben, und nehmen Sie die Vereinigung aller erweiterten Kreise, um den Bereich anzuzeigen, den Ihr blauer Kreis nicht haben kann. Der Punkt, den Sie suchen, ist der nächstgelegene Punkt, der sich nicht in dieser Vereinigung befindet. Wenn es auf C0 einen Punkt gibt, der sich nicht in der Vereinigung befindet, die die Lösung ist, und wenn C0 vollständig bedeckt ist, muss sich P an einem Schnittpunkt zwischen zwei anderen erweiterten Kreisen befinden und in einem Bereich, der nicht bedeckt ist diese Vereinigung (dh nicht in einem erweiterten Kreis ).

Dies ist O (n ^ 2). Es gibt jedoch einige Möglichkeiten, dies zu verbessern. Ein Raster kann verwendet werden, um den Aufwand für die paarweise Suche zu verringern. Ich denke auch, dass die Kreise nach ihrer Nähe zu O (dem Abstand zwischen dem Zwei Kreise (vom Radio verkleinert) würden dazu beitragen, den Suchraum für die Überdeckungs- und Kreuzungssuche zu begrenzen

Mögliche Lösungen suchen

1. Überprüfen Sie, ob der Weißpunkt die Lösung für sich ist. Es deckt den Fall mit 0 roten Kreisen und den unbedeutenden Fall ab, wenn rote Kreise weit vom weißen Punkt entfernt sind.
2. Ein roter Kreis.
   1. Der weiße Punkt ist der Mittelpunkt des Kreises. Mögliche Lösungen sind unendlich viele Punkte auf dem Kreis, wobei der Mittelpunkt im weißen Punkt und der Radius die Summe des Radius des blauen Kreises und des Durchmessers des roten Kreises sind. Nennen wir es den grünen Kreis .
   2. Weißpunkt ist woanders. Es gibt nur eine mögliche Lösung auf der Linie, die den weißen Punkt und den Mittelpunkt des roten Kreises verbindet. Sie ist der Radius des blauen Kreises von dem Punkt entfernt, an dem der rote Kreis die Linie in Richtung des weißen Punktes kreuzt.
3. Zwei oder mehr rote Kreise.
   1. Nehmen wir nacheinander die roten Kreise und suchen nach einer möglichen Lösung für jeden von ihnen einzeln nach Punkt 2 (ein Kreis).
   2. Lassen Sie uns für jedes Paar der roten Kreise prüfen, ob Sie den blauen Kreis zeichnen können, der beide roten berührt. Dh wenn der Abstand zwischen ihren Mittelpunkten kleiner oder gleich der Summe ihrer Radien plus Durchmesser des blauen Kreises ist. Wenn Sie können, haben Sie zwei (oder eine, wenn die roten Kreise genau einen blauen Kreisdurchmesser entfernt sind) mögliche Lösungen .

Ist-Lösungssuche unter möglichen Lösungen

Jetzt haben Sie eine Reihe von Punkten, bei denen es sich um mögliche Lösungen handelt , durchlaufen diese und überprüfen sie für jede.

1. Wenn der Punkt tatsächlich eine Lösung ist. Kein roter Kreis sollte seinen Mittelpunkt näher als seinen Radius zu diesem Punkt haben.
2. Liegt es näher am Weißpunkt als die zuvor gefundene Lösung.
3. Wenn Sie den grünen Kreis haben (Punkt 2.1)
   • Wenn es unter den einzelnen Punkten keine Lösung gibt, die zum grünen Kreis gehört, ist der grüne Kreis die Antwort.
   • Wenn Sie individuelle Lösungen im grünen Kreis haben und nur eine Lösung benötigen, nehmen Sie einfach eine davon.
   • Wenn Sie individuelle Lösungen im grünen Kreis haben und eine unbegrenzte Anzahl von Lösungen benötigen, müssen Sie ein anderes Problem lösen. Sie müssen aus dem grünen Kreis alle Bögen ausschneiden, die durch ein Paar von Einzellösungen aus jedem roten Kreis definiert sind.

NB: Ich sage nicht, dass die Implementierung des Algorithmus genau beschrieben werden soll. Sie können versuchen, die Leistung durch dynamisches Programmieren zu verbessern, oder mögliche Lösungen überspringen, bei denen offensichtlich ist, dass sie nicht funktionieren.