# Finding nearest neighbors of each coordinate

I've got a list of coordinates (WGS1984 Decimal Degree) and have started work on a program that performs a DBSCAN on them to find clusters amongst them. To perform the DBSCAN's range query to determine the neighbors within a specified distance, I converted each point into ECEF using formulas from here. I then built a KD Tree to store them.

Is using a KD Tree the best method for this? I am having trouble traversing the tree because points that are clearly within the neighborhood of others are not being found.

Of note, I use the Haversine formula to determine if a point is to be added to a cluster or not, not the square distance between the two ECEF points.

• Can you test the KD Tree with dummy data to make sure your implementation is correct? Sep 14, 2017 at 15:41
• @MarcPfister I think the KD Tree is likely implemented wrong. I've been messing with it switching between converting the lat/lon to x/y so that I can use square distance to find points, then just to check via `Haversine` before adding to a cluster. Can you use KD Trees with lat/lon without a conversion to another coordinate system? Sep 14, 2017 at 15:55
• I don't see why you couldn't use lat/lon. Maybe compare against `PyQuadTree` or even a geohash implementation? Sep 14, 2017 at 16:07
• @MarcPfister Well I thought it was because of the square distance calculation. If a point is (11.8845, 126.1885) [lat/lon] and I want to search within a 2km radius for neighbor points, decimal degrees does not translate directly to linear distances. So that's why I had to convert to ECEF. Sep 14, 2017 at 16:38
• You just need to find possible candidates to test so I would think you can approximate and err on overshooting. Sep 14, 2017 at 16:53

I think you don't need the ECEF conversion and the k-d tree.

Only implement this algorithm with the Haversine distance function:

https://github.com/chrisjmccormick/dbscan

• So most of that is already included, its not the DBSCAN that is the problem. The reason I would try to avoid that `rangeQuery()` implementation is because that forces the overall program to run at `O(N^2)` complexity. A BST would be faster to eliminate points that don't meet criteria. Sep 14, 2017 at 15:52
• The reason I used ECEF is because the world is a ellipsoid (of sorts). As latitude increases, the distance in km gets shorter and short away from the equator. So you must use `Haversine` to calculate distance. I am just having trouble traversing the tree is all. Sep 14, 2017 at 15:53
• @pstatix- any comments on my question - scicomp.stackexchange.com/questions/30102/…?
– user36959
Aug 31, 2018 at 4:43