Segmenting Linear Shapes

This post started as a Handmade Software lightning talk. It walks through how we let users cut a long historic line, like a trail or a canal, into smaller segments by pointing and clicking on a map.

The domain problem

A few terms first:

• Resources are things with historical value. A statue of Abraham Lincoln is a resource. So is the Oregon Trail.
• Projects are federally funded projects.
• Section 106 is the law that says every federally funded project must be reviewed for its impact on historical resources.

Now imagine you need to build a bus stop close to the Oregon Trail. The entire Oregon Trail gets pulled into the review process. That is 2,170 miles (3,490 kilometers) of trail.

• The review takes days.
• Nobody is realistically going to review the whole thing.
• It turns into a back and forth with the agency.

Problem statement

Long linear resources are pulled into review in their entirety. That is impractical, and it does not fit the domain.

The solution: let the user declare a stretch of a linear resource as a segment, and review only that segment.

Technical issues

• A linear resource has many paths. Roads branch and canals fork, so the geometry is a 2D array of paths, not one line.
• The parent geometry gets edited after segments exist. How do the segments stay attached to it?
• How do we even get this information from the user? That needs a frontend interaction.

What the client asked for

I want to be able to point and click on a line, and then save it. It should be visually obvious that the segment is there.

The user flow

The user turns on the segment tool and clicks near the route. The click is almost never exactly on the line, so we have to snap it to the line with a tolerance:

The click snaps to the nearest point on the route. This produces a hit object. The referenced route, the snapped coordinates, how far along the route, and the offset from the respective route:

The next click must go forward along the route. If it goes backward, the tool refuses it.

Finally, the route is cut between the two measures. Because the cut follows the route itself, the segment keeps all of the route's curves instead of drawing a straight line between the clicks.

Data structures

There are two structs.

The first is the hit, used for frontend interaction and validation in the GIS view:

{
  "line": "Route[0]", // the parent route, one path in the 2D array
  "at": {
    "coords": [321.2, 150.2], // the snapped point on the route
    "measure": 3.177, // how far along the route the point is
    "offset": 1117.2 // how far the click was from the route
  }
}

The second is for database persistence:

{
  "parentResourceId": 42, // foreign key to the parent resource
  "waypoints": [
    // a MultiPoint in PostGIS
    [321.2, 150.2],
    [498.7, 162.9]
  ]
}

The measure and the offset are not saved. They only matter while the user is clicking.

Point and click, in pseudocode

on "Create Segment" click:
    routes = paths of the parent polyline
    hits = []

on map click(point):
    candidates = [locate(route, point) for each route]
    hit = the candidate with the smallest offset
    if hit.offset > 8 km: ignore       // too far from every route
    if not canExtend(hits, hit): warn  // backward, or no junction
    hits.add(hit)
    draw stitch(hits) as a draft

on double click:
    line = stitch(hits)
    save { parentResourceId, waypoints: hits.coords, line }

Each entry in hits is the first struct. The object passed to save is the second.

The two helper functions:

locate(route, point):                  // one route only
    for each piece A -> B of the route:
        q = closest point to `point` on the piece
    q = the one with the smallest distance to `point`
    return { route, coords: q,
             measure: distance along the route to q,
             offset:  distance from point to q }

stitch(hits):
    for each pair (a, b) in hits:
        line += a.route.slice(a.measure, b.measure)
    return line

locate is linear referencing. In Turf, it is nearestPointOnLine. slice is dynamic segmentation, which is lineSliceAlong in Turf.

Notice that the "pick the smallest distance" step happens twice. Turf does it once across the pieces of a single route. Route.snap does it again across all of the routes.

Questions to ponder

What about forks in rivers, roads, and trails?

Forks happen all the time. A segment can move from one path to another only through a junction: an end point the two paths share, within about 0.1 m. When there is no junction, the tool refuses the click.

What happens to a segment when someone edits the parent route?

The saved waypoints snap to the new route again, and the line is stitched again from those waypoints.

Why store waypoints, and not measures or the line?

An edit to the route changes every measure, so saved measures would point to the wrong places. A waypoint can simply snap to the edited route again. The saved line is still stored, but it is only a copy from the moment of the save.

Why do this in the browser, and not in PostGIS?

PostGIS can do the same math with ST_LineLocatePoint and ST_LineSubstring. We need the result live, while the user is clicking, so it runs in the browser.

How do you even test this stuff?

Good question. I am still thinking about that one.