algorithm - triangulo - Centro de gravedad de un polígono.
centroide de un triangulo (6)
Estoy tratando de escribir una función de PHP que calcule el centro de gravedad de un polígono.
He mirado 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 polígonos que se intersectan.
¿Es eso posible?
También he leído eso: http://paulbourke.net/geometry/polyarea/ Pero esto está restringido a polígonos que no se intersectan a sí mismos.
¿Cómo puedo hacer esto? ¿Me puede indicar la dirección correcta?
El centro de gravedad (también conocido como "centro de masa" o "centroide" se puede calcular 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ído de Wikipedia : el centroide de un polígono cerrado que no se auto interseca 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 usando 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 visite este http://paulbourke.net/geometry/polyarea/ o Wikipedia .
Espero eso ayude.
¡Saludos!
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;
}
Lee mas en:
Esta fue mi implementación en Java de la solución aceptada, agregué una verificación condicional adicional porque algunos de mis polígonos eran planos y no tenían área, y en lugar de darme el punto medio, estaba regresando (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 sea impreciso, pero le invito a que elimine ese bit. Además, dado que todos mis puntos eran enteros positivos, el control tenía sentido para mí, pero para usted, agregar un control 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));
}
Swift 4, basado en la respuesta c dada arriba
/// Given an array of points, find the "center of gravity" of the points
/// - Parameters:
/// - points: Array of points
/// - Returns:
/// - Point or nil if input points count < 3
static func centerOfPoints(points: [CGPoint]) -> CGPoint? {
if points.count < 3 {
return nil
}
var sum: CGFloat = 0
var pSum: CGPoint = .zero
for i in 0..<points.count {
let p1 = points[i]
let p2 = points[(i+1) % points.count]
let cross = p1.x * p2.y - p1.y * p2.x
sum += cross
pSum = CGPoint(x:((p1.x + p2.x) * cross) + pSum.x,
y:((p1.y + p2.y) * cross) + pSum.y)
}
let z = 1 / (3 * sum)
return CGPoint(x:pSum.x * z,
y:pSum.y * z)
}
Ya que todos nos estamos divirtiendo mucho al implementar este algoritmo en diferentes idiomas, aquí está mi versión que encontré 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)
en frío c ++ y al tiempo que supones que tienes 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 buena c y mientras asumas que tienes una estructura de puntos con las propiedades x e y:
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);
}