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!

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).