如何在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应用程序中的多边形的中心点添加一个标记。

- iambriansreed

---

我找到了这段代码：http://jsfiddle.net/SXde5/ - Joe

@AlexKorban 中心点 != 质心 - “凹多边形” - iambriansreed

正如Zevan所建议的那样，可以在http://paulbourke.net/geometry/polyarea/javascript.txt找到JavaScript质心函数。不完全确定它是否能处理凸多边形，但附带的插图表明它可以。 - Alex Korban

不确定我是否理解了最后一条评论，但凹多边形的质心并不总是包含在多边形内。 - ellisbben

@Zevan 提供的 polyarea 链接返回 404，我猜可能是以下链接 http://paulbourke.net/geometry/polygonmesh/，其中包含一个质心函数。JavaScript 代码位于 http://paulbourke.net/geometry/polygonmesh/javascript.txt。该网站似乎性能非常差，所以请准备等待。 - user254694

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

- Myobis

---

正如维基百科在参考文章中所述，需要注意的是：“假定顶点按其沿多边形周长的出现顺序编号，并且顶点（xn，yn）被假定为与（x0，y0）相同”。 - Fgblanch

如果 (x0, y0) != (xn, yn)，则调整以自动关闭多边形。 - Myobis

我认为在第一行 var first = t[0] 应该改为 var first = pts[0]。 - user993683

感谢 @JoeRocc 发现这个问题。 - Myobis

在 pts.push(first) 之前最好先克隆数组 pts = [...pts]。 - ZoomAll

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 }

- pragmar

---

处理基本方法的实际问题加1分，令人惊讶的是在我查阅的维基百科和其他地方都没有提到。然而，解决方案中存在一个错误：以 x += (p1.y + p2.y ... 和 y += (p1.x + p2.x ... 开头的行当然应该是 x += (p1.x + p2.x ... 和 y += (p1.y + p2.y ...。 - Jonas

哎呀！感谢你发现了这个问题，Jonas。已经修复了。 - pragmar

这是什么原因引起的？舍入误差吗？ - Sphinxxx

Python版本：https://gist.github.com/marcbln/4fc3d5179d06adb5a82551db43d80b07 - qwertz

Answer 3

如果您希望将标签放置在凹多边形内部，则上面的答案效果不是很好。凹多边形的重心很可能在多边形外部。 有一个名为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));

- Henry Luo

Answer 4

这很容易做到。一个有限点集(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;
} 

- Peter Olson

---

多边形的质心（centroid）在同一维基百科页面中有定义，它与构成多边形的点的质心不同。你对若干点的质心的定义是正确的。但是，任何区域的质心被定义为其质量中心的位置，通常会与顶点的质心不同。 - Abhranil Das

我试图更正“points”引用中缺失的“i”，但是这个愚蠢的编辑器要求我改变至少6个字符，所以我将示例中的方法名更改为驼峰式（这在JS中更常见） - 希望这样可以行吗Peter Olson？（我不知道如何否则更改示例，使其可以正常工作，而不会因拼写错误而抛出错误） - csuwldcat

Answer 5

如果您对“质心”的定义不太清楚，这里有关于多边形质心的公式。可以看出，它比点集的质心要复杂得多。如果您只需要计算点的质心，那就很好。但是，如果您需要计算多边形的质心，则需要实现此公式，不过这并不难。请记住，在不规则多边形的一般情况下，即您的情况下，这两个质心将不同（否则该公式不存在）。

- Abhranil Das

---

你提供的质心仍然是一组点的质心；这组点只是无限的... :) - ellisbben

当然，我只是不想详细解释它。在另一种情况下，我们将考虑点作为相等质量的质点，而在这里我们考虑质量在多边形内均匀分布。 - Abhranil Das

Answer 6

在Myobis'和pragmar's的答案基础上，没有必要通过复制第一个元素来修改数组。 事实上，在他们的实现中，for循环的第一次迭代并不会做任何事情，因为pts[i]和pts[j]是相同的。

这里是同样具有一些优化的算法（最初从如何找到多边形的重心？移植）：

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

- Sphinxxx