Does a common algorithm exist to find the midpoint of a linestring by distance within a coordinate system?

Question

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
    }
  }

Answer 1

The JTS library has Linear reference methods as mentioned above by user30184.

More specifically, the Linesegment Class has a method Midpoint()

https://locationtech.github.io/jts/javadoc/org/locationtech/jts/geom/LineSegment.html#midPoint--

This method will return coordinate values of the midpoint of the linesegement. In your above code, it appears that you know the coordinate values of your 'linestring'. Coordinate values are required to create a linesegment object, so I think you have everything you need there.

Then its just a simple case of measuring distance from node 1 of your linestring, to the midpoint.

Your code is an interesting approach, using a traversal method, but you are over complicating this - It also has some flaws due to units (eg: What distance in units are you travelling? Meters? CMs? MM? etc). The solution is much more simple, remembering that lines exist on an assumed 2D Euclidean plane. If you already know your start node and end node coords (which you do) then calculating the mid point would simply be:

XY Coords of start node - XY coords of end node / 2

eg: Line segment start node has coord values of 345612, 7523697 (Values from a known 2D map grid) and end node coord values 345620, 7523690

Difference of X = 8. Difference of Y = -7... Divide by 2, and we get 4 and -3.5. Midpoint exists at 345612 + 4 and 7523697 - 3.5 Midpoint = 345608, 752363.5

Either way, checkout the midpoint method on linesegment class!