1

I am trying to find nearest n/w nodes from multiple buildings in an area, I have 2 geodataframes/Tables in Oracle DB, buildings have point geometries with ID's and Nodes have point geometries with Node ID's,

Eg: I want to find the nearest N nodes from 1 building- I have ~100000 Nodes, so to find the nearest nodes I am experimenting with 2 techniques, Oracle Spatial Functions and GeoPandas/BallTree in Python

  1. Finding the Nearest points using Ball Tree from Sklearn, Code - https://stackoverflow.com/questions/62198199/k-nearest-points-from-two-dataframes-with-geopandas

closest_stops = nearest_neighbor(buildings, stops, return_dist=True)

This gives me fast results and works on the complete set of Data

  1. Finding Nearest points using SDO_NN in Oracle DB: Link - https://docs.oracle.com/database/121/SPATL/sdo_nn.htm#SPATL1032

SDO_NN(geometry1, geometry2, param [, number]);

My code

SDO_NN(S.LOCATION, ORACLE_SPATIAL_STUDIO.SGTECH_PTF(N.LONGITUDE, N.LATITUDE), 'DISTANCE = '2000' UNIT=FOOT SDO_NUM_RES=1', 1 ) = 'TRUE'

The question is I observed for some buildings the 1st Nearest points out of the ~100000 Nodes is exactly the same for both Techniques in Meters/Feet, although there are some instances where the 1st nearest Point is completely off for the BallTree Algorithm, Eg:

Building Location Building Location Result from BallTree - 110m Result from BallTree Result from SDO_NN - 185m Result from SDO_NN

In reality on Google Maps, the distance is completely off from the calculations and also the result from SDO_NN looks closer GoogleMaps

I understand that here BallTree uses the haversine metric to measure the distance, but I would like to understand the difference between both and which can be trusted for real world applications such as Network Deployment Routes ,etc.

Best case scenario is getting the Nearest Node based on Accessibility/Roadway distance but I believe that's challenging with my current setup.

Any Ideas on the Distance calculations here? Any Suggestions on which technique I can rely on?

1
  • I cannot use any paid services such as FourSquare, Google Maps API for finding the distances, I have to rely on the coordinates.
    – m2rik
    Jan 14, 2022 at 18:04

1 Answer 1

2

BallTree is very fast, you can change the distance metric in BallTree to metric='euclidean' and check again.

tree = BallTree(candidates, leaf_size=15, metric='euclidean')

Also since your coordinates are in EPSG:4326 (WGS84) its always better to convert to a projected coordinate system which gives distances in meters directly. You can convert your coordinates to a UTM projection and once you do that both methods should give you same results for all cases as both will use Euclidean distance. I think the difference in results is only because of the different distance methods used.

Edit: Based on your comment I tried to verify the straight distance between the nearest point you found using BallTree method and the building and it seems that it is 827meters. enter image description here

I feel that while you are constructing the BallTree and updating the distances back in the dataframe you are probably putting distances against incorrect index. While the distance of SDO_NN matches to that 185 meters you have calculated.

In the other Stackoverflow link you are referring to construct your balltree the index of geodatframe is being reset at this line

right = right_gdf.copy().reset_index(drop=True)

so make sure you are updating distances against correct indices.

6
  • I do have the right projections for both my Dataframes and if you see the BallTree code, it converts the co-ordinates to radians and back to Meters for calculations. Also, Just tested it using the Euclidean distance and the number was 206m, the question is which one do I trust for measuring the distances, SDO_NN uses indexes to get the distance whereas BallTree is measuring based on the Great-circle Distance, also if you see the Google the distances are way off. Any feedback is appreciated and thanks for your response
    – m2rik
    Jan 14, 2022 at 21:17
  • 1
    Ideally the output of both methods should have been same. There is definitely something wrong with way you are using BallTree. I have updated possible causes of this in the answer
    – Abhilshit
    Jan 14, 2022 at 21:53
  • I removed the reset index part as the index I have for my rightgdf is sequential, even after making that change, the result I got is 219m. RangeIndex(start=0, stop=121976, step=1) Again my goal is to figure out whether I should go ahead with SDO_NN or rely on BallTree for efficiency and usability
    – m2rik
    Jan 14, 2022 at 22:22
  • So, using Euclidean I am getting the same Node as from SDO_NN, whereas Haversine gives me a different node which in numbers 110m is closer but in reality is ~827m away which you calculated too, so I am assuming its the way SDO_NN calculates the distances, I should probably keep it to Euclidean, although it is interesting to see that, the people who wrote this suggest using the Haversine metric automating-gis-processes.github.io/site/notebooks/L3/…
    – m2rik
    Jan 14, 2022 at 22:32
  • Haversine is a better distance metric to use since it accounts for the curvature of earth especially with coordinates in EPSG:4326 (WGS84). You might want to try to let SDO_NN use haversine and check what is the result. Again if possible share, a subsample. of your geodataframe, I can see whats up with balltree asI am working on a similar problem off lately
    – Abhilshit
    Jan 15, 2022 at 19:40

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.