Emplacement du projet sur un chemin (en grand cercle)

Je fais des recherches sur ce site SE depuis quelques heures maintenant, et j'ai encore du mal à trouver une solution à ma question. Mon objectif est que, étant donné un chemin dans OSM et ma position (coordonnées lat / lon), je veux trouver la position la plus proche (coordonnées lat / lon) de cette façon. Le point peut être n'importe où sur le chemin, sans se limiter aux points utilisés pour définir le chemin.

Je pense donc à l'algorithme suivant:

1. Chemin séparé en arêtes distinctes, chaque arête ne reliant que deux points.
2. Sélectionnez le bord le plus proche.
3. Projetez mon emplacement sur ce bord.

Maintenant, il y a beaucoup de questions sur le calcul de la distance entre un emplacement et un chemin:

• Point WGS sur la distance du segment de ligne WGS (grand cercle)
• Calcul de la distance entre un point et une ligne virtuelle de deux lat / lngs
• Comment approximer la distance point à segment sur la sphère?

Aussi une question très similaire dont je ne peux pas obtenir les calculs corrects ou vérifiés:

• Trouver le point le plus proche sur une ligne

Il y a aussi quelques informations du Dr Math à ce sujet. Cependant, je n'arrive pas à trouver d'algorithme pour calculer l'emplacement à l'étape 3. Comme je n'ai pas touché l'algèbre (vectorielle) depuis un bon moment, je ne comprends pas très bien la logique de ces réponses.

Quelqu'un peut-il montrer un algorithme pour ce faire? Une solution dans n'importe quel langage de programmation raisonnable me convient.

L'utilisation d'un modèle sphérique de la terre peut donner une précision adéquate et conduire à des calculs simples et rapides.

Convertissez toutes les coordonnées en coordonnées cartésiennes centrées sur la Terre (3D). Par exemple, la formule

(cos(lon)*cos(lat), sin(lon)*cos(lat), sin(lat))

ça ira. (Il utilise une mesure de distance dans laquelle le rayon de la Terre est d'une unité, ce qui est pratique.)

Ecrire X0 = (x0, y0, z0) pour le point de départ et X1 = (x1, y1, z1) pour le point de destination, qui définissent le grand cercle (à condition que X0 soit distinct de X1 et que les deux ne soient pas diamétralement opposés), soit U le produit croisé normalisé de X0 et X1. Ceci est calculé en deux étapes:

V = (xv, yv, zv) = (y0*z1 - z0*y1, z0*x1 - x0*z1, x0*y1 - y0*x1)

La longueur de V est

|V| = sqrt(xv^2 + yv^2 + zv^2)

La normalisation étend V à la longueur unitaire:

U = (xu, yu, zu) = V / |V| = (xv/|V|, yv/|V|, zv/|V|).

La distance 3D orientée entre tout point X = (x, y, z) et le plan de ce grand cercle n'est que le produit scalaire de X avec Z, donné par

d = X * U = x*xu + y*yu + z*zu

Le point le plus proche en termes de distance à la surface de la terre est celui qui est le plus proche du plan: il a donc la plus petite valeur absolue de d .

Cette figure montre un grand cercle (en noir) déterminé par les deux points blancs et 2000 points aléatoires sur la sphère colorés et ombrés en fonction de leur distance 3D absolue au plan de ce grand cercle; c'est-à-dire, | d |.

Après avoir trouvé un point le plus proche, projetez-le sur le grand cercle en le projetant d'abord sur le plan du grand cercle (en 3D), puis en l'étendant radialement vers l'extérieur jusqu'à la surface de la terre. La projection soustrait simplement d * U:

X' = (x', y', z') = X - d*U = (x - d*xu, y - d*yu, z - d*zu).

La projection radiale renormalise simplement X 'de la même manière que V est renormalisé en U:

X'' = X' / |X'|.

(Cela sera problématique si | X '| = 0, ce qui se produit lorsque le point le plus proche est l'un des pôles du grand cercle. Incluez un test dans le code de cette condition, si cela peut se produire, et traitez-le séparément, en utilisant le signe de d pour identifier quel pôle.)

Si vous le souhaitez, convertissez les coordonnées de X '' en (lat, lon) en utilisant les formules habituelles .