c++ - центра - центроид трапеции




Поиск центра тяжести многоугольника? (3)

Чтобы получить центр, я попытался, для каждой вершины, добавить к сумме, делить на число вершин.

Я также попытался найти самую верхнюю, самую нижнюю -> получить середину ... найти крайний левый крайний край, найти среднюю точку.

Оба они не вернули идеальный центр, потому что я полагаюсь на центр, чтобы масштабировать многоугольник.

Я хочу масштабировать свои полигоны, поэтому я могу разместить вокруг них границу.

Каков наилучший способ найти центроид многоугольника, учитывая, что многоугольник может быть вогнутым, выпуклым и иметь много сторон разной длины?


Разбейте его на треугольники, найдите область и центр тяжести каждого, затем вычислите среднее значение всех частичных центроидов, используя частичные области в качестве весов. С вогнутостью некоторые области могут быть отрицательными.


Формула приведена here .

Для тех, кто с трудом понимает сигма-нотацию в этих формулах, вот какой-то код на C ++, показывающий, как выполнить вычисление:

#include <iostream>

struct Point2D
{
    double x;
    double y;
};

Point2D compute2DPolygonCentroid(const Point2D* vertices, int vertexCount)
{
    Point2D centroid = {0, 0};
    double signedArea = 0.0;
    double x0 = 0.0; // Current vertex X
    double y0 = 0.0; // Current vertex Y
    double x1 = 0.0; // Next vertex X
    double y1 = 0.0; // Next vertex Y
    double a = 0.0;  // Partial signed area

    // For all vertices except last
    int i=0;
    for (i=0; i<vertexCount-1; ++i)
    {
        x0 = vertices[i].x;
        y0 = vertices[i].y;
        x1 = vertices[i+1].x;
        y1 = vertices[i+1].y;
        a = x0*y1 - x1*y0;
        signedArea += a;
        centroid.x += (x0 + x1)*a;
        centroid.y += (y0 + y1)*a;
    }

    // Do last vertex separately to avoid performing an expensive
    // modulus operation in each iteration.
    x0 = vertices[i].x;
    y0 = vertices[i].y;
    x1 = vertices[0].x;
    y1 = vertices[0].y;
    a = x0*y1 - x1*y0;
    signedArea += a;
    centroid.x += (x0 + x1)*a;
    centroid.y += (y0 + y1)*a;

    signedArea *= 0.5;
    centroid.x /= (6.0*signedArea);
    centroid.y /= (6.0*signedArea);

    return centroid;
}

int main()
{
    Point2D polygon[] = {{0.0,0.0}, {0.0,10.0}, {10.0,10.0}, {10.0,0.0}};
    size_t vertexCount = sizeof(polygon) / sizeof(polygon[0]);
    Point2D centroid = compute2DPolygonCentroid(polygon, vertexCount);
    std::cout << "Centroid is (" << centroid.x << ", " << centroid.y << ")\n";
}

Я тестировал это только для квадратного многоугольника в верхнем правом квадранте x / y.

Если вы не возражаете выполнять две (потенциально дорогостоящие) операции дополнительного модуля в каждой итерации, то вы можете упростить предыдущую функцию compute2DPolygonCentroid следующим образом:

Point2D compute2DPolygonCentroid(const Point2D* vertices, int vertexCount)
{
    Point2D centroid = {0, 0};
    double signedArea = 0.0;
    double x0 = 0.0; // Current vertex X
    double y0 = 0.0; // Current vertex Y
    double x1 = 0.0; // Next vertex X
    double y1 = 0.0; // Next vertex Y
    double a = 0.0;  // Partial signed area

    // For all vertices
    int i=0;
    for (i=0; i<vertexCount; ++i)
    {
        x0 = vertices[i].x;
        y0 = vertices[i].y;
        x1 = vertices[(i+1) % vertexCount].x;
        y1 = vertices[(i+1) % vertexCount].y;
        a = x0*y1 - x1*y0;
        signedArea += a;
        centroid.x += (x0 + x1)*a;
        centroid.y += (y0 + y1)*a;
    }

    signedArea *= 0.5;
    centroid.x /= (6.0*signedArea);
    centroid.y /= (6.0*signedArea);

    return centroid;
}

boost::geometry::centroid(your_polygon, p);




vector-graphics