c++ - 不规则形状的区域

Question

我有一组位于图像上的点。这组点形成了一个不规则的封闭形状。我需要找到这个形状的面积。是否有任何用于计算面积的正常算法？或者库中是否有任何支持，例如 boost？我正在使用 C++。

Answer 1

如果您的多边形很简单（除了成对的连续线段外，它没有任何共同点），那么维基百科会为您提供帮助：

面积公式为

（假设最后一点与第一点相同）

您可以轻松地将其实现为

float area = 0.0f;

for (int i = 0; i < numVertices - 1; ++i)
  area += point[i].x * point[i+1].y - point[i+1].x * point[i].y;

area += point[numVertices-1].x * point[0].y - point[0].x * point[numVertices-1].y;

area = abs(area) / 2.0f;

当然顶点必须根据它们在多边形中的自然跟随来排序。

Answer 2

有一个求和公式。

Answer 3

您可能想要更精确，甚至可能提供图形示例。

例如，如果您拥有的点仅仅是像素，那么像素数等于面积。但是如果这些点是多边形的角，那么多边形的面积就不是那么容易确定的了。您将使用polygon triangulation，并对获得的三角形的面积求和。

Answer 4

注意：如果您不知道点的顺序并且不能保证您的多边形是凸的，则无法确定形状的顺序，因为产生多边形的点可能有多个可能的顺序。如果您确实知道多边形是凸的，那么确定点的顺序很容易。仅从一个特定点按角度对点进行排序，第一个点是在其自身和初始点之间形成一条线的点，这样所有其他点都在该线的同一侧。这个过程形成的三角形也可以用来计算面积。

Answer 5

Boost.Geometry 中支持多边形的面积计算（这还没有被 boost 接受，而且使用起来非常混乱）。否则，您必须首先确定由您的点定义的多边形。从外观上看，您的所有点都是多边形的顶点，因此这只是正确排序点集的简单问题。另一种可能性是您正在寻找点集的凸包（请参阅http://en.wikipedia.org/wiki/Convex_hull_algorithms）。

Answer 6

不谦虚，我请您参考我对另一个问题的回答重叠圆圈的组合区域。Monte Carlo 是强大的、易于并行化的，并且最终会为您提供所需准确性的答案。

Answer 7

最简单的方法可能是对您的形状进行三角测量并计算三角形的面积。Dave Eberly 有一个名为（Boost license）的库，可以帮助进行三角测量；这里有更多信息。例如，寻找 TriangulateEC。