Trilaterationsalgorithmus für n Punkte

27

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

Bildbeschreibung hier eingeben

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.

Kārlis Baumanis
quelle
in welcher sprache arbeitest du
WolfOdrade
Meistens PHP, ein bisschen JavaScript. Ich denke, ich musste das vorher erwähnen, aber ich bin ein Webentwickler und um Whubers Antwort zu verstehen, muss ich einen Mathematiker finden.
Kārlis Baumanis
Werden die Radien von den relativen Signalstärken abgeleitet?
Kirk Kuykendall
Ja! Tatsächlich sind die Radien in dBm
Kārlis Baumanis
1
@ Reddox, teilweise - ich habe es geschafft, es mit php_exec () unter Verwendung von mathematica auf der Serverseite zu berechnen.
Kārlis Baumanis

Antworten:

29

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:

Datentabelle

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]

Konfidenzintervalltabelle

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]

Karte

  • 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.

whuber
quelle
3
Gut gemacht, Bill!
1
@Reddox Im Prinzip ja: Jede Sprache, die vollständig ist, kann buchstäblich jede Berechnung durchführen. Aber PHP wäre eine weit unten stehende Liste von Möglichkeiten für jedermann als Zielsprache. Auch das PHP-Handbuch gibt zu: "PHP ist wahrscheinlich nicht die beste Sprache, um eine Desktop-Anwendung mit einer grafischen Benutzeroberfläche zu erstellen, aber wenn Sie PHP sehr gut kennen und einige erweiterte PHP-Funktionen auf Ihrer Client-Seite nutzen möchten Anwendungen können Sie auch PHP-GTK verwenden, um solche Programme zu schreiben. "
Whuber
1
@ Reddox Danke für den Link. Ich sehe, wie es Geometrierechnungen liefert. Unter diesen Umständen werden diese nicht wirklich benötigt: Die einzige solche Berechnung ist eine Anwendung des pythagoreischen Theorems, um Entfernungen als Wurzelsummen von Quadraten zu erhalten (der Aufruf Normin meinem Code). Die ganze Arbeit ist mit der gewichteten nichtlinearen Anpassung der kleinsten Quadrate verbunden, aber ich glaube nicht, dass die GEOS-Bibliothek diese Fähigkeit bietet. Möglicherweise kann GEOS hilfreich sein, wenn genaue ellipsoide Abstände erforderlich sind.
Whuber
2
Wenn ich das richtig lese, @BenR, scheinen Sie die Daten im Verhältnis zu den quadratischen Radien zu gewichten und nicht umgekehrt proportional zu ihnen. Was passiert , wenn Sie teilen mit , square(data[2])indem sie es anstelle der Multiplikation?
whuber
1

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.

Masum Billal
quelle
Was ist T ... die "innersten Punkte" - wenn ich 5 Knoten habe ... wie viele "innersten Punkte" sollte ich überprüfen?
Ewizard