2

I am looking for a fast algorithm that will find the closest point on a line segment in a graph (such as a road network) to my test point.

I'll try to be more specific. I have a road network graph. This may have somewhere in the region of 30 million nodes and links/lines (my US dataset is of this size). I already have a fast routing algorithm up and running, but it works from node to node. The real world does not work with nodes, but with coordinates. I could search for the nearest node to each start/end coordinate, and in the past I have coded a very fast coordinate matching algorithm (a few million nodes, and managing >~1000 test points per second).

Commercial routing algorithms do not work like that: They direct you to the nearest road segment. In other words I need to match a coordinate to the nearest line (graph link). As well as finding the closest line, I need a fraction that tells me how far along the line that closest point is. Then I can route from the closest node and add the fractional line in to the distance/time sum. Or correct accordingly if the route happens to go down the line.

I think it is reasonable to have a limit on the maximum distance to search. E.g. "The closest line that is within 500 metres". And this should help prune the search space.

Coding up an algorithm that searches all of these lines is pretty simple, but it would be slow due to the large number of lines and the geometry calculations. I could limit the search to be limited to those lines within the distance limit. And this could be further optimized by sorting the lines by longitude (say). Of course most lines have a fine longitude "width" which complicates that sort&search.

I still think this will be slow. How do commercial packages do this? Most will find and display a route within half a second or so, and most of that is taken up with the main routing algorithm, and constructing the result (deriving turn directions, etc).

There are a number of similar questions on this site (eg. How to find the nearest point projected on the road network? ) but these refer to specific packages such as PostGIS or ArcGIS. I am looking for an actual algorithm to code up myself. I suspect my main issue is known the words/phrases to search for. Once I've found an algorithm name, then a bit of Googling/etc will quickly find all-sorts of algorithms and papers...

  • It largely depends on how you store your data. Using a database (especially a GIS-aware one) and using indexes should make searches like this very quick. – barrycarter Apr 30 '16 at 18:09
  • They most likely use indexed grids. It's enough to search 1+8 neighbors. – FelixIP Apr 30 '16 at 20:52
  • Okay, some are built on true GIS systems (e.g. the routing Maptitude), but many aren't. Mine for example :-) @FelixIP: Do mean, find the closest node, and then test the neighbours and their links? Seems like that might miss some cases. – winwaed May 1 '16 at 17:49
  • I mean assigning segments to predefined mesh/cell once and store it in segment table – FelixIP May 1 '16 at 18:30
  • Sounds memory hungry – winwaed May 1 '16 at 20:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.