4 ms·
When you're evaluating datastructures to quickly get the nearest neighbor in constant time, and you're dealing with actual longitude and latitude, you really ne
by pimmen 8y ago
When you're evaluating datastructures to quickly get the nearest neighbor in constant time, and you're dealing with actual longitude and latitude, you really need to be aware of this so that you don't accidentally pick something that only works for euclidean distances.
- jacobolus 8y agoIf you just want nearest neighbor, I would recommend storing floating point (x, y, z) coordinates, and using Euclidean distance in 3-space. (Or rather, the square of distance Δx² + Δy² + Δz²; skip the square root.) If you want to save storage space / bandwidth, you can use the stereographic projection onto a plane and then cut the precision of the floating-point numbers. Stereographic projection / inverse stereographic projection only requires 1 division per point. Latitude/longitude is quite an inefficient and cumbersome way of representing points on a sphere, though it’s convenient if navigating using the stars.
- kardos 8y ago> Latitude/longitude is quite an inefficient and cumbersome way of representing points on a sphere Using lat/lon absolves you of storing projection metadata
- jacobolus 8y agohttps://en.wikipedia.org/wiki/Latitude#Geodetic_and_geocentric_latitudes https://en.wikipedia.org/wiki/Latitude#Geodetic_and_geocentr... “The definition must be accompanied with a specification of the ellipsoid.” etc.
- tgb 8y agoI think this is misleading or misstated. Haversine distance of points on a sphere is a monotonic function of euclidean distance, so one's nearest neighbor is the same in both. You must be warning people not to just take the sum of square differences on the actual latitude and longitude values.