Comment calculer la distance d'un point à un segment de droite, sur une sphère?
https://stackoverflow.com/questions/1299567
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai un segment de ligne (grande partie du cercle) sur la terre. Le segment de ligne est définie par les coordonnées de ses extrémités. De toute évidence, deux points définissent deux segments de ligne, donc je suppose suis intéressé par le plus court.
Je me donne un troisième point, et je suis à la recherche de la distance (la plus courte) entre la ligne et le point.
Toutes les coordonnées sont données en longitude \ latitude (WGS 84).
Comment calculer la distance?
Une solution dans toutes les langues de programmation raisonnable fera.
La solution
Voici ma propre solution, basée sur l'idée demander au Dr Math . Je serais heureux de voir vos commentaires.
Disclaimer premier. Cette solution est correcte pour les sphères. La Terre est pas une sphère, et le système de coordonnées (WGS 84) ne suppose pas que c'est une sphère. Donc, ceci est juste une approximation, et je ne peux pas vraiment estimer est une erreur. En outre, pour de très petites distances, il est probablement possible d'obtenir une bonne approximation en supposant que tout est juste un coplanaires. Encore une fois, je ne sais pas comment les distances « petits » doivent être.
pour les entreprises. Je vais appeler les extrémités des lignes A, B et le troisième point C. En fait, l'algorithme est le suivant:
- convertir les coordonnées cartésiennes en coordonnées première (à l'origine au centre de la terre) - par exemple, .
-
Calculer T, le point sur la ligne AB qui est le plus proche de C, en utilisant les produits vectoriels 3 ci-dessous:
G = A x B
F = C x G
T = G x F
-
Normaliser T et multiplier par le rayon de la terre.
- Convertir T Retour à la longitude \ latitude.
- calculer la distance entre T et C - par exemple, .
Ces étapes suffisent si vous cherchez la distance entre C et le grand cercle défini par A et B. Si comme moi vous êtes intéressé par la distance entre C et le segment de ligne plus courte, vous devez prendre l'étape supplémentaire de vérifier que T est en effet sur ce segment. Dans le cas contraire, alors nécessairement le point le plus proche est l'une des extrémités A ou B - la meilleure façon est de vérifier que l'on.
En termes généraux, l'idée derrière les trois produits vectoriels est le suivant. La première (G) nous donne le plan du grand cercle de A et B (de sorte que le plan contenant A, B et l'origine). Le second (F) nous donne le grand cercle de la traverse C et est perpendiculaire à l'G. Alors T est l'intersection des grands cercles définis par F et G, porté à la bonne longueur par la normalisation et de la multiplication par r.
Voici un code Java partiel pour le faire.
Trouver le point le plus proche du grand cercle. Les entrées et les sorties sont des tableaux de longueur-2. Les réseaux intermédiaires sont de longueur 3.
double[] nearestPointGreatCircle(double[] a, double[] b, double c[])
{
double[] a_ = toCartsian(a);
double[] b_ = toCartsian(b);
double[] c_ = toCartsian(c);
double[] G = vectorProduct(a_, b_);
double[] F = vectorProduct(c_, G);
double[] t = vectorProduct(G, F);
normalize(t);
multiplyByScalar(t, R_EARTH);
return fromCartsian(t);
}
Trouver le point le plus proche sur le segment:
double[] nearestPointSegment (double[] a, double[] b, double[] c)
{
double[] t= nearestPointGreatCircle(a,b,c);
if (onSegment(a,b,t))
return t;
return (distance(a,c) < distance(b,c)) ? a : c;
}
Ceci est une méthode simple de test si le point T, que nous connaissons est sur le même grand cercle A et B, est sur le segment plus court de ce grand cercle. Cependant, il existe des méthodes plus efficaces pour le faire:
boolean onSegment (double[] a, double[] b, double[] t)
{
// should be return distance(a,t)+distance(b,t)==distance(a,b),
// but due to rounding errors, we use:
return Math.abs(distance(a,b)-distance(a,t)-distance(b,t)) < PRECISION;
}
Autres conseils
Distance d'un point à un grand cercle , de demander au Dr . Math. Vous avez encore besoin de transformer la longitude / latitude aux coordonnées sphériques et échelle pour le rayon de la terre, mais cela semble être une bonne direction.
est un code complet pour réponse acceptée comme ideone violon (trouvé ):
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
private static final double _eQuatorialEarthRadius = 6378.1370D;
private static final double _d2r = (Math.PI / 180D);
private static double PRECISION = 0.1;
// Haversine Algorithm
// source: http://stackoverflow.com/questions/365826/calculate-distance-between-2-gps-coordinates
private static double HaversineInM(double lat1, double long1, double lat2, double long2) {
return (1000D * HaversineInKM(lat1, long1, lat2, long2));
}
private static double HaversineInKM(double lat1, double long1, double lat2, double long2) {
double dlong = (long2 - long1) * _d2r;
double dlat = (lat2 - lat1) * _d2r;
double a = Math.pow(Math.sin(dlat / 2D), 2D) + Math.cos(lat1 * _d2r) * Math.cos(lat2 * _d2r)
* Math.pow(Math.sin(dlong / 2D), 2D);
double c = 2D * Math.atan2(Math.sqrt(a), Math.sqrt(1D - a));
double d = _eQuatorialEarthRadius * c;
return d;
}
// Distance between a point and a line
public static void pointLineDistanceTest() {
//line
//double [] a = {50.174315,19.054743};
//double [] b = {50.176019,19.065042};
double [] a = {52.00118, 17.53933};
double [] b = {52.00278, 17.54008};
//point
//double [] c = {50.184373,19.054657};
double [] c = {52.008308, 17.542927};
double[] nearestNode = nearestPointGreatCircle(a, b, c);
System.out.println("nearest node: " + Double.toString(nearestNode[0]) + "," + Double.toString(nearestNode[1]));
double result = HaversineInM(c[0], c[1], nearestNode[0], nearestNode[1]);
System.out.println("result: " + Double.toString(result));
}
// source: http://stackoverflow.com/questions/1299567/how-to-calculate-distance-from-a-point-to-a-line-segment-on-a-sphere
private static double[] nearestPointGreatCircle(double[] a, double[] b, double c[])
{
double[] a_ = toCartsian(a);
double[] b_ = toCartsian(b);
double[] c_ = toCartsian(c);
double[] G = vectorProduct(a_, b_);
double[] F = vectorProduct(c_, G);
double[] t = vectorProduct(G, F);
return fromCartsian(multiplyByScalar(normalize(t), _eQuatorialEarthRadius));
}
@SuppressWarnings("unused")
private static double[] nearestPointSegment (double[] a, double[] b, double[] c)
{
double[] t= nearestPointGreatCircle(a,b,c);
if (onSegment(a,b,t))
return t;
return (HaversineInKM(a[0], a[1], c[0], c[1]) < HaversineInKM(b[0], b[1], c[0], c[1])) ? a : b;
}
private static boolean onSegment (double[] a, double[] b, double[] t)
{
// should be return distance(a,t)+distance(b,t)==distance(a,b),
// but due to rounding errors, we use:
return Math.abs(HaversineInKM(a[0], a[1], b[0], b[1])-HaversineInKM(a[0], a[1], t[0], t[1])-HaversineInKM(b[0], b[1], t[0], t[1])) < PRECISION;
}
// source: http://stackoverflow.com/questions/1185408/converting-from-longitude-latitude-to-cartesian-coordinates
private static double[] toCartsian(double[] coord) {
double[] result = new double[3];
result[0] = _eQuatorialEarthRadius * Math.cos(Math.toRadians(coord[0])) * Math.cos(Math.toRadians(coord[1]));
result[1] = _eQuatorialEarthRadius * Math.cos(Math.toRadians(coord[0])) * Math.sin(Math.toRadians(coord[1]));
result[2] = _eQuatorialEarthRadius * Math.sin(Math.toRadians(coord[0]));
return result;
}
private static double[] fromCartsian(double[] coord){
double[] result = new double[2];
result[0] = Math.toDegrees(Math.asin(coord[2] / _eQuatorialEarthRadius));
result[1] = Math.toDegrees(Math.atan2(coord[1], coord[0]));
return result;
}
// Basic functions
private static double[] vectorProduct (double[] a, double[] b){
double[] result = new double[3];
result[0] = a[1] * b[2] - a[2] * b[1];
result[1] = a[2] * b[0] - a[0] * b[2];
result[2] = a[0] * b[1] - a[1] * b[0];
return result;
}
private static double[] normalize(double[] t) {
double length = Math.sqrt((t[0] * t[0]) + (t[1] * t[1]) + (t[2] * t[2]));
double[] result = new double[3];
result[0] = t[0]/length;
result[1] = t[1]/length;
result[2] = t[2]/length;
return result;
}
private static double[] multiplyByScalar(double[] normalize, double k) {
double[] result = new double[3];
result[0] = normalize[0]*k;
result[1] = normalize[1]*k;
result[2] = normalize[2]*k;
return result;
}
public static void main(String []args){
System.out.println("Hello World");
Ideone.pointLineDistanceTest();
}
}
Il fonctionne très bien pour les données a commenté:
//line
double [] a = {50.174315,19.054743};
double [] b = {50.176019,19.065042};
//point
double [] c = {50.184373,19.054657};
noeud le plus proche: 50.17493121381319,19.05846668493702
Mais j'ai problème avec ces données:
double [] a = {52.00118, 17.53933};
double [] b = {52.00278, 17.54008};
//point
double [] c = {52.008308, 17.542927};
nœud le plus proche est: 52.00834987257176,17.542691313436357 ce qui est faux
.Je pense que la ligne spécifiée par deux points ne sont pas un segment fermé.
Si quelqu'un a besoin de cette réponse est loleksy porté à c #
private static double _eQuatorialEarthRadius = 6378.1370D;
private static double _d2r = (Math.PI / 180D);
private static double PRECISION = 0.1;
// Haversine Algorithm
// source: http://stackoverflow.com/questions/365826/calculate-distance-between-2-gps-coordinates
private static double HaversineInM(double lat1, double long1, double lat2, double long2) {
return (1000D * HaversineInKM(lat1, long1, lat2, long2));
}
private static double HaversineInKM(double lat1, double long1, double lat2, double long2) {
double dlong = (long2 - long1) * _d2r;
double dlat = (lat2 - lat1) * _d2r;
double a = Math.Pow(Math.Sin(dlat / 2D), 2D) + Math.Cos(lat1 * _d2r) * Math.Cos(lat2 * _d2r)
* Math.Pow(Math.Sin(dlong / 2D), 2D);
double c = 2D * Math.Atan2(Math.Sqrt(a), Math.Sqrt(1D - a));
double d = _eQuatorialEarthRadius * c;
return d;
}
// Distance between a point and a line
static double pointLineDistanceGEO(double[] a, double[] b, double[] c)
{
double[] nearestNode = nearestPointGreatCircle(a, b, c);
double result = HaversineInKM(c[0], c[1], nearestNode[0], nearestNode[1]);
return result;
}
// source: http://stackoverflow.com/questions/1299567/how-to-calculate-distance-from-a-point-to-a-line-segment-on-a-sphere
private static double[] nearestPointGreatCircle(double[] a, double[] b, double [] c)
{
double[] a_ = toCartsian(a);
double[] b_ = toCartsian(b);
double[] c_ = toCartsian(c);
double[] G = vectorProduct(a_, b_);
double[] F = vectorProduct(c_, G);
double[] t = vectorProduct(G, F);
return fromCartsian(multiplyByScalar(normalize(t), _eQuatorialEarthRadius));
}
private static double[] nearestPointSegment (double[] a, double[] b, double[] c)
{
double[] t= nearestPointGreatCircle(a,b,c);
if (onSegment(a,b,t))
return t;
return (HaversineInKM(a[0], a[1], c[0], c[1]) < HaversineInKM(b[0], b[1], c[0], c[1])) ? a : b;
}
private static bool onSegment (double[] a, double[] b, double[] t)
{
// should be return distance(a,t)+distance(b,t)==distance(a,b),
// but due to rounding errors, we use:
return Math.Abs(HaversineInKM(a[0], a[1], b[0], b[1])-HaversineInKM(a[0], a[1], t[0], t[1])-HaversineInKM(b[0], b[1], t[0], t[1])) < PRECISION;
}
// source: http://stackoverflow.com/questions/1185408/converting-from-longitude-latitude-to-cartesian-coordinates
private static double[] toCartsian(double[] coord) {
double[] result = new double[3];
result[0] = _eQuatorialEarthRadius * Math.Cos(deg2rad(coord[0])) * Math.Cos(deg2rad(coord[1]));
result[1] = _eQuatorialEarthRadius * Math.Cos(deg2rad(coord[0])) * Math.Sin(deg2rad(coord[1]));
result[2] = _eQuatorialEarthRadius * Math.Sin(deg2rad(coord[0]));
return result;
}
private static double[] fromCartsian(double[] coord){
double[] result = new double[2];
result[0] = rad2deg(Math.Asin(coord[2] / _eQuatorialEarthRadius));
result[1] = rad2deg(Math.Atan2(coord[1], coord[0]));
return result;
}
// Basic functions
private static double[] vectorProduct (double[] a, double[] b){
double[] result = new double[3];
result[0] = a[1] * b[2] - a[2] * b[1];
result[1] = a[2] * b[0] - a[0] * b[2];
result[2] = a[0] * b[1] - a[1] * b[0];
return result;
}
private static double[] normalize(double[] t) {
double length = Math.Sqrt((t[0] * t[0]) + (t[1] * t[1]) + (t[2] * t[2]));
double[] result = new double[3];
result[0] = t[0]/length;
result[1] = t[1]/length;
result[2] = t[2]/length;
return result;
}
private static double[] multiplyByScalar(double[] normalize, double k) {
double[] result = new double[3];
result[0] = normalize[0]*k;
result[1] = normalize[1]*k;
result[2] = normalize[2]*k;
return result;
}
Pour la distance jusqu'à quelques milliers de mètres je simplifierait la question de la sphère au plan. Ensuite, la question est assez simple comme calcul de triangle facile peut être utilisé:
Nous avons des points A et B et recherchez une distance X à la ligne AB. Puis:
Location a;
Location b;
Location x;
double ax = a.distanceTo(x);
double alfa = (Math.abs(a.bearingTo(b) - a.bearingTo(x))) / 180
* Math.PI;
double distance = Math.sin(alfa) * ax;
La distance la plus courte entre deux points sur une sphère est le plus petit côté du grand cercle passant par les deux points. Je suis sûr que vous le savez déjà. Il y a une question similaire ici http://www.physicsforums.com/ archives / index.php / t-178252.html qui peuvent vous aider à modéliser mathmatically.
Je ne sais pas comment vous êtes susceptible d'obtenir un exemple de code cela, pour être honnête.
Je cherche essentiellement la même chose en ce moment, sauf que je parle strictement ne se soucient pas d'avoir un segment d'un grand cercle, mais je veux juste la distance à un point quelconque sur le cercle complet.
Deux liens J'enquêtent actuellement sur:
Cette page mentionne "la distance inter-piste", qui semble essentiellement être ce que vous recherchez.
En outre, dans la discussion suivante sur la liste de diffusion PostGIS, la tentative semble (1) déterminer le point le plus proche sur le grand cercle avec la même formule utilisée pour la ligne de fond sur un plan 2D (avec line_locate_point « PostGIS) et ensuite (2) le calcul de la distance entre cela et le troisième point sur un sphéroïde. Je ne sais pas si mathématiquement étape (1) est correct, mais je serais surpris.
http://postgis.refractions.net/pipermail /postgis-users/2009-July/023903.html
Enfin, je viens de voir que les éléments suivants liés à la rubrique « connexes »:
Distance du point à la ligne grande fonction de cercle ne fonctionne pas correctement.
