Algorithm to find the closest segment to a point among many segments (Reverse Geocoding)

Question

I have a set of segments defined by two points. Given a point how can I discover the closest segment to such point?

I have already written an algorithm that computes the distance between a point and a segment. Anyway calculating such distance for each segment and then choose the segment with the lowest distance is not really efficient :(

Since the segments represent streets this is actually a Reverse GeoCoding problem so I hope there are well-known solutions to this problem...

THANKS A LOT!

Thee

Is the set of segments sorted in any way? – Glynas

Do the segments overlap? Do you mean segments on a line, or e.g. spherig segments? If the latter, how do your two points define the segment? (different definitions are possible) ---- Anyway, sorting the segments by some criteria usually helps. – Quintile

@Giorgio: Did you found the algorithm? Could you please to share or give me a link to that algorithm. Thank you in advance! – Potto

Answer 1

Use a grid, kd-tree, quadtree or similar binary space partitioning method. Then, starting from the tree cell that your point lies in, start exploring segments until the distance from the point to the cell containing the segment is greater than the smallest distance found so far.

http://en.wikipedia.org/wiki/Binary_space_partitioning

(This is, of course, assuming that the segments/streets change only very rarely, but you have a lot of points to locate).

Soy

There's no way to know whether any given segment intersects with any given partition without performing an (at least) equally-expensive (compared to the point-segment distance) calculation, so any partitioning approach would only potentially be faster if the set of segments meets certain conditions (like maximum segment length << partition dimensions, e.g.). – Sickler

@MusiGenesis: the key is to make every segment part of all the leaves it intersects when the tree is constructed. This way, if one of the leaves is close enough to the points, the segment will be tested, and if none of the leaves are close enough, then the segment is never tested. Since the tree is only constructed once, the cost of doing this is split over all the request that happen afterwards. – Soy

agreed. I was assuming there is a different set of segments each time. – Sickler