Emplacement du projet sur un chemin (en grand cercle)

9

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:

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

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.

bouke
la source
1
Puisqu'il semble essentiel à votre "rejet" des autres questions, veuillez élaborer sur "projeter mon emplacement sur ce bord". La projection n'est peut-être pas sur le bord. Je pense que cette question est abordée dans les autres questions. (Bravo, pour la recherche, BTW.)
Martin F
@MartinF cette question calcule la distance d'un point à une ligne, mais pas le point le plus proche sur la ligne elle-même.
bouke
Il existe une solution sur gis.stackexchange.com/a/23500/3195 bien qu'elle soit peut - être difficile à comprendre.
Martin F
Ah oui merci, j'ai mis à jour ref non. 3. La «solution» de cette question particulière renvoie à une explication générale du champ du problème. Bien que cela puisse être suffisant pour des mathématiciens bien fondés, je ne comprends pas très bien les mathématiques dans cet article.
bouke

Réponses:

7

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 .

Figure

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 .

whuber
la source
Une question. Considérons le cas non trop inhabituel où nous pouvons choisir n'importe quel X1 et X0 (sur le grand cercle), d'un point de vue de la précision, est-il préférable de choisir X1 et X0 de près ou de loin (à nouveau à condition que X0 soit distinct de X1 et les deux ne sont pas diamétralement opposés)?
user189035
1
@ user189035 Choisissez-les à 90 degrés l'un de l'autre. Lorsqu'ils sont très proches, leur produit croisé est numériquement incertain: il y a beaucoup d'annulations dans les soustractions, entraînant la perte de chiffres significatifs.
whuber