Positioniergeräte (sich überschneidende Kreise)
Ich habe eine Reihe von Punkten, die mobile Geräte in einem Raum darstellen. Zuvor habe ich systematisch jeweils einen Ping ausgesendet und die Zeit, zu der er bei den anderen ankommt, zur Berechnung der Entfernungen aufgezeichnet.
Hier ist ein einfaches Diagramm eines Beispielnetzwerkes.
Der untere A-Knoten sollte stattdessen ein D sein
Nach der Aufnahme der Entfernungen habe ich die Entfernungsinformation in Hashes.
%Vor%Meine Mathematik ist rostig, aber ich habe das Gefühl, dass ich in der Lage sein sollte, Kreise mit diesen Werten als jeweilige Kreise zu zeichnen und dann die Kreise zu schneiden, um einen relativen Graph der Knoten zu berechnen.
Jedes Mal, wenn ich es versuche, beginne ich mit einer Reihe von Kreisen, die um den Wurzelknoten herum gezeichnet sind (in diesem Fall A), der ungefähr so aussieht:
Ich weiß, dass die anderen Knoten auf den Linien liegen müssen, die ich um A gezeichnet habe, aber ohne sie positionieren zu können, wie zeichnen Sie ihre Abstände, so dass Sie die Kreise schneiden und den Graphen erstellen können?
>1 Antwort
Beginnen Sie mit einem beliebigen Punkt, sagen Sie A. Nun nehmen Sie den zweiten Punkt, sagen Sie B, und zeichnen Sie ihn irgendwo auf dem Kreis mit der Mitte bei A und Radius als Abstand zwischen A und B. Jetzt nehmen Sie einen weiteren Punkt C.
Lassen Sie die Entfernung (A,C)=x und (B,C)=y . Finde den Schnittpunkt der Kreise (A,x) und (B,y) . Markieren Sie es als C .
wobei der Kreis (P,q) den Mittelpunkt bei P und den Radius q angibt.
Wenn kein solcher Punkt existiert, sind die angegebenen Daten falsch.
Nimm nun den 4 th Punkt und finde ähnlich den Schnittpunkt von Kreisen mit Zentren an den ersten drei Punkten und Radien als Abstand zwischen dem vierten und anderen drei Punkten. Wenden Sie diese Methode an, bis alle Punkte geplottet sind.
Beachten Sie, dass es unendlich viele Lösungen geben kann, wie RobH darauf hingewiesen hat. Da Sie nur eine virtuelle Darstellung benötigen, reicht eine der gültigen Lösungen aus.
Der obige Algorithmus hat eine Reihenfolge von O(N^2) . Es kann ineffizient sein, wenn die Anzahl der Punkte größer als 10000 ist.
Beachten Sie auch, dass Sie, um den Schnittpunkt von k circles zu finden, zuerst den Schnittpunkt für zwei beliebige Kreise suchen und diese Punkte auf den verbleibenden Kreisen validieren müssen. Dies liegt daran, dass k -Kreise höchstens zwei Punkte schneiden können, vorausgesetzt, dass alle unterschiedliche Zentren haben.
BEARBEITEN: Zu jedem Zeitpunkt, wenn es zwei gültige Plots für einen Punkt gibt, können wir einen beliebigen auswählen und trotzdem kommen wir zu einer der gültigen Lösungen.
Tags und Links javascript algorithm java c math