Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Algorithm for finding nearby points?

Tags:

Given a set of several million points with x,y coordinates, what is the algorithm of choice for quickly finding the top 1000 nearest points from a location? "Quickly" here means about 100ms on a home computer.

Brute force would mean doing millions of multiplications and then sorting them. While even a simple Python app could do that in less than a minute, it is still too long for an interactive application.

The bounding box for the points will be known, so partitioning the space into a simple grid would be possible. However the points are distributed somewhat unevenly, so I suspect most grid squares would be empty and then suddenly some of them would contain a large portion of the points.

Edit: Does not have to be exact, actually can be quite inaccurate. It wouldn't be a huge deal if the top 1000 are actually just some random points from the top 2000 for example.

Edit: Set of points rarely changes.

like image 668
Bemmu Avatar asked May 08 '09 05:05

Bemmu


People also ask

How do you find the closest pair of points algorithm?

Split-Conquer Method — Finding the Closest Pair The split conquer algorithm sorts the array by X coordinate, divides the sorted array into two, apply the algorithm recursively to the subarrays, and check whether or not there exists a pair with a shorter distance than that found in subarrays.

How do you find the closest point to a set of points?

The closest pair is the minimum of the closest pairs within each half and the closest pair between the two halves. To split the point set in two, we find the x-median of the points and use that as a pivot. Finding the closest pair of points in each half is subproblem that is solved recursively.

How do I find the closest point of a triangle?

To find the closest point on a triangle to a given point, we first project the given point onto the triangle's plane. If the point orthogonally projects inside the triangle, then the projection point is the closest point to the given point.


1 Answers

How about using quadtree?

You divide area to rectangles, if area has low density of points, rectangles are large, and if area has high density of points, rectangles will be small. You recursively subdivide each rectangle to four sub rectangles until rectangles are small enough or contain few enough points.

You can then start looking at points in rectangles near the location, and move outwards until you have found your 1000 points.

Code for this could get somewhat complex, so maybe you should try first with the simple grid and see if it is fast enough.

like image 84
Juha Syrjälä Avatar answered Sep 25 '22 10:09

Juha Syrjälä