Suite

Algorithme de génération de réseau

Algorithme de génération de réseau


J'essaye de résoudre un problème de génération de réseau, et je serais content des entrées. Tout d'abord, la description de mon problème :

J'ai une liste de connexions entre les emplacements avec des distances respectives. Par exemple:

EmplacementA <-> EmplacementB : 4500 m EmplacementB <-> EmplacementC : 3000 m EmplacementC <-> EmplacementA : 2000 m… et ainsi de suite…

Ce que je ne sais pas, mais essayez de le découvrir : La position géographique réelle de mes emplacements. Je connais la position de quelques nœuds dans le réseau, et étant donné une longue liste de connexions avec des distances, je devrais pouvoir trouver approximativement les positions de mes emplacements inconnus.

Remarque : je suis ne pas essayer d'optimiser réellement tous les chemins au sein de ce réseau (par exemple, Dijkstra, etc.). Je voudrais simplement savoir quelles sont les coordonnées géographiques des nœuds de mon système.

Ma question est la suivante : quelle sorte d'"algorithme de placement de nœuds" suis-je à la recherche ? Je serais heureux pour tous les mots clés à cet égard. Je suis sûr à 100% qu'il existe des algorithmes pour ce problème, mais je ne sais même pas quoi rechercher.


Comme on peut le voir sur cette photo

Pour chaque point inconnu, vous aurez besoin de distances à 3 points avec des coordonnées connues. Je commencerais donc par la triangulation de points connus. J'espère que le reste du processus est clair à partir de l'image.

Remarque : en raison d'imprécisions dans les distances par rapport à des points connus, vous devrez gérer 6 points. Vous devrez en désherber 3, le centre des 3 restants sera votre point inconnu. Il existe plusieurs techniques pour supprimer les valeurs aberrantes. Personnellement, je préfère le peeling à coque convexe.

Malheureusement, cela fonctionnera pour les inconnus assis à l'intérieur du triangle. Si c'est à l'extérieur :

Vous devrez trouver 3 points avec des distances totales minimales les uns par rapport aux autres