¿Cómo se puede encontrar el centroide de un polígono irregular cóncavo en JavaScript?

Question

¿Cómo se puede encontrar el centroide de un polígono irregular cóncavo dados sus vértices en JavaScript?

Quiero pasar un conjunto de puntos x, y a una función de JavaScript y recibir un punto 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); 

La variable my_points solamente se supone que representa el formato de los puntos que debe darse, no representan el conteo específico de puntos que debe darse.

centroide devuelto será un punto en algún lugar dentro del polígono.

El objetivo final sería agregar un marcador en el centro de gravedad de un polígono en una aplicación Google Maps V3.

Answer 1

Para el centroide de la superficie 2D (que es probable que sea lo que necesita), Lo mejor es comenzar con a little bit of maths.

que lo adaptaron para su propia notación:

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

Esto es bastante simple de hacer. El centroid of a finite set of k pointsx , x , ... x _k se describe por la fórmula

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

Eso significa que solo podemos añadir todos los puntos y luego dividir por el número de puntos, como este:

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 3

Si no está ocasionales acerca de la definición de 'centro de gravedad', this es la fórmula para el centro de gravedad de un polígono. Como puede ver, es lo suficientemente más complicado que el centroide de un conjunto de puntos. Si puede hacer con el centroide de los puntos, está bien, pero si quiere el centroide del polígono, tendría que implementar esta fórmula, que por cierto no es muy difícil. Recuerde que en el caso general de un polígono irregular, que es su caso, , estos dos centroides serán diferentes (de lo contrario, esta fórmula no existiría).

Answer 4

La respuesta aceptada tiene un problema que se vuelve importante a medida que el área del polígono se hace más pequeña. No sería visible en la mayoría de los casos, pero puede dar lugar a algunos resultados extraños en dimensiones muy pequeñas. Aquí hay una actualización de esa solución para dar cuenta de este problema.

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

Aquí hay un caso de un centroide acabe fuera de un pequeño polígono para cualquier persona curioso en cuanto a lo que estoy hablando:

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 }