Javascript - how to calculate midpoint of linestring?

Question

With given GeoJSON linestring:

{
  "type": "FeatureCollection",
  "features": [
    {
      "type": "Feature",
      "properties": {},
      "geometry": {
        "type": "LineString",
        "coordinates": [
          [
            2.6806640625,
            46.437856895024204
          ],
          [
            4.7021484375,
            50.20503326494332
          ],
          [
            13.271484375,
            47.010225655683485
          ],
          [
            17.2265625,
            52.855864177853974
          ]
        ]
      }
    }
  ]
}

I'd like to find exact middle point. I don't mean the middle element of a given array but calculating a midpoint which is exactly placed at the middle of line. So, if a line is 30km long in total then midpoint would be placed at 15km.

I tried searching npm for something like that but couldn't find. The only library which is close gives ability to place n points on line, and then I can get the middle one. But it's pretty bad in my case because precision is not that good.

Perfect option would be implementation of this http://postgis.net/docs/manual-1.5/ST_Line_Interpolate_Point.html in JavaScript.

How can I achieve it?

What is a linestring? Why does it have four points? Shouldn't a line have only two points? — fafl, Feb 21 '17 at 15:55
@fafl Linestring description can be found here: http://geojson.org/geojson-spec.html#linestring — Daniel, Feb 22 '17 at 09:13
I updated my answer, been working on it for a while now. finally got it! :) — Maher Fattouh, Feb 22 '17 at 21:25

Maher Fattouh · Accepted Answer · 2023-03-29T13:15:08.973

Here's a working CodePen

the following code will return the point at a specific distance.

for this specific case the midpoint distance is total length / 2

call the main function like this, assuming our linestring array is stored in points

var totalLength = totalLen(points);
var midDistance = totalLength / 2;
var midPoint = getPointByDistance(points, midDistance)

##Javascript

myData = {
  "type": "FeatureCollection",
  "features": [{
    "type": "Feature",
    "properties": {},
    "geometry": {
      "type": "LineString",
      "coordinates": [
        [
           2.6806640625,
          46.437856895024204
        ],
        [
          4.7021484375,
          50.20503326494332
        ],
        [
          13.271484375,
          47.010225655683485
        ],
        [
          17.2265625,
          52.855864177853974
        ]
      ]
    }
  }]
}
var points = myData.features[0].geometry.coordinates
var totalLength = totalLen(points);
var midDistance = totalLength / 2;
var midPoint = getPointByDistance(points, midDistance)
alert ("midPoint = " + midPoint[0] + ", " + midPoint[1])
// main function
function getPointByDistance(pnts, distance) {
  var cl = 0;
  var ol;
  var result;
  pnts.forEach(function(point, i, points) {
    ol = cl;
    cl += i ? lineLen([points[i-1], point]) : 0;
    if (distance <= cl && distance > ol){
      var dd = distance - ol;
      result = pntOnLine([points[i-1], point], dd);
    }
  });
  return result
};
// returns a point on a single line (two points) using distance // line=[[x0,y0],[x1,y1]]
function pntOnLine(line, distance) {
  t = distance / lineLen(line)
  xt = (1 - t) * line[0][0] + (t * line[1][0])
  yt = (1 - t) * line[0][1] + (t * line[1][1])
  return [xt, yt]
};
// returns the total length of a linestring (multiple points) // pnts=[[x0,y0],[x1,y1],[x2,y2],...]
function totalLen(pnts) {
  var tl = 0;
  pnts.forEach(function(point, i, points) {
    tl += i ? lineLen([points[i - 1], point]) : 0;
  });
  return tl;
};
// returns the length of a line (two points) // line=[[x0,y0],[x1,y1]]
function lineLen(line) {
  var xd = line[0][0] - line[1][0];
  var yd = line[0][1] - line[1][1];
  return Math.sqrt(xd * xd + yd * yd);
};

##Explanation

1. we find the total length of the linestring:

function lineLen() calculates the length of a single line.
function totalLen() loops through the lines and calculates the total length.

*source and credits here (Igor Šarčević)

2. the distance of midpoint is total length / 2:

now that we have the wanted distance we loop through lines and check distance of this line-startpoint and this line-endpoint and see if midpoint distance is between them.
once we have the single line that we know our midpoint is on we calculate it's distance from this line-startpoint (total length - line-startpoint distance)
now we use this formula (function pntOnLine()) to find xt,yt (wanted midpoint)

