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?
    – pstatix
    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.
    – pstatix
    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

1 Answer 1


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

Only implement this algorithm with the Haversine distance function:


  • 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.
    – pstatix
    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.
    – pstatix
    Sep 14, 2017 at 15:53
  • @pstatix- any comments on my question - scicomp.stackexchange.com/questions/30102/…?
    – user36959
    Aug 31, 2018 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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