Centro de gravedad de un polígono

Question

Estoy tratando de escribir una función PHP que calculará el centro de gravedad de un polígono.

He examinado las otras preguntas similares pero parece que no puedo encontrar una solución a esto.

Mi problema es que necesito poder calcular el centro de gravedad para polígonos regulares e irregulares e incluso para polígonos auto intersectados.

¿Es esto posible?

También he leído que: http://paulbourke.net/geometry/polyarea/ Pero esto está restringido a polígonos que no se intersecan.

¿Cómo puedo hacer esto? ¿Puedes señalarme la dirección correcta?

Answer 1

El centro de gravedad (también conocido como "centro de masa" o "centroide" puede calcularse con la siguiente fórmula:

X = SUM[(Xi + Xi+1) * (Xi * Yi+1 - Xi+1 * Yi)]/6/A 
Y = SUM[(Yi + Yi+1) * (Xi * Yi+1 - Xi+1 * Yi)]/6/A 

extraídos de Wikipedia: El centroide de un no-auto-intersección polígono cerrado definido por n vértices (x0, y0), (x1, y1), ..., (xn-1, YN-1) es el punto (Cx, Cy), donde


y donde A es el área firmada del polígono,

Ejemplo utilizando VBasic:

' Find the polygon's centroid. 
Public Sub FindCentroid(ByRef X As Single, ByRef Y As _ 
    Single) 
Dim pt As Integer 
Dim second_factor As Single 
Dim polygon_area As Single 

    ' Add the first point at the end of the array. 
    ReDim Preserve m_Points(1 To m_NumPoints + 1) 
    m_Points(m_NumPoints + 1) = m_Points(1) 

    ' Find the centroid. 
    X = 0 
    Y = 0 
    For pt = 1 To m_NumPoints 
     second_factor = _ 
      m_Points(pt).X * m_Points(pt + 1).Y - _ 
      m_Points(pt + 1).X * m_Points(pt).Y 
     X = X + (m_Points(pt).X + m_Points(pt + 1).X) * _ 
      second_factor 
     Y = Y + (m_Points(pt).Y + m_Points(pt + 1).Y) * _ 
      second_factor 
    Next pt 

    ' Divide by 6 times the polygon's area. 
    polygon_area = PolygonArea 
    X = X/6/polygon_area 
    Y = Y/6/polygon_area 

    ' If the values are negative, the polygon is 
    ' oriented counterclockwise. Reverse the signs. 
    If X < 0 Then 
     X = -X 
     Y = -Y 
    End If 
End Sub 

Para más información visita este website o Wikipedia.

Espero que ayude.

¡Recuerdos!

Answer 2

en c frío ++ y mientras asumiendo que tiene una estructura Vec2 con propiedades x e y:

const Vec2 findCentroid(Vec2* pts, size_t nPts){ 
    Vec2 off = pts[0]; 
    float twicearea = 0; 
    float x = 0; 
    float y = 0; 
    Vec2 p1, p2; 
    float f; 
    for (int i = 0, j = nPts - 1; i < nPts; j = i++) { 
     p1 = pts[i]; 
     p2 = pts[j]; 
     f = (p1.x - off.x) * (p2.y - off.y) - (p2.x - off.x) * (p1.y - off.y); 
     twicearea += f; 
     x += (p1.x + p2.x - 2 * off.x) * f; 
     y += (p1.y + p2.y - 2 * off.y) * f; 
    } 

    f = twicearea * 3; 

    return Vec2(x/f + off.x, y/f + off.y); 
} 

y en javascript:

function findCentroid(pts, nPts) { 
    var off = pts[0]; 
    var twicearea = 0; 
    var x = 0; 
    var y = 0; 
    var p1,p2; 
    var f; 
    for (var i = 0, j = nPts - 1; i < nPts; j = i++) { 
     p1 = pts[i]; 
     p2 = pts[j]; 
     f = (p1.lat - off.lat) * (p2.lng - off.lng) - (p2.lat - off.lat) * (p1.lng - off.lng); 
     twicearea += f; 
     x += (p1.lat + p2.lat - 2 * off.lat) * f; 
     y += (p1.lng + p2.lng - 2 * off.lng) * f; 
    } 
    f = twicearea * 3; 
    return { 
    X: x/f + off.lat, 
    Y: y/f + off.lng 
    }; 
} 

o en el bueno de C y mientras se asume que usted tener un struct Point con x e y propiedades:

const Point centroidForPoly(const int numVerts, const Point* verts) 
{ 
    float sum = 0.0f; 
    Point vsum = 0; 

    for (int i = 0; i<numVerts; i++){ 
     Point v1 = verts[i]; 
     Point v2 = verts[(i + 1) % numVerts]; 
     float cross = v1.x*v2.y - v1.y*v2.x; 
     sum += cross; 
     vsum = Point(((v1.x + v2.x) * cross) + vsum.x, ((v1.y + v2.y) * cross) + vsum.y); 
    } 

    float z = 1.0f/(3.0f * sum); 
    return Point(vsum.x * z, vsum.y * z); 
} 

Answer 3

En php:

// Find the polygon's centroid. 
function getCenter($polygon) 
{ 
    $NumPoints = count($polygon); 

    if($polygon[$NumPoints-1] == $polygon[0]){ 
     $NumPoints--; 
    }else{ 
     //Add the first point at the end of the array. 
     $polygon[$NumPoints] = $polygon[0]; 
    } 

    // Find the centroid. 
    $X = 0; 
    $Y = 0; 
    For ($pt = 0 ;$pt<= $NumPoints-1;$pt++){ 
     $factor = $polygon[$pt][0] * $polygon[$pt + 1][1] - $polygon[$pt + 1][0] * $polygon[$pt][1]; 
     $X += ($polygon[$pt][0] + $polygon[$pt + 1][0]) * $factor; 
     $Y += ($polygon[$pt][1] + $polygon[$pt + 1][1]) * $factor; 
    } 

    // Divide by 6 times the polygon's area. 
    $polygon_area = ComputeArea($polygon); 
    $X = $X/6/$polygon_area; 
    $Y = $Y/6/$polygon_area; 

    return array($X, $Y); 
} 


function ComputeArea($polygon) 
{ 
    $NumPoints = count($polygon); 

    if($polygon[$NumPoints-1] == $polygon[0]){ 
     $NumPoints--; 
    }else{ 
     //Add the first point at the end of the array. 
     $polygon[$NumPoints] = $polygon[0]; 
    } 

    $area = 0; 

    for ($i = 0; $i < $NumPoints; $i++) { 
     $i1 = ($i + 1) % $NumPoints; 
     $area += ($polygon[$i][1] + $polygon[$i1][1]) * ($polygon[$i1][0] - $polygon[$i][0]); 
    } 

    $area /= 2; 
    return $area; 
} 

Leer más en:

PHP: How to determine the center of a Polygon

Answer 4

Ésta era mi implementación en Java de la solución aceptada, he añadido una comprobación condicional adicional porque algunos de mis polígonos eran planas y no tenía ninguna zona, y en lugar de darme el punto medio, regresaba (0,0). Por lo tanto, en este caso, hago referencia a un método diferente que simplemente promedia los vértices. El redondeo al final se debe a que quería mantener mi objeto de salida como enteros, aunque es impreciso, pero le doy la bienvenida para que elimine ese bit.Además, como todos mis puntos eran enteros positivos, el cheque tenía sentido para mí, pero para ti, agregar un cheque de área == 0 también tendría sentido.

private Vertex getCentroid() { 

     double xsum = 0, ysum = 0, A = 0; 
     for (int i = 0; i < corners.size() ; i++) { 

      int iPlusOne = (i==corners.size()-1)?0:i+1; 

      xsum += (corners.get(i).getX() + corners.get(iPlusOne).getX()) * (corners.get(i).getX() * corners.get(iPlusOne).getY() - corners.get(iPlusOne).getX() * corners.get(i).getY()); 
      ysum += (corners.get(i).getY() + corners.get(iPlusOne).getY()) * (corners.get(i).getX() * corners.get(iPlusOne).getY() - corners.get(iPlusOne).getX() * corners.get(i).getY()); 
      A += (corners.get(i).getX() * corners.get(iPlusOne).getY() - corners.get(iPlusOne).getX() * corners.get(i).getY()); 
     } 
     A = A/2; 
     if(xsum==0 &&ysum==0) 
     { 
      area = averageHeight/2; 
      return getMidpointCenter(); 
     } 
     double x = xsum/(6 * A); 
     double y = ysum/(6 * A); 
     area = A; 


     return new Vertex((int) Math.round(x), (int) Math.round(y)); 
    } 

Answer 5

Dado que todos estamos pasando tan bien la aplicación de este algo en diferentes idiomas, aquí está mi versión Llamé para Python:

def polygon_centre_area(vertices: Sequence[Sequence[float]]) -> Tuple[Sequence[float], float]: 
    x_cent = y_cent = area = 0 
    v_local = vertices + [vertices[0]] 

    for i in range(len(v_local) - 1): 
     factor = v_local[i][0] * v_local[i+1][1] - v_local[i+1][0] * v_local[i][1] 
     area += factor 
     x_cent += (v_local[i][0] + v_local[i+1][0]) * factor 
     y_cent += (v_local[i][1] + v_local[i+1][1]) * factor 

    area /= 2.0 
    x_cent /= (6 * area) 
    y_cent /= (6 * area) 

    area = math.fabs(area) 

    return ([x_cent, y_cent], area)