I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance. My question is, will I get correct results (same nearest neighbor) if I use euclidean distance instead ?
If not, can you give me a concrete example of 3 GPS coordinates (WGS84) where euclidean distance fails to distinguish which coordinate is closer to which ?
1 Answer 1
Short answer: No, you will not get the same results.
It does not matter what coordinate system or what geographic standard you are using, it is not possible to make projection from sphere into rectangle and save all data (angles and distances) at the same time.
Haversine formula is prepared to operate on circles, 3D distance on sphere, while Euclidean distance will treat them as 2D points, so the result must differ.
Haversine is one of methods to get actual distance on sphere, to use it on Earth, it is only approximation so in such case I would suggest Vincenty formula.
The errors depend on coordinates given and the distance between points.
Take reference point $A =\{40^{\circ}N, 40^{\circ}E\} = \{40, 40\},ドル $B =\{42^{\circ}N, 40^{\circ}E\} = \{42, 40\},ドル $C =\{40^{\circ}N, 42^{\circ}E\} = \{40, 42\},ドル treating them as $X, Y$ tells that they are equidistant - this is how Euclidean distance would see raw coordinates.
According to Haversine formula distance from $A$ to $B$ is ~222ドル.4 km$ (~222,108ドル km$ Vincenty), distance from $A$ to $C$ is ~170ドル.4 km$ (~170,784ドル km$ Vincenty), so it kinda fails.
The idea with ruler on the map, this gets heavy, it will fail as the above, but it depends on map projection (errors change, some projections save angles, some tries to save distances).
-
$\begingroup$ Can you give me a concrete example of 3 GPS coordinates (WGS84) where euclidean distance fails to distinguish which coordinate is closer to which ? $\endgroup$dimitris93– dimitris932016年05月18日 23:58:26 +00:00Commented May 18, 2016 at 23:58
-
$\begingroup$ These points are not WGS84 though. Is this true if we converted them to WGS84 ? $\endgroup$dimitris93– dimitris932016年05月19日 11:35:16 +00:00Commented May 19, 2016 at 11:35
-
$\begingroup$ WGS84 is like this: 32.9285723, 25.2859483 $\endgroup$dimitris93– dimitris932016年05月19日 11:47:38 +00:00Commented May 19, 2016 at 11:47
-
$\begingroup$ @Shiro so it like does not matter, this is true in whatever system you choose - it will fail. To do what you want the transform that maps 3D sphere (ellipsoid) into 2D saving everything (both distances and angles) is needed. Such transform does not exist. $\endgroup$Evil– Evil2016年05月19日 14:28:59 +00:00Commented May 19, 2016 at 14:28
Explore related questions
See similar questions with these tags.