多边形的重心

Question

我正在尝试编写一个 PHP 函数来计算多边形的重心。

我看过其他类似的问题，但我似乎找不到解决方案。

我的问题是我需要能够计算规则和不规则多边形甚至自相交多边形的重心。

这可能吗？

我也读过：http://paulbourke.net/geometry/polyarea/ 但这仅限于非自相交的多边形。

我该怎么做？你能给我指出正确的方向吗？

Answer 1

重心（也称为“质量中心”或“质心”可以用以下公式计算：

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,yn−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

有关更多信息，请查看此网站或维基百科。

希望有帮助。

问候！

Answer 2

在冷 c++ 中，同时假设您有一个具有 x 和 y 属性的 Vec2 结构：

Vec2 findCentroid(const 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 结构：

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

Swift 4，基于上面给出的 c 答案

/// 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)
}

Answer 4

因为我们都在用不同的语言实现这个算法时玩得很开心，所以这是我为 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)

Answer 5

这是我在 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 6

在 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：如何确定多边形的中心

Answer 7

这是我在 Python 中的实现，基于 Joseph 的 C++ 实现。我认为它比其他 python 答案更清楚。

def find_centroid(polygon):
    """ Computes the centroid (a.k.a. center of gravity) for a non-self-intersecting polygon.

    Parameters
    ----------
    polygon : list of two-dimensional points (points are array-like with two elements)
        Non-self-intersecting polygon (orientation does not matter).

    Returns
    -------
    center_of_gravity : list with 2 elements
        Coordinates (or vector) to the centroid of the polygon.
    """
    offset = polygon[0]
    center_of_gravity = [0.0, 0.0]
    double_area = 0.0
    for ii in range(len(polygon)):
        p1 = polygon[ii]
        p2 = polygon[ii-1]
        f = (p1[0]-offset[0])*(p2[1]-offset[1]) - (p2[0]-offset[0])*(p1[1]-offset[1])
        double_area += f
        center_of_gravity[0] += (p1[0] + p2[0] - 2*offset[0]) * f
        center_of_gravity[1] += (p1[1] + p2[1] - 2*offset[1]) * f
    center_of_gravity[0] = center_of_gravity[0] / (3*double_area) + offset[0]
    center_of_gravity[1] = center_of_gravity[1] / (3*double_area) + offset[1]
    return center_of_gravity
    # If you want to return both the CoG and the area, comment the return above
    return center_of_gravity, abs(double_area/2)

Answer 8

根据这个答案

在 C# 中：

public static Point findCentroid(List<Point> pts)
    {
        Point off = pts[0];
        double twicearea = 0;
        double x = 0;
        double y = 0;
        Point p1, p2;
        double f;
        for (int i = 0, j = pts.Count - 1; i < pts.Count; 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 new Point(x / f + off.x, y / f + off.y);
    }

Answer 9

这是基于 Joseph 的 C++ 答案。

变化：

• 现在需要两个迭代器。
• 角落情况，单个点和一条线，被处理。
• 它支持任何可通过结构化绑定分解的类型，如

  std::pair<float, float>

  和sfml的

  sf::Vector2<T>

  .
• 它还支持

  x

  和

  y

  （或

  first

  和

  second

  在

  std::pair

  s 的情况下）的不同类型。

#include <iterator>
#include <type_traits>

template<class Iter, class V2 = typename std::iterator_traits<Iter>::value_type>
V2 findCentroid(Iter first, Iter last) {
    if(first == last) return V2{};                   // {0,0} or throw or leave UB

    if(auto next = std::next(first); next == last) { // a single point
        return *first;                                
    } else if(std::next(next) == last) {             // a line
        const auto& [x1, y1] = *first;
        const auto& [x2, y2] = *next;
        return V2{(x1 + x2) / 2, (y1 + y2) / 2};     // midpoint of the line
    }

    // three or more points:
    const auto& [offx, offy] = *first;
    using T1 = std::remove_cvref_t<decltype(offx)>;
    using T2 = std::remove_cvref_t<decltype(offy)>;
    T1 x{};
    T2 y{};
    decltype((x * y) - (x * y)) twicearea{}, f;

    for(auto prev = std::prev(last); first != last; prev = first++) {
        const auto& [p1x, p1y] = *first;
        const auto& [p2x, p2y] = *prev;
        f = (p1x - offx) * (p2y - offy) - (p2x - offx) * (p1y - offy);
        twicearea += f;
        x += (p1x + p2x - 2 * offx) * f;
        y += (p1y + p2y - 2 * offy) * f;
    }

    f = twicearea * 3;

    return V2{static_cast<T1>(x / f + offx), static_cast<T2>(y / f + offy)};
}

---

旁注：如果你来到这里是因为你使用 sfml 的

sf::ConvexShape

创建多边形并希望旋转点位于多边形的质心（就像我所做的那样），这里有一个使用上述辅助函数的辅助类：

#include <SFML/Graphics/ConvexShape.hpp>

#include <cstddef>
#include <initializer_list>

class Polygon : public sf::ConvexShape {
public:

    inline Polygon(std::initializer_list<sf::Vector2f> pnts) :
        sf::ConvexShape(pnts.size()) 
    {
        for(std::size_t idx = 0; idx < pnts.size(); ++idx) {
            setPoint(idx, pnts.begin()[idx]);
        }
        setOrigin(findCentroid(pnts.begin(), pnts.end()));
    }

};

初始化

Polygon

的容器将很简单：

const std::array<Polygon, 2> shapes{{
    {{0,10}, {50,0}, {120,10}, {100,90}, {30,100}, {0,50}}, // one Polygon
    {{30,0}, {47, 10}, {44, 20}}                            // another Polygon
}};