我有一组位于图像上的点。这组点形成了一个不规则的封闭形状。我需要找到这个形状的面积。是否有任何用于计算面积的正常算法?或者库中是否有任何支持,例如 boost?我正在使用 C++。
7 回答
如果您的多边形很简单(除了成对的连续线段外,它没有任何共同点),那么维基百科会为您提供帮助:
面积公式为
(假设最后一点与第一点相同)
您可以轻松地将其实现为
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;
当然顶点必须根据它们在多边形中的自然跟随来排序。
有一个求和公式。
您可能想要更精确,甚至可能提供图形示例。
例如,如果您拥有的点仅仅是像素,那么像素数等于面积。但是如果这些点是多边形的角,那么多边形的面积就不是那么容易确定的了。您将使用polygon triangulation,并对获得的三角形的面积求和。
注意:如果您不知道点的顺序并且不能保证您的多边形是凸的,则无法确定形状的顺序,因为产生多边形的点可能有多个可能的顺序。如果您确实知道多边形是凸的,那么确定点的顺序很容易。仅从一个特定点按角度对点进行排序,第一个点是在其自身和初始点之间形成一条线的点,这样所有其他点都在该线的同一侧。这个过程形成的三角形也可以用来计算面积。
Boost.Geometry 中支持多边形的面积计算(这还没有被 boost 接受,而且使用起来非常混乱)。否则,您必须首先确定由您的点定义的多边形。从外观上看,您的所有点都是多边形的顶点,因此这只是正确排序点集的简单问题。另一种可能性是您正在寻找点集的凸包(请参阅http://en.wikipedia.org/wiki/Convex_hull_algorithms)。
不谦虚,我请您参考我对另一个问题的回答重叠圆圈的组合区域。Monte Carlo 是强大的、易于并行化的,并且最终会为您提供所需准确性的答案。
最简单的方法可能是对您的形状进行三角测量并计算三角形的面积。Dave Eberly 有一个名为(Boost license)的库,可以帮助进行三角测量;这里有更多信息。例如,寻找 TriangulateEC。