CODEWITHSUNDEEP
algorithmsortingcomputer-sciencecomputational-geometrygeographic-distance
Dylan A
Dylan A

Reputation: 1

Finding Closest Point to a Set of Points (in Lat/Long)

I am given a random set of points (not told how many) with a latitude and longitude and need to sort them.

I will then be given another random point (lat/long) and need to find the point closest to it (from the set above).

When I implement a linear search (put the set in a list and then calculate all the distances), it takes approximately 7 times longer than permitted.

So, I need a much more efficient sorting algorithm, but I am unsure how I could do this, especially since I'm given points that don't exist on a flat plane.

Upvotes: 0

Views: 1376

Answers (1)

S. Huber
S. Huber

Reputation: 1193

If your points are moderately well distributed then geometric hashing is a simple method to speed up nearest neighbor searches in practice. The idea is simply to register your objects in grid cells and do your search cell-wise so you can restrict your search to a local neighborhood.

This little python demo applied the idea to circles in the plane: Circles inserted into a geometric hash

So in your case you can choose some fixed N and split the longitude coordinates in [0, 2pi] into N equal parts and the latitude coordinates in [0, pi] into N parts. This gives you N^2 cells on the sphere. You register all your initial points at these cells.

When you are given the query point p then you start searching in the cell that is hit by p and in a large enough neighborhood such that you cannot miss the closest point.

If you initially register n points then you could choose N to something like sqrt(n)/4 or so.

Upvotes: 2

Related Questions