Trilaterationsalgorithmus für n Punkte

Ich muss einen Algorithmus finden, der den Schwerpunkt A (auch bekannt als Schwerpunkt, geometrischer Mittelpunkt, Massenmittelpunkt) aus der Zahl berechnet , in der sich die Kreise T1, T2, T3, T4, T5, .., Tn schneiden UND die Länge der Linie R vom Schwerpunkt bis am weitesten entfernte Ecke der genannten Figur

Folgende Informationen werden gegeben:

• T1 Latitude = 56.999883 Longitude = 24.144473 Radius = 943
• T2 Latitude = 57.005352 Longitude = 24.151168 Radius = 857
• T3 Latitude = 57.005352 Longitude = 24.163356 Radius = 714
• T4 Latitude = 56.999042 Longitude = 24.168506 Radius = 714
• T5 Latitude = 56.994226 Longitude = 24.15709 Radius = 771

Das Ergebnis sollte folgendermaßen aussehen: A Breite = XX.XXXXXXX Länge = XX.XXXXXXX Radius = XX

Wie Sie wahrscheinlich bereits herausgefunden haben, arbeite ich an einer Software, die den Gerätestandort anhand der nächstgelegenen WLAN-Zugangspunkte oder mobilen Basisstationen ermitteln kann. Da sich die Anzahl der Zugangspunkte oder Basisstationen ändern kann, benötige ich einen Algorithmus, der sich an eine ungewisse Anzahl von Punkten anpassen kann .

Es gibt hier und hier einige ähnliche Fragen , aber keine von ihnen beantwortet genau meine Frage.

Die Radiusmessungen sind sicherlich fehlerbehaftet. Ich würde erwarten, dass der Fehlerbetrag proportional zu den Radien selbst ist. Nehmen wir an, die Messungen sind ansonsten unvoreingenommen. Eine vernünftige Lösung verwendet dann eine gewichtete nichtlineare Anpassung der kleinsten Quadrate mit Gewichten, die umgekehrt proportional zu den quadratischen Radien sind.

Dies ist Standard - Sachen in (unter anderem) Python, R, Mathematica und viele voll funktionsfähige statistische Pakete, so dass ich es einfach veranschaulichen. Hier sind einige Daten, die durch Messen der Abstände mit einem relativen Fehler von 10% zu fünf zufälligen Zugriffspunkten rund um den Gerätestandort erhalten wurden:

Mathematica benötigt nur eine Codezeile und keine messbare CPU-Zeit, um die Anpassung zu berechnen:

fit = NonlinearModelFit[data, Norm[{x, y} - {x0, y0}], {x0, y0}, {x, y}, Weights -> 1/observations^2]

Bearbeiten--

Für große Radien können genauere (sphärische oder ellipsoidale) Lösungen gefunden werden, indem lediglich der euklidische Abstand Norm[{x, y} - {x0, y0}]durch eine Funktion zur Berechnung des sphärischen oder ellipsoidalen Abstandes ersetzt wird. In Mathematica könnte dies zB über erfolgen

fit = NonlinearModelFit[data, GeoDistance[{x, y}, {x0, y0}], {x0, y0}, {x, y}, 
        Weights -> 1/observations^2]

--Ende der Bearbeitung

Ein Vorteil einer solchen statistischen Technik besteht darin, dass Konfidenzintervalle für die Parameter (die Koordinaten des Geräts) und sogar eine gleichzeitige Konfidenzellipse für den Standort des Geräts erstellt werden können.

ellipsoid = fit["ParameterConfidenceRegion", ConfidenceLevel -> 0.95];
fit["ParameterConfidenceIntervalTable", ConfidenceLevel -> 0.95]

Es ist aufschlussreich, die Daten und die Lösung zu zeichnen:

Graphics[{Opacity[0.2], EdgeForm[Opacity[0.75]], White, Disk[Most[#], Last[#]] & /@ data, 
  Opacity[1], Red, ellipsoid, 
  PointSize[0.0125], Blue, Point[source], Red, Point[solution],
  PointSize[0.0083], White, Point @ points}, 
  Background -> Black, ImageSize -> 600]

• Die weißen Punkte sind die (bekannten) Zugriffspunkte.

• Der große blaue Punkt ist der wahre Gerätestandort.

• Die grauen Kreise repräsentieren die gemessenen Radien. Im Idealfall kreuzen sie sich alle am tatsächlichen Gerätestandort - dies ist jedoch aufgrund von Messfehlern offensichtlich nicht der Fall.

• Der große rote Punkt gibt den geschätzten Gerätestandort an.

• Die rote Ellipse kennzeichnet einen Vertrauensbereich von 95% für den Gerätestandort.

Die Form der Ellipse ist in diesem Fall von Interesse: Die Ortsunsicherheit ist entlang einer NW-SE-Linie am größten. Hier ändern sich die Entfernungen zu drei Zugangspunkten (nach Nordosten und Südosten) kaum, und es gibt einen Kompromiss zwischen den Entfernungen zu den beiden anderen Zugangspunkten (nach Nordosten und Südosten).

(In einigen Systemen kann ein genauerer Vertrauensbereich als Kontur einer Wahrscheinlichkeitsfunktion erhalten werden; diese Ellipse ist nur eine Annäherung zweiter Ordnung an eine solche Kontur.)

Wenn die Radien fehlerfrei gemessen werden, haben alle Kreise mindestens einen Schnittpunkt, und wenn dieser Punkt eindeutig ist, ist dies die eindeutige Lösung.

Diese Methode funktioniert mit zwei oder mehr Zugangspunkten. Drei oder mehr sind erforderlich, um Konfidenzintervalle zu erhalten. Wenn nur zwei verfügbar sind, wird einer der Schnittpunkte gefunden (sofern vorhanden). Andernfalls wird ein geeigneter Ort zwischen den beiden Zugriffspunkten ausgewählt.

In diesem Fall schneidet jeder Kreis alle anderen Kreise und so können wir die Schnittpunkte folgendermaßen bestimmen:

Bestimmen Sie zuerst alle n * (n-1) Schnittpunkte. Rufen Sie den Satz dieser Schnittpunkt I . Nehmen Sie eine Liste von Punkten T, die die innersten Punkte enthält. Dann überprüfe für jeden Punkt p in I , ob p in jedem Kreis liegt. Befindet sich p in jedem Kreis, so ist dies der Punkt am innersten Schnittpunkt. Fügen Sie der Liste T einen solchen Punkt hinzu .

Jetzt haben Sie die gewünschten Schnittpunktkoordinaten. Ich kann mir mindestens zwei Möglichkeiten vorstellen, um den Ort vorherzusagen:

1. Berechnen Sie einfach den Schwerpunkt (Abstand als Gewicht verwenden?) Des durch T gebildeten Polygons, und der Schwerpunkt ist der gewünschte Ort.
2. Berechnen Sie den minimalen Kreis, der jeden Punkt von T enthält . Dann ist der Mittelpunkt dieses Kreises der gewünschte Ort. Die Berechnung von R sollte danach einfach sein.

Ein weiterer Hinweis: Wandeln Sie zuerst die Signalstärke in die Entfernung um, indem Sie das Freiraumpfadmodell (oder Variationen) verwenden. Mein Ansatz ist: Sie haben einen beliebigen Trainingsdatensatz und sollten versuchen, den Pfadverlustexponenten mithilfe einer Lernmethode zu ermitteln, anstatt n = 2 oder n = 2,2 als festen Wert zu verwenden.