Come calcolare la distanza da un punto ad un segmento di linea, su una sfera?
https://stackoverflow.com/questions/1299567
-
18-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Ho un segmento di linea (cerchio grande parte) sulla terra. Il segmento di linea è definita dalle coordinate dei suoi estremi. Ovviamente, due punti definiscono due segmenti di linea, in modo da assumere Sono interessato in quello più corto.
mi viene data un terzo punto, e sto cercando il (breve) distanza tra la linea e il punto.
Tutte le coordinate sono date in longitudine \ latitudine (WGS 84).
Come faccio a calcolare la distanza?
Una soluzione in qualsiasi linguaggio di programmazione ragionevole farà.
Soluzione
Ecco la mia propria soluzione, basata sull'idea di chiedere Dr. Math . Sarei felice di vedere il tuo feedback.
di responsabilità prima. Questa soluzione è corretta per le sfere. Terra non è una sfera, e il sistema di coordinate (WGS 84) non si assume che sia una sfera. Quindi, questo è solo un'approssimazione, e non posso davvero stimare è errore. Inoltre, per distanze molto piccole, probabilmente è anche possibile ottenere una buona approssimazione assumendo tutto è un solo un complanare. Anche in questo caso non so come "piccolo" le distanze devono essere.
Ora per affari. Chiamerò le estremità delle linee A, B e il terzo punto C. In pratica, l'algoritmo è:
- convertire le coordinate primo coordinate cartesiane (con l'origine nel centro della terra) - es qui .
-
Calcolare T, il punto della linea AB che è più vicina a C, utilizzando i prodotti seguenti 3 vettore:
G = A x B
F = C x G
T = G x F
-
Normalizza T e moltiplicare per il raggio di terra.
- Converti T torna a longitudine \ latitudine.
- calcolare la distanza tra T e C - esempio qui .
Questi passaggi sono sufficienti se si sta cercando per la distanza tra C e il grande cerchio definito da A e B. Se come me siete interessati la distanza tra C e il segmento di linea più breve, è necessario prendere il passo in più di verificare che T è davvero su questo segmento. Se non lo è, allora necessariamente il punto più vicino è una delle estremità A o B - il modo più semplice è quello di verificare quale.
In termini generali, l'idea alla base dei tre prodotti vettore è il seguente. Il primo (G) ci dà il piano del cerchio di A e B (in modo che il piano contenente A, B e l'origine). Il secondo (F) ci dà la grande cerchio passa attraverso C ed è perpendicolare al G. Allora T è l'intersezione dei cerchi massimi definiti da F e G, portati alla lunghezza corretta normalizzazione e moltiplicazione per R.
Ecco un po 'di codice Java parziale per farlo.
Trovare il punto più vicino il grande cerchio. Gli ingressi e uscita sono di lunghezza-2 array. Gli array intermedi sono di lunghezza 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);
}
Trovare il punto più vicino al segmento:
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;
}
Questo è un semplice metodo di prova se il punto T, che come sappiamo è sullo stesso cerchio di A e B, si trova sul segmento più breve di questo grande cerchio. Tuttavia ci sono metodi più efficaci per farlo:
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;
}
Altri suggerimenti
distanza da un punto a un cerchio massimo , dal Chiedi Dr . Matematica. Hai ancora bisogno di trasformare la longitudine / latitudine di coordinate sferiche e la scala per il raggio della terra, ma questo mi sembra una buona direzione.
Questo è il codice completo per risposta accettata come Ideone violino (trovato qui ):
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();
}
}
Funziona bene per i dati commentato:
//line
double [] a = {50.174315,19.054743};
double [] b = {50.176019,19.065042};
//point
double [] c = {50.184373,19.054657};
nodo più vicino è: 50.17493121381319,19.05846668493702
Ma ho problemi con questi dati:
double [] a = {52.00118, 17.53933};
double [] b = {52.00278, 17.54008};
//point
double [] c = {52.008308, 17.542927};
nodo più vicina è: 52.00834987257176,17.542691313436357 che è sbagliato
.Credo che la linea indicata da due punti non è un segmento chiuso.
Se qualcuno ha bisogno in questo è la risposta loleksy portato su 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;
}
Per distanza fino a un paio di migliaia di metri vorrei semplificare il problema di sfera in aereo. Quindi, la questione è abbastanza semplicemente come un semplice calcolo triangolo può essere utilizzato:
Abbiamo i punti A e B e cerchiamo una distanza X per la linea AB. Poi:
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 distanza più breve tra due punti su una sfera è il lato minore del cerchio massimo passante per i due punti. Sono sicuro che lo sanno già. V'è una domanda simile qui http://www.physicsforums.com/ archive / index.php / t-178252.html che possono aiutare a modellare mathmatically.
Non sono sicuro di come sarà la probabilità di ottenere un esempio di codice di questo, ad essere onesti.
Sono fondamentalmente cercando la stessa cosa in questo momento, se non che a rigor di termini non si preoccupano di avere un segmento di un grande cerchio, ma vogliono solo la distanza da qualsiasi punto del cerchio completo.
Due collegamenti sto attualmente indagando:
Questa pagina parla di "distanza di cross-track", che sembra fondamentalmente per essere quello che stai cercando.
Inoltre thread sulla mailing list PostGIS, il tentativo sembra (1) determinare il punto più vicino sul grande cerchio con la stessa formula utilizzata per la linea-distanza su un 2D-plane (con line_locate_point PostGIS') , e poi (2) calcolare la distanza tra questo e il terzo punto su una sferoide. Non ho idea se matematicamente punto (1) è corretto, ma sarei sorpreso.
http://postgis.refractions.net/pipermail /postgis-users/2009-July/023903.html
Infine, ho appena visto che i seguenti legata alla voce "correlate":
distanza dal punto di alla linea di grande funzione cerchio non funziona bene.
