Segmenting Linear Shapes

This post started as a Handmade Software - Seattle 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 properties with historical value. A statue of Abraham Lincoln is a resource, and so is the Oregon Trail. They can be split into two general categories for our technical purposes: Linear or Non-Linear.
• Projects are federally funded, licensed, or permitted projects.
• Section 106 is the law that says every such project must be reviewed for its impact on historical resources.¹

We have created an application to streamline the review process. But the application did not take into account the length of linear resources compared to the corresponding project.

Imagine you need to build a bus stop close to the Oregon Trail. The entire Oregon Trail will get pulled into the review process. That is 2,170 miles (3,490 kilometers) of trail that will need to be reviewed.

Consequences of this oversight in the program:

• The review can take way longer than it's supposed to.
• Nobody is actually going to review the whole thing. It is too much to cover.
• It turns into a back-and-forth with the agency.

In short

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

Now that we have a potential solution, we need to think about problems that we can immediately run into:

• 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 spatial information from the user? That needs an interactive frontend experience.

Frontend interaction design

Users 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.

How can we do this with the ArcGIS.js SDK? There is no out-of-the-box way. We will have to make our own custom tool.

The user flow of our custom tool

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. It holds the referenced route, the snapped coordinates, how far along the route the point is, and the offset from the route:

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

Finally, the route is cut between the two hits. Because the cut follows the route itself, the segment keeps all of the route's vertices instead of drawing a straight line between the clicks. This is called dynamic segmentation.³

Here is the tool running in the application:

Data structures

There are two structs.

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

type Hit struct {
	Line Route // the parent route (one path from the linear resource)
	At   struct {
		Coords []Coordinate
		// validation props...
		Measure float64
		Offset  float64
	}
}

The second is for database persistence⁴:

type Segment struct {
	ParentResourceID int64        // foreign key to the parent resource
	Waypoints        []Coordinate // the snapped coordinates of the clicks
	Line             []Coordinate // the stitched line, a copy from save time
}

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

Segment logic in pseudo code

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
    validate(hit) // wrong direction, too far from all possible matches, etc...
    hits.add(hit)
    draw stitch(hits) as a draft

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

func locate(route, point) Hit:
    // we use turf.js for this
    q = nearest point on route to point
    return { route, coords: q,
             measure: distance along the route to q,
             offset:  distance from point to q }

func stitch(hits) Polyline:
    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. Turf is great by the way.

In TypeScript, the two steps look like this:

import { nearestPointOnLine, lineSliceAlong } from "@turf/turf";

// locate: snap the click to the route
const snap = nearestPointOnLine(route, click);
const { location: measure, dist: offset } = snap.properties;

// stitch: cut the route between two hits. (route, start, end)
const piece = lineSliceAlong(route, a.measure, b.measure);

Questions from talk

• What about forks in rivers, roads, and trails?
  • A segment can go from one path to another only through a junction. A junction is an end point that both paths share. With no junction, the tool refuses the click.
• What happens to a segment when someone edits the parent route?
  • Every waypoint snaps to the edited route again, and the line is stitched again. This runs on every change to the parent shape.
• Why store waypoints, and not measures or only the line?
  • An edit to the route changes the measures, and the saved line no longer matches. A waypoint is only a coordinate, so it can snap to the edited route again. Its the same mechanism of when the user clicks, we just do it instantly, so we are resilient to edits.
• Why do this in the browser, and not in PostGIS or server side?
  • PostGIS can do the same math with ST_LineLocatePoint and ST_LineSubstring. But the user needs the result live, on every click and every drag, network I/O would be way too slow.

Talk to me!

Feel free to contact me if you would like to chat!

• Git server git.TheNoeTrevino.com
• Website: TheNoeTrevino.com
• Email: noetrevino.music@gmail.com