1

I have implemented a KD-Tree that stores coordinates (latitude, longitude). I have also implemented a Nearest Neighbor search algorithm using the Haversine distance.

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, for example 32.5321141, 35.23215122) where euclidean distance fails to distinguish which coordinate is closer to which ?

1

How are you defining these "Euclidean distances"? Just using lat-long as x-y cartesian coordinates? That will work fairly well for small areas but at some point you have to realise that the X-coordinates are getting closer together at the poles.

If I'm standing two metres from the north pole my feet could be at maybe 30W and 30E (perhaps I do the splits...), which is 60 angular degree units apart in cartesian lat-long. But the north pole is only some tiny fraction of a degree unit in front of my feet. A euclidean distance algorithm would think my feet are thousands of times further apart than the distance from my feet to the pole.

Yes its extreme up here with the polar bears, but the spherical earth can muck up your distance calculations anywhere except on the equator.

Transform to a reasonable cartesian coordinate system if your data is in a small area, or use the full spherical distance.

  • Euclidean distance of (32.5, 30.5), (40.7, 20.5) is sqrt((32.5 - 40.7)^2 + (30.5 - 20.5)^2) . Can you please give me 3 coordinates where euclidean distance decides that A is closer to B than C, and it is wrong ? I can't find an example like this. Things like "angular degree" and "30W and 30E" doesn't make sense to me. I am not familiar with GIS. This KD-Tree is used for a routing engine. So if the problem is at very top of the map (the poles) I really doubt I will be calculating routes that involve the poles. – dimitris93 May 19 '16 at 12:05
  • 1
    The problem is worse at the poles, it exists everywhere, fading to zero on the equator. Its much easier to illustrate it at the pole, since the difference in lat-long is so plain. The other problem with Euclidean distances like this is at the +180 line, half way round the world, where the coordinates suddenly jump to -180. – Spacedman May 19 '16 at 16:32
  • Hmm...... I see what you are saying. That is a problem. – dimitris93 May 19 '16 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.