pgRouting: A Technique for Generating Route Loops

Part 2: Cleaning up the loops

This supplements the posting a few days back about routing loops. Go back and read it if you like. Phase 2 was the fetching of routes between each WP pair, and the collection of  $route_segments as a list of pgRouting line segments, complete with associated information about the segment such as its name. Phase 3 is up to you, iterating over the segments to generate text directions, WKT for sending to OpenLayers, etc.


But, let's add Phase 2B: cleanup of the route to remove meaningless spurs.

A nearly constant issue with the loops we've been generating, is that they don't "look like loops" The given path could have you walk a quarter-mile up a trail, then pull a U-turn to get back onto the path to the next one. All of these little spurs sticking off of the trail, made it look like one of those models of benzene. Ideally we wouldn't take such nonsensical detours (if the detour were far enough that it actually altered the routing, it wouldn't be nonsensical).

We gave thought to some ideas. One was to close the linestring into a polygon by adding a point, then use ST_MakeValid() to clean up the polygon. MakeValid would (presumably) remove the self-intersecting regions of the polygon, which means the spurs. But that won't work: once we've merged into a polygon, we lost the identity of each segment; though we may have a nice oval, we would have no feasible way to re-fetch the segment names, and we'd basically be restricted to a nameless polygon any any info we could derive about its segments.

So, what occurred to me: Knowing that it's sorted by TSP, and that we're routing for shortest distance between each TSP, any segment which appears more than 1 time (identified by its GID) must be part of a spur. I can't provide a mathematical proof about some outlandish topology, but it really looks true here. So let's go with it.

It worked great! The only catch was that the apex of a spur is only visited once: while we removed the spur, we do have extraneous points. Fortunately, these "spur apexes" are surrounded by two-visit segments so they should be easy to detect too.

PHASE 2B: REMOVE DUPLICATE SEGMENTS

    // go over the segments and catalog them by ID#
    // keeping a count of any segments which are touched twice
    $already_seen = array();
    foreach ($route_segments as $segment) {
        if (! @$already_seen[ $segment->gid ] ) $already_seen[ $segment->gid ] = 0;
        $already_seen[ $segment->gid ]++;
    }

    // go over them again and collect only segments which appear once AND which are not surrounded by two-fers
    $route_segments_unique = array();
    $howmany = sizeof($route_segments);
    for ($i=0; $i<$howmany; $i++) {
        // this node is a backtrack; omit it
        if ($already_seen[$route_segments[$i]->gid ] != 1) continue;

        // if this is not the first or last point, check the surrounding points

        // if they are both repeats, then this one will be an island
        if ($i != 0 and $i != $howmany-1) {
            if ($already_seen[ $route_segments[$i-1]->gid ] != 1) continue;
            if ($already_seen[ $route_segments[$i+1]->gid ] != 1) continue;
        }

        // fine, fine, then it's a valid node on a nice non-crossing path
        $route_segments_unique[] = $route_segments[$i];
    }
    $route_segments = $route_segments_unique;
    unset($route_segments_unique);
    unset($howmany);

CONCLUSION

This works great! We are now getting nice, clean loops without weird spurs.

This does still suffer some of what I call "the trailhead effect" The very end of a loop may be trimmed off, e.g. the part where we walk 200 feet to the first fork, which we would walk back again. Technically it's a spur, and I've not figured out logic for knowing that this is "a good spur" Fortunately, this isn't a problem in the real world: the hiker is standing at the trailhead and can see on the map that "turn onto Butterfly Creek Trail" is right over there.