algorithm - Arduino凸包算法

Question

我正在使用 Arduino 进行一个项目，该项目需要计算由许多点组成的多边形的面积。我使用测量员定理，

但是这些点是随机顺序的，而不是（逆时针）顺时针。有些人制作交叉的线，他们制作像领结或沙漏一样的多边形，这不适用于测量员的定理，所以我需要按（逆）顺时针顺序对它们进行排序。最简单的方法是什么？

Answer 1

您不需要找到凸包。只需从一堆逆时针排列的点中使用面积公式：

http://en.wikipedia.org/wiki/Polygon#Area_and_centroid

float totalArea = 0.0;
for(i=0; i<N; i++) {
    float parallelogramArea = (point[i].x*point[i+1].y - point[i+1].x*point[i].y)
    float triangleArea = parallelogramArea / 2.0;
    totalArea += triangleArea;
}
// or divide by 2 out here for efficiency

面积公式来自取每条边 AB，并通过取叉积（给出平行四边形的面积）并将其切成两半（因子）来计算边缘和原点（三角形 ABO）之间的（有符号）面积1/2)。当一个人环绕多边形时，这些正三角形和负三角形将重叠，原点和多边形之间的区域将被抵消并为0，而只剩下里面的区域。这就是为什么这个公式被称为测量者公式的原因，因为“测量者”在原点；如果逆时针方向，从原点的角度来看，左->右时添加正区域，右->左时添加负区域。

下面给出了数学公式，但没有提供其背后的直觉（如上所示）：

编辑（更改问题后）

如果没有额外的假设，例如“多边形是凸的”，绝对没有办法“得到它们的顺序”。

• 如果多边形是凹的，那么在一般情况下，如果没有很多额外的假设，它几乎是不可能的（证明：考虑一个位于凸包内的点，但其邻居不在；您可以使用该点构建许多可能的有效多边形，它的邻居和他们的邻居）。

• 如果多边形是凸多边形，您需要做的就是按多边形内任意点（例如三个任意点的质心）的角度进行排序。

Answer 2

您可以找到这些点的重心(cx,cy)，然后计算这些点相对于 的角度(cx,cy)。

angle[i] = atan2(y[i]-cy, x[i]-cx) ; 

然后按角度对点进行排序。

请注意，一组随机点不能描述单个独特的多边形。所以这个方法只会给你一个可能的多边形，而不一定是你手动连接点时得到的多边形。