多邊形的重心

Question

我想寫一個PHP函數來計算多邊形的重心。

我看過其他類似的問題，但我似乎無法找到解決方案。

我的問題是，我需要能夠計算正常和不規則多邊形甚至自相交多邊形的重心。

這可能嗎？

我也讀過：http://paulbourke.net/geometry/polyarea/ 但這隻限於非自相交多邊形。

我該怎麼做？你能指點我正確的方向嗎？

Answer 1

比重（也被稱爲「質量中心」或「質心」可以用下面的公式來計算的中心：從Wikipedia提取

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 

： 非自相交的質心由n個頂點（X0，Y0），（X1，Y1）限定封閉的多邊形，...，（XN-1，炔1）是點（CX，CY），其中


和其中A是多邊形的簽名區域，

實施例使用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 

有關的詳細信息檢查此website或Wikipedia。

希望它有幫助。

問候！

Answer 2

在寒冷的C++和同時假設

你有一個VEC 2結構與x和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); 
} 

，並在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 
    }; 
} 

或好老c和在假定你具有x和y屬性的Point結構：

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

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

更多詳情：

PHP: How to determine the center of a Polygon

Answer 4

這是我在接受的解決方案的Java實現，我增加了一個額外條件檢查，因爲我的一些多邊形持平，沒有區域，而不是給我中點，它返回（0,0）。因此，在這種情況下，我引用了一個簡單地平均頂點的不同方法。最後的四捨五入是因爲我想將輸出對象保留爲整數，即使它不精確，但我歡迎您將其刪除。另外，因爲我所有的積分都是正整數，所以檢查對我來說是有意義的，但對於你來說，增加一個區域檢查== 0也是有意義的。

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

既然大家都是爲實現此算法中以不同的語言這麼多的樂趣，這裏是我的版本，我敲了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)