*credits to Sen Jacob.

##Visualization I included an HTML5 canvas to draw (visualize) the linestring and midpoint, you don't have to include them. but they're useful if you want to test the code and see the result live

// Just for visualizing on canvas (not needed)
var canvas = document.getElementById("myCanvas");
var ctx = canvas.getContext('2d');
drawLine(points);
//
ctx.beginPath();
ctx.arc(midPoint[0], midPoint[1], 2, 0, 2 * Math.PI);
ctx.closePath();
ctx.fillStyle = "red";
ctx.fill();
//
function drawLine(pnts) {
  pnts.forEach(function(point, i, points) {
    if (i === 0) {
      ctx.beginPath();
      ctx.moveTo(point[0], point[1]);
    } else {
      ctx.lineTo(point[0], point[1]);
    }
    if (i === points.length - 1) {
      ctx.stroke();
    }
  });
}

Is this for simple lines or taking care of the curvature of a sphere? — fafl, Feb 24 '17 at 15:03
In `getPointByDistance` function, the result of `totalLen` (the first line) is assigned to a var `tl` but `tl` is unused in the function body. Am I missing something ? — MoOx, Mar 28 '23 at 09:59
I can't remember why I did that, but you're right. it is unused. — Maher Fattouh, Mar 29 '23 at 13:14

fafl · Answer 2 · 2017-02-24T16:07:57.607

So I assume you have a list of coordinates, that describe a line with waypoints on a sphere. Every coordinate has latitude and longitude. This implementation goes through the lines until it reaches 50% of the distance:

var coordinates = [
  [
    2.6806640625,
    46.437856895024204
  ],
  [
    4.7021484375,
    50.20503326494332
  ],
  [
    13.271484375,
    47.010225655683485
  ],
  [
    17.2265625,
    52.855864177853974
  ]
];

// From http://stackoverflow.com/a/18883823/5710637
function calcCrow(lat1, lon1, lat2, lon2) 
{
  var R = 6371; // km
  var dLat = toRad(lat2-lat1);
  var dLon = toRad(lon2-lon1);
  var lat1 = toRad(lat1);
  var lat2 = toRad(lat2);

  var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
    Math.sin(dLon/2) * Math.sin(dLon/2) * Math.cos(lat1) * Math.cos(lat2); 
  var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); 
  var d = R * c;
  return d;
}

// Converts numeric degrees to radians
// From http://stackoverflow.com/a/18883823/5710637
function toRad(Value) 
{
    return Value * Math.PI / 180;
}

// Returns a point from a line
// Should use halversine but i'm too bad at math
function getPoint(factor, lat1, lon1, lat2, lon2)
{
  while (lat1 < 0) {lat1 += 360}
  while (lat2 < lat1) {lat2 += 360}
  latPoint = lat1 + factor * (lat2 - lat1)
  latPoint = ((latPoint + 180) % 360) - 180
  otherLat = latPoint < 0 ? latPoint + 180 : latPoint - 180
  latPoint = Math.abs(latPoint) < Math.abs(otherLat) ? latPoint : otherLat
  lonPoint = lon1 + factor * (lon2 - lon1)
  return [latPoint, lonPoint]
}

function getHalfDistance(coordinates)
{
  // Calculate complete distance
  var totalDistance = 0;
  for (var i = 1; i < coordinates.length; i++) {
    totalDistance += calcCrow(coordinates[i-1][0], coordinates[i-1][1], coordinates[i][0], coordinates[i][1])
  }

  // Find the 50%
  var target = 0.5
  var currentDistance = 0
  for (var i = 1; i < coordinates.length; i++) {
    var thisDistance = calcCrow(coordinates[i-1][0], coordinates[i-1][1], coordinates[i][0], coordinates[i][1]);
    if (target * totalDistance < currentDistance + thisDistance) {
       var midDistance = target * totalDistance - currentDistance;
       var factor = midDistance / thisDistance;
       return getPoint(factor, coordinates[i-1][0], coordinates[i-1][1], coordinates[i][0], coordinates[i][1]);
    }
    currentDistance += thisDistance
  }
}

console.log(getHalfDistance(coordinates))

Javascript - how to calculate midpoint of linestring?

2 Answers2