I have a list of points (more than a few million) defined by latitude and longitude. I want to find out the neighbors of each point. For example, I want to know for each point, what the nearest point, or what the nearest 4 points? or how many neighbors are within 10km radius?

I want to do it programmatically, please provide some possible solutions.

So far I have used a for loop to find out the nearest neighbor:

//C++ example
for (i=0;i<npoint;i++)
            distance = some_function(lat1, lon1, lat2, lon2);
      //now we can find the smallest distance from the container

But this only works for a limited data size.

  • In QGIS use menu vector : analyses : nearest neighbour to find the nearest neighbours of each point. See also [find nearest feature][1]. To find the number of neigbours within 10 km add a 10km-buffer to your points-layer. Then use menu vector : analyses : count points in polygon - see also [How to count points in polygons with QGIS?][2] Works similar in QGIS 3.x [1]: issues.qgis.org/projects/qgis/wiki/Find_nearest_features [2]: gis.stackexchange.com/questions/213186/…
    – Babel
    Sep 6, 2019 at 22:52
  • 1
    scipy's kdtree is helpful for this kind of analysis, but keep in mind that you would need to project your lat/long into some kind of coordinate system with non-degree units.
    – Jon
    Sep 6, 2019 at 23:07
  • @jon, the problem is I have million to billion of points all over the globe. The points are distributed on a sphere.
    – Chang
    Sep 6, 2019 at 23:28
  • 2
    I highly recommend doing this in postgis
    – jbalk
    Sep 6, 2019 at 23:53
  • 2
    What have you a tried to do so far? The question above as stated is too broad.
    – om_henners
    Sep 7, 2019 at 3:35


Your Answer

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

Browse other questions tagged or ask your own question.