Нахождение центроида многоугольника

Я использую следующий код, чтобы найти центр тяжести многоугольника (я не писал код, это из другого вопроса).

Point compute2DPolygonCentroid(const std::vector<Point> vertices) {
Point centroid;
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
for (int i = 0; i < vertices.size() - 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.back().x;
y0 = vertices.back().y;
x1 = vertices.front().x;
y1 = vertices.front().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;
}

Проблема в том, что он работает ТОЛЬКО когда точки во входном векторе vertices в порядке по часовой стрелке. Когда точки расположены против часовой стрелки, это не работает. Вот картина того, что я имею в виду под CW && заказ ccw:

введите описание изображения здесь

Я не понимаю, почему это не работает, когда меняется только порядок точек, но точки остаются прежними.

0

Решение

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

В этом алгоритме, если порядок ветра неправильный, вычисленная площадь будет отрицательной, и когда вы делаете что-то вроде

centroid.x += (x0 + x1) * a;

вы получите неправильное значение, потому что a будет отрицательным и centroid.x без знака

Вы должны хранить промежуточные значения центроида в виде плавающей запятой некоторого вида, чтобы а) вы не получали этих проблем со знаком / без знака и б) чтобы не возникало ошибок округления в каждой вершине; Я не уверен, что эти ошибки окажутся достаточно большими, чтобы вызвать у вас проблемы, но глупо рисковать, когда их так легко избежать. Вы должны привести к unsigned int (или какому-либо другому) в самом конце, когда вы вернетесь.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]