Algorithme de trilatération pour n nombre de points

27

Je dois trouver un algorithme qui peut calculer le centroïde A (alias centre de gravité, centre géométrique, centre de masse) à partir de la figure où les cercles T1, T2, T3, T4, T5, .., Tn se coupent ET la longueur de la ligne R du centroïde à coin le plus éloigné de la figure mentionnée

Les informations suivantes sont fournies:

  • T1 Latitude = 56,999883 Longitude = 24,144473 Rayon = 943
  • T2 Latitude = 57,005352 Longitude = 24,151168 Rayon = 857
  • T3 Latitude = 57,005352 Longitude = 24,163356 Rayon = 714
  • T4 Latitude = 56,999042 Longitude = 24,168506 Rayon = 714
  • T5 Latitude = 56,994226 Longitude = 24,15709 Rayon = 771

Le résultat devrait ressembler à ceci: A Latitude = XX.XXXXXXX Longitude = XX.XXXXXXX Rayon = XX

entrez la description de l'image ici

Comme vous l'avez probablement déjà compris, je travaille sur un logiciel qui peut trouver l'emplacement de l'appareil par les points d'accès Wifi ou les stations de base mobiles les plus proches, car le nombre de points d'accès ou de stations de base peut changer, j'ai besoin d'un algorithme qui peut s'adapter à une quantité incertaine de points .

Il y a des questions similaires ici et ici , mais aucune d'entre elles ne répond exactement à ma question.

Kārlis Baumanis
la source
dans quelle langue travaillez-vous?
WolfOdrade
Principalement PHP, un peu de JavaScript. Je suppose que je devais le mentionner auparavant, mais je suis développeur Web et pour comprendre la réponse de Whuber, je devrai trouver un mathématicien.
Kārlis Baumanis
Les rayons sont-ils dérivés des intensités relatives du signal?
Kirk Kuykendall
Oui! En fait, les rayons sont en dBm
Kārlis Baumanis
1
@Reddox, en partie - j'ai réussi à le calculer avec php_exec () en utilisant mathématique sur le côté serveur.
Kārlis Baumanis

Réponses:

29

Les mesures de rayon sont sûrement sujettes à une erreur. Je m'attendrais à ce que la quantité d'erreur soit proportionnelle aux rayons eux-mêmes. Supposons que les mesures soient par ailleurs non biaisées. Une solution raisonnable utilise alors l' ajustement des moindres carrés non linéaires pondéré , avec des poids inversement proportionnels aux rayons carrés.

Ce sont des choses standard disponible dans (entre autres) Python, R, Mathematica , et de nombreux progiciels statistiques complet, donc je vais l' illustrer. Voici quelques données obtenues en mesurant les distances, avec une erreur relative de 10%, à cinq points d'accès aléatoires entourant l'emplacement de l'appareil:

Tableau de données

Mathematica a besoin d'une seule ligne de code et d'aucun temps CPU mesurable pour calculer l'ajustement:

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

Modifier--

Pour les grands rayons, des solutions plus précises (sphériques ou ellipsoïdales) peuvent être trouvées simplement en remplaçant la distance euclidienne Norm[{x, y} - {x0, y0}]par une fonction pour calculer la distance sphérique ou ellipsoïdale. Dans Mathematica, cela pourrait être fait, par exemple , via

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

- fin de l'édition

Un avantage de l'utilisation d'une technique statistique comme celle-ci est qu'elle peut produire des intervalles de confiance pour les paramètres (qui sont les coordonnées de l'appareil) et même une ellipse de confiance simultanée pour l'emplacement de l'appareil.

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

Tableau des intervalles de confiance

Il est instructif de tracer les données et la solution:

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]

Carte

  • Les points blancs sont les emplacements (connus) des points d'accès.

  • Le gros point bleu est le véritable emplacement de l'appareil.

  • Les cercles gris représentent les rayons mesurés. Idéalement, ils se croiseraient tous à l'emplacement réel de l'appareil - mais évidemment, ils ne le font pas, en raison d'une erreur de mesure.

  • Le gros point rouge est l'emplacement estimé de l'appareil.

  • L'ellipse rouge délimite une région de confiance à 95% pour l'emplacement de l'appareil.

