寻找多边形的质心
Finding the centroid of a polygon
我用下面的代码来求一个多边形的质心(我没有写代码,它来自另一个问题)。
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 命令的图片:
我不明白为什么当点的顺序改变但点仍然相同时它不起作用。
事实证明,问题是 Point
有未签名的成员。还有一个潜在的次要问题,关于浮点数舍入问题。
在这个算法中,如果风序是错误的,计算的面积将是负数,当你做类似的事情时
centroid.x += (x0 + x1) * a;
你会得到一个不正确的值,因为 a
是负数而 centroid.x
是无符号的。
您应该将中间质心值存储为某种浮点数,这样 a) 您就不会遇到这些 signed/unsigned 问题,并且 b) 这样您就不会在每个问题上都出现舍入错误顶点;我不确定这些错误最终是否会大到足以给您带来问题,但是在可以如此轻松避免的情况下冒险冒险似乎很愚蠢。当你 return.
时,你应该在最后转换为 unsigned int (或其他)
我用下面的代码来求一个多边形的质心(我没有写代码,它来自另一个问题)。
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 命令的图片:
我不明白为什么当点的顺序改变但点仍然相同时它不起作用。
事实证明,问题是 Point
有未签名的成员。还有一个潜在的次要问题,关于浮点数舍入问题。
在这个算法中,如果风序是错误的,计算的面积将是负数,当你做类似的事情时
centroid.x += (x0 + x1) * a;
你会得到一个不正确的值,因为 a
是负数而 centroid.x
是无符号的。
您应该将中间质心值存储为某种浮点数,这样 a) 您就不会遇到这些 signed/unsigned 问题,并且 b) 这样您就不会在每个问题上都出现舍入错误顶点;我不确定这些错误最终是否会大到足以给您带来问题,但是在可以如此轻松避免的情况下冒险冒险似乎很愚蠢。当你 return.
时,你应该在最后转换为 unsigned int (或其他)