0

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++)
  {
     lat1=latitude[i];
     lon1=longotide[i];
     for(j=0;j<npoint;j++)
        {
            lat2=latitude[j];
            lon2=longotide[j];
            distance = some_function(lat1, lon1, lat2, lon2);
            vDistance.push_back(distance);
         }
      //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 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 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 at 23:28
  • 2
    I highly recommend doing this in postgis – jbalk Sep 6 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 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.