CODEWITHSUNDEEP
c++
ConfusedCoder
ConfusedCoder

Reputation: 387

How can I find the closest location on a map to an arbitrary point?

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

Answers (2)

James Adkison
James Adkison

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

LHLaurini
LHLaurini

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

Related Questions