Recentl I needed to find the mid-point of a linestring. I work with java/Scala so I naturally reached for the JTS library but couldn't find anything in there for doing this. I implemented an algorithm myself and am wondering whether there is an equivalent within common GIS programming packages, or if it is a specific solution to this problem that a more general algorithm could also solve. Here's a diagram of how it works.
The basic idea is to precalculate the length and divide by 2 so you know the distance to travel to the middle. Then, you traverse the linestring from one end until you have traversed more than the midpoint distance. Finally, take the vector which points from the too-far point back to the previous point and travel the distance equivalent to the difference between how far you've traveled and the total length to the center.
Here's the Scala code using JTS.
val distanceToMiddle = gf.createLineString(coordinates.toArray).getLength / 2
val result = findCoordinateByTraversing(coordinates)(distanceToMiddle)
def findCoordinateByTraversing(points: List[Coordinate])(targetDistance: Double): Option[Coordinate] = {
findPointByTraversingHelper(points, 0)(targetDistance)
}
@scala.annotation.tailrec
private def findPointByTraversingHelper(points: List[Coordinate], distanceAccum: Double)(
targetDistance: Double
): Option[Coordinate] = {
points match {
case pointA :: pointB :: points =>
// If the total distance travelled puts us beyond the middle, find the midpoint
val distanceTravelled = distanceAccum + new LineSegment(pointA, pointB).getLength
distanceTravelled match {
case d if d > targetDistance =>
// Find the midpoint by backtracking from pointB to pointA in the direction of pointA and magnitude of the remaining distance
val directionAngleRadians = Angle.angle(pointB, pointA)
val remainingDistanceToMid = distanceTravelled - targetDistance
val newX = pointB.x + remainingDistanceToMid * Math.cos(directionAngleRadians)
val newY = pointB.y + remainingDistanceToMid * Math.sin(directionAngleRadians)
Some(new Coordinate(newX, newY))
// Else keep looking for the midpoint
case _ => findPointByTraversingHelper(pointB :: points, distanceTravelled)(targetDistance)
}
// Single point or no points results in nothing being returned
case _ => None
}
}
LengthLocationMap
and then call.getLocation
on the object with the linear geometry'slength / 2
. However, it is still unclear to me how to get coordinates in the coordinate space for theLinearLocation
that is returned from that method... github.com/locationtech/jts/blob/…