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 ?
Best Answer
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.