How Can You Find The Centroid Of A Concave Irregular Polygon In JavaScript?

March 25, 2023 Post a Comment

How can you find the centroid of a concave irregular polygon given its vertices in JavaScript? I want to pass a set of x,y points to a JavaScript function and be given an x,y point

Solution 1:

For the centroid of the 2D surface (which is likely to be what you need), The best is to start with a little bit of maths.

I adapted it here to your own notation :

function get_polygon_centroid(pts) {
   var first = pts[0], last = pts[pts.length-1];
   if (first.x != last.x || first.y != last.y) pts.push(first);
   var twicearea=0,
   x=0, y=0,
   nPts = pts.length,
   p1, p2, f;
   for ( var i=0, j=nPts-1 ; i<nPts ; j=i++ ) {
      p1 = pts[i]; p2 = pts[j];
      f = p1.x*p2.y - p2.x*p1.y;
      twicearea += f;          
      x += ( p1.x + p2.x ) * f;
      y += ( p1.y + p2.y ) * f;
   }
   f = twicearea * 3;
   return { x:x/f, y:y/f };
}

Solution 2:

The accepted answer has an issue which becomes prominent as the polygon's area becomes smaller. It would not be visible in most cases, but can result in some weird results at very small dimensions. Here's an update to that solution to account for this issue.

function get_polygon_centroid(pts) {
   var first = pts[0], last = pts[pts.length-1];
   if (first.x != last.x || first.y != last.y) pts.push(first);
   var twicearea=0,
   x=0, y=0,
   nPts = pts.length,
   p1, p2, f;
   for ( var i=0, j=nPts-1 ; i<nPts ; j=i++ ) {
      p1 = pts[i]; p2 = pts[j];
      f = (p1.y - first.y) * (p2.x - first.x) - (p2.y - first.y) * (p1.x - first.x);
      twicearea += f;
      x += (p1.x + p2.x - 2 * first.x) * f;
      y += (p1.y + p2.y - 2 * first.y) * f;
   }
   f = twicearea * 3;
   return { x:x/f + first.x, y:y/f + first.y };
}

Here's a case of a centroid ending up outside of a small polygon for anyone curious as to what I'm talking about:

var points = [
    {x:78.0001462, y: 40.0008827},
    {x:78.0000228, y: 40.0008940},
    {x:78.0000242, y: 40.0009264},
    {x:78.0001462, y: 40.0008827},
];
// original get_polygon_centroid(points)
// results in { x: 77.99957948181007, y: 40.00065236005001 }
console.log(get_polygon_centroid(points))
// result is { x: 78.0000644, y: 40.000901033333335 }

Solution 3:

This is fairly simple to do. The centroid of a finite set of k points x₁, x₂, ... x_k is described by the formula

(x₁ + x₂ + ... + x_k) / k

That means we can just add all the points up and then divide by the number of points, like this:

function getPolygonCentroid(points){ 
  var centroid = {x: 0, y: 0};
  for(var i = 0; i < points.length; i++) {
     var point = points[i];
     centroid.x += point.x;
     centroid.y += point.y;
  }
  centroid.x /= points.length;
  centroid.y /= points.length;
  return centroid;
}

Solution 4:

If you are not casual about the definition of 'centroid', this is the formula for the centroid of a polygon. As you can see, it's sufficiently more complicated than the centroid of a set of points. If you can do with the centroid of the points, that's fine, but if you want the centroid of the polygon, you'd have to implement this formula, which btw is not very difficult. Please remember that in the general case of an irregular polygon, which is your case, these two centroids will be different (otherwise this formula wouldn't exist).

Solution 5:

Building on Myobis' and pragmar's answers, it's not necessary to alter the array by duplicating the first element. In fact, in their implementation the first iteration of the for loop doesn't do anything because pts[i] and pts[j] are identical.

Here is the same algorithm with some optimizations (originally ported from Finding the centroid of a polygon?):

function get_polygon_centroid(points) {
    //Correction for very small polygons:
    const x0 = points[0].x , y0 = points[0].y;

    let x = 0, y = 0, twiceArea = 0;

    let prev = points[points.length - 1];
    for (const next of points)
    {
        const x1 = prev.x - x0, y1 = prev.y - y0,
              x2 = next.x - x0, y2 = next.y - y0,
              a  = x1 * y2 - x2 * y1;

        twiceArea += a;
        x += (x1 + x2) * a;
        y += (y1 + y2) * a;

        prev = next;
    }

    const factor = 3 * twiceArea;  // 6 * twiceArea/2
    x /= factor;
    y /= factor;

    return { x: x + x0, y: y + y0 };
}

const points = [
    { x: 78.0001462, y: 40.0008827 },
    { x: 78.0000228, y: 40.0008940 },
    { x: 78.0000242, y: 40.0009264 },
];
console.log(get_polygon_centroid(points));

JavaScript College