Как найти центр тяжести вогнутого неправильного многоугольника в JavaScript? - PullRequest
Новая
       21

Как найти центр тяжести вогнутого неправильного многоугольника в JavaScript?

17 голосов
/ 14 марта 2012

Как найти центр тяжести вогнутого неправильного многоугольника, учитывая его вершины в 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.

Ответы [ 4 ]

26 голосов
/ 30 марта 2012

Для центроида 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 };
}
6 голосов
/ 03 мая 2017

Принятый ответ имеет проблему, которая становится заметной, когда площадь многоугольника становится меньше.В большинстве случаев он не будет виден, но может привести к некоторым странным результатам при очень малых размерах.Вот обновление этого решения, чтобы учесть эту проблему.

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 }
3 голосов
/ 14 марта 2012

Это довольно просто сделать. центроид конечного множества k точек x 1 , x 2 , ... x k описывается формулой

(x 1 + x 2 + ... + 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;
}
1 голос
/ 01 апреля 2012

Если вы не случайны с определением «центроида», это - формула для центроида многоугольника.Как видите, это достаточно сложнее, чем центроид набора точек.Если вы можете сделать с центроидом точек, это нормально, но если вы хотите центроид многоугольника, вам придется реализовать эту формулу, что, между прочим, не очень сложно.Пожалуйста, помните, что в общем случае неправильного многоугольника, как в вашем случае, эти два центроида будут отличаться (в противном случае эта формула не существовала бы).

...