WHY WON'T IT FIND A ROUTE? BOUNDING BOX AND TOLERANCE

Today's post is fairly brief, but is the culmination of eight hours of tediously trying routes and adjustments. If it saves you one hour, won't you consider it worthwhile? :)

So, we have a routing network of trails for a Parks N Rec district. Directions via dijkstra_sp_delta() are working A-OK and have been for some months. But, the client wrote back with some news: he's having trouble finding a longer path across this one park.

I tried it too: about half of the routes would work, and half would not. I could route the 15 miles to a location, but move the marker a few hundred feet in any direction, and it may or may not be able to route there, even though my eyes can see the trail segments laid out.

It's consistent too: the same point would always work or always fail. And I followed it back into the SQL and verified that the given pair of nodes always would or would not have a route. So it's not some sysadmin issue such as out of memory or core dumps.

TOLERANCE

The directions handed back to the browser, include WKT of the segments so they can be plotted onto the map. I noticed that the route as given would skip from one trail to an adjacent one: walking a straight line, it would suddenly be 20 feet to the left on an adjacent trail, and sometimes back to the original trail. The visual effect was rather goofy and unattractive.

And, I suspect that this was routing us onto adjacent trails which would later diverge, and coming up with false negatives.

The cause here, is a too-high tolerance (25 feet) when generating the routing network via assign_vertex_id() The data had some known "dangles" due to human error in digitizing the trails, and a higher tolerance fixed that. We reanalyzed with a tolerance of 10 feet, and this stopped happening.

This solved an annoyance, but didn't get us any closer to finding the routes. Turns out that wasn't the problem at all...

BOUNDING BOX

Ultimately I discovered it:the directions stuff uses dijkstra_sp_delta() with a tolerance of 2640 feet. That is to say, the calculation excludes any segments that are not within a 2640-foot bounding box of the start and end vertices. That excludes the 900 square miles that can't possibly be relevant to this route, and gives us plenty of wiggle room to find routes.

Wrong.

In the case of this trails data, 5280 was the magic number. The trails meander enough, that a good path really can deviate by 1 mile away from the straight-line between the two points. And the performance loss isn't that bad, certainly not as bad as complete non-performance!

Anyway, no huge breakthrough here, but a word for someone else who just isn't finding the path: check your delta bounding box, and see if you're being too strict.