La forme de l'ellipse dans ce cas est intéressante: l'incertitude de localisation est la plus grande le long d'une ligne NW-SE. Ici, les distances à trois points d'accès (au NE et au SO) changent à peine et il y a un compromis d'erreurs entre les distances aux deux autres points d'accès (au nord et au sud-est).

(Une région de confiance plus précise peut être obtenue dans certains systèmes comme contour d'une fonction de vraisemblance; cette ellipse n'est qu'une approximation de second ordre d'un tel contour.)

Lorsque les rayons sont mesurés sans erreur, tous les cercles auront au moins un point d'intersection mutuelle et - si ce point est unique - ce sera la solution unique.

Cette méthode fonctionne avec deux points d'accès ou plus. Trois ou plus sont nécessaires pour obtenir des intervalles de confiance. Lorsque seulement deux sont disponibles, il trouve l'un des points d'intersection (s'ils existent); sinon, il sélectionne un emplacement approprié entre les deux points d'accès.

whuber
la source
3
Bravo Bill!
1
@Reddox En principe, oui: tout langage complet de turing peut faire littéralement n'importe quel calcul. Mais PHP serait en bas de la liste des choix de quiconque comme langue cible. Même le manuel PHP l' admet: "PHP n'est probablement pas le meilleur langage pour créer une application de bureau avec une interface utilisateur graphique, mais si vous connaissez très bien PHP, et que vous souhaitez utiliser certaines fonctionnalités avancées de PHP dans votre côté client vous pouvez également utiliser PHP-GTK pour écrire de tels programmes. "
whuber
1
@Reddox Merci pour le lien. Je vois comment il fournit des calculs de géométrie. Dans ce cas, ceux-ci ne sont pas vraiment nécessaires: le seul calcul de ce type est une application du théorème de Pythagore pour obtenir des distances en tant que sommes racines de carrés (l'appel à Normdans mon code). Tout le travail est impliqué dans l'ajustement des moindres carrés non linéaires pondérés, mais je ne pense pas que la bibliothèque GEOS offre cette capacité. GEOS pourrait être d'une certaine utilité lorsque des distances ellipsoïdales précises sont nécessaires.
whuber
2
Si je lis bien, @BenR, il semble que vous pondérez les données proportionnellement aux rayons carrés plutôt qu'inversement proportionnels à eux. Que se passe-t-il lorsque vous divisez par square(data[2])au lieu de multiplier par lui?
whuber
1

Dans ce cas, chaque cercle intersecte tous les autres cercles et nous pouvons donc déterminer les points d'intersection de cette façon:

Déterminez d'abord tous les points d'intersection n * (n-1). Appelez l'ensemble de ces points d'intersection I . Prenez une liste de points T qui contient les points les plus intérieurs. Ensuite, pour chaque point p dans I , vérifiez si p est à l'intérieur de chaque cercle. Si p est à l'intérieur de chaque cercle, c'est le point sur l'intersection la plus intérieure. Ajouter un tel point à la liste T .

Vous avez maintenant les coordonnées d'intersection souhaitées. Je peux penser à au moins deux façons de prédire l'emplacement:

  1. Il suffit de calculer le centroïde (utiliser la distance comme poids?) Du polygone formé par T et le centroïde est l'emplacement souhaité.
  2. Calculer le cercle minimum qui contient tous les points de T . Ensuite, le centre de ce cercle est l'emplacement souhaité. Le calcul de R devrait être simple après cela.

Autre remarque: convertissez d'abord la force du signal en distance à l'aide d'un modèle de trajet d'espace libre (ou de variations). Ma position est la suivante: vous avez un ensemble de données d'apprentissage, vous devriez essayer de trouver l'exposant de perte de chemin en utilisant une technique d'apprentissage au lieu d'utiliser n = 2 ou n = 2.2 comme valeur fixe.

Masum Billal
la source
qu'est-ce que T ... les "points les plus intimes" - si j'ai 5 nœuds ... combien de "points les plus intimes" dois-je rechercher?
ewizard