# Smathermather's Weblog

## Looping Trails– alternate routing for recreational use

Posted by smathermather on June 16, 2011

This post will be a conceptual one, rather than technology specific. Imagine a scenario where you want to provide a curated trail experience from a mobile device. You want people to be able to go to a park, pick a starting location (such as their current location) in their device, and query the system for all the possible 1-3 mile loops from that location. How do you rank the looping options, once you’ve calculated what all the possible loops are?

1 possible loop

All other things being equal, you might suggest that you want the experience to be as loopy as possible to avoid the Bilbo Baggins problem (There and Back Again):

A shape index, like Perimeter/Area could be a proxy for loopiness.

But once you’ve chosen your loopiest trail, the one with the smallest perimeter to area ratio, how do you choose your second best option?  You should choose the next least similar trail loop, so that the user can choose from the maximum diversity of possible choices:

Trail 1 is less similar (50%) to Trail 2 is to Trail 3...

Now we have a clear hierarchy of choices for our trail user, we return the best possible option first, then a list of the options which are least similar.  If you were to offer a 3rd option (three options is a nice place to start to avoid overwhelming the user), that 3rd option should be the second least similar option to the 1st.

The question is, how to do we calculate similarity between routes?  Fuzzy Hashes is the answer.  A fuzzy hash comparison of the pairwise geometries of all the possible loops would give us a matrix of similarity:

Which we can use to complete our trail loop ranking.

1. ### smathermathersaid

Looking around in the PostGIS options, perhaps ST_HausdorffDistance would be an existing function which would tell us what we need to know with respect to similarity… . http://postgis.refractions.net/docs/ST_HausdorffDistance.html

2. ### smathermathersaid

In fact, looking closer at Hausdorff distance, this could help with determining the difference between similar, but parallel loops. That’s better than we can do with fuzzy hashes.

3. ### smathermathersaid

And finally– similar problem, different application:

http://lin-ear-th-inking.blogspot.com/2009/01/computing-geometric-similarity.html