1

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. enter image description here

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

3
  • Did you find the linear referencing methods of JTS locationtech.github.io/jts/javadoc/org/locationtech/jts/…? PostGIS has postgis.net/docs/ST_LineInterpolatePoint.html.
    – user30184
    Oct 8, 2020 at 23:48
  • I didn't! I think linear referencing is the solution. I haven't tried it out or dug into the code but it looks like you can pass a linear geometry to construct a LengthLocationMap and then call .getLocation on the object with the linear geometry's length / 2. However, it is still unclear to me how to get coordinates in the coordinate space for the LinearLocation that is returned from that method... github.com/locationtech/jts/blob/…
    – jcallin
    Oct 9, 2020 at 16:06
  • That's a pretty specific use case, and there's no standard algorithm for this that I know of. But your approach sounds reasonable.
    – dr_jts
    Mar 20, 2021 at 19:40

1 Answer 1

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!

2
  • LineSegment only works for a single line segment, if you look in my picture example I am solving this problem for all linestrings in a coordinate space. I believe my solution is coordinate agnostic because it uses JTS's Coordinate class which can occupy many different coordinate spaces
    – jcallin
    Oct 9, 2020 at 15:55
  • my apologies - you did say linestring not segment, yep my bad. Network trace/linear tracing might solve this and the above mentioned geometry classes should have something that can solve this.... - You have commented this above, so I think you are on the right track. Maybe try tracing out the network first to create a list/vector/array of named segment coord pairs at the vertexes , so you end up with seg_1, x1y1, x2, y2, seg_2, x2,y2, x3,y3 etc. That will give you coords of each vertex, lengths of each segment etc, im sure there is more elegant ways. Geometry in a DB will always have coords!
    – nr_aus
    Oct 11, 2020 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.