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

Question

Hey guys!!

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

Iterating through the entire set of segments, calculating each point-segment distance and then selecting the smallest is not efficient, but it is the only way to do this.

If your formula for calculating the distance uses trigonometry functions (sin, cos etc.), there is a much faster non-trigonometric function you can use instead. I can dig this up if you need it.

Answer 2

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

Answer 3

A 2D segment Voronoi diagram is probably faster than a BSP, though more code: http://www.cgal.org/Manual/3.1/doc_html/cgal_manual/Segment_Voronoi_diagram_2/Chapter_main.html