如何在JavaScript中找到凹形不规则多边形的质心？

Question

如何在JavaScript中找到凹顶不规则多边形的质心？

我想将一组x,y点传递给JavaScript函数并给出一个x,y点.

var my_points = [{x:3,y:1},{x:5,y:8},{x:2,y:9}];

function get_polygon_centroid(points){
    // answer
}

var my_centroid = get_polygon_centroid(my_points);

该my_points变量仅应表示要给出的点的格式,而不是表示要给出的点的具体计数.

返回的质心将是多边形内的某个点.

最终目标是在Google Maps V3应用程序中的多边形的质心处添加标记.

Answer 1

对于2D表面的质心(这可能是你需要的),最好是从一点点数学开始.

我在这里根据你自己的符号进行了调整:

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

Answer 2

接受的答案有一个问题,随着多边形的面积变小,这个问题变得突出.它在大多数情况下都不可见,但可能会在非常小的尺寸上产生一些奇怪的结果.以下是解决此问题的解决方案的更新.

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

这是一个质心结束在一个小多边形之外的情况,对于任何好奇我正在谈论的内容:

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 }

Answer 3

这很容易做到。有限集k点 x ₁ , x ₂ , ... x _k的质心由以下公式描述

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

这意味着我们可以将所有点相加，然后除以点数，如下所示：

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

Answer 4

如果您希望标签位于凹不规则多边形内，那么上述答案效果不太好。凹多边形的质心很可能位于多边形之外。

这个Polylabel库可以很好地解决这个问题。这篇博客文章提供了该算法的详细信息。如果您想在浏览器中使用该库并且不想自己打包，可以从该页面下载该库。

使用该库的代码示例：

function get_polygon_centroid(points) {
    var pts = points.map(p => [p.x, p.y]);  // convert {x:x, y:y} into [x, y]
    var centroid = polylabel([pts]);
    return {x:centroid[0], y:centroid[1]};
}
var my_points = [{x:3,y:1},{x:5,y:8},{x:2,y:9}];
console.log('centroid', get_polygon_centroid(my_points));