Reputation: 387
Note: For the remainder of this question I will call this arbitrary point as "myPoint" to avoid confusion.
Problem: There are several points on the map (it not practical to calculate the distance between each point and myPoint).
Attempt at a Solution: I tried doing a radius search but in order to know where these points are located within the circle, I would have to go through all the points and make sure the distance between them is less than the search circle's radius.
Question: How can I find the closest point to myPoint in an efficient way? Please ask questions if clarification is needed.
Upvotes: 0
Views: 1218
Reputation: 9602
You could use a technique to "partition" the search space (i.e., the map).
You could consider defining a regular grid that covers the map and store all map locations within each cell of the grid.
With this it is easy to calculate/determine which cell contains the myPoint. Then it is just a matter of considering the points within the same cell.
Note: You may have to consider neighboring cells too in the event the cell containing myPoint doesn't have any map locations or that the distance to a point in a neighboring cell is shorter than the distance to the point within the same cell (e.g., myPoint is near a cell border).
Upvotes: 1
Reputation: 2570
Calculating the distance between the points is inevitable. What I suggest you can do is to slice the map in smaller pieces (not necessarily regular) and then only calculate the distance between the points that lie in the same slice.
Upvotes: 1