How to Interpolate Along a Linestring

A linestring is simply a sequence of two or more points (or zero points), where each pair of points defines a line segment. Thus the sequence can be thought of as string of line segments that define some curve.

To interpolate along a linestring is, effectively, to walk along the linestring until we get to the point we want.

The length of the linestring is the sum of the lengths of all its segments. For this problem, we will assume we know the length. (If we don’t, this can be computed easily.) We will also assume that the point we want to find is a specific distance along the linestring and not a ratio from [0, 1]. If we do want to use a ratio, the distance we require is also easily computed.

The Simple Case: Interpolate on a Line Segment

If we have a single line segment of two points, we want to do a linear interpolation (or “lerp”) between them. Since a linear interpolation is the interpolation between two values in a straight line, we can do this for the x and y independently to get the new point.

def lerp(start: Double, end: Double, ratio: Double): Double = {
    start * (1 - ratio) + end * ratio
}

def lerp(start: Point, end: Point, ratio: Double): Point = {
    Point(lerp(start.x, end.x, ratio), lerp(start.y, end.y, ratio))
}

Note that start + (end - start) * ratio was not used. This is due to the floating-point arithmetic error that could result in not getting the end when the ratio is 1. Also, in this case, we used a ratio instead of distance since we need the ratio for linear interpolation.

In the case of a linestring, we are using distance. This is because we need to know how far we have traveled along the linestring to determine the ratio for interpolating along the line segment where our desired point lies.

Finding the Ratio for the Remaining Distance

If the current line segment we are on will contain the point we want, then we know how far we have traveled (including this segment). From this, we can compute the distance we truly have remaining and use that to find the ratio needed on the current segment. The distance remaining is the distance wanted minus the distance we have traveled up until this segment. The ratio is then just the distance remaining over the length of the current segment.

def findRatioBetweenPointsToGetDistanceWanted(start: Point, end: Point, distanceTraveled: Double, distanceWanted: Double): Double = {
    val distanceFromStartToEnd = calculateDistanceBetweenPoints(start, end)
    val distanceRemaining = distanceWanted - (distanceTraveled - distanceFromStartToEnd)
    distanceRemaining / distanceFromStartToEnd
}

Putting it All Together

To traverse the linestring up until the segment we need to interpolate on, we can just add up the lengths of each segment until we have traveled farther than the distance we want.

def getPointAlongLineString(points: Seq[Point], distanceWanted: Double): Point = {
    var distanceTraveled = 0.0
    var currentPoint = points.head
    var previousPointIndex = 0

    for (nextPointIndex <- 1 until points.length if distanceTraveled < distanceWanted) {
      val nextPoint = points(nextPointIndex)
      distanceTraveled += calculateDistanceBetweenPoints(point, nextPoint)
      currentPoint = nextEdgePoint
      previousPointIndex = nextPointIndex - 1
    }

    val previousPoint = points(previousPointIndex)
    val ratio = findRatioBetweenPointsToGetDistanceWanted(previousPoint, currentPoint, distanceTraveled, distanceWanted)
    lerp(previousPoint, point, ratio)
}