algorithm - Arduino凸包算法

Question

我正在使用 Arduino 开发一个项目，该项目需要计算由许多点组成的多边形的面积。我用 surveyor's theorem ,

但是点是随机排列的，不是(逆)时针的。有些制作交叉线，他们制作多边形，如领结或沙漏，这不适用于测量员定理，因此我需要按(逆)时针顺序对它们进行排序。最简单的方法是什么？

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，只剩下里面的面积。这就是为什么该公式被称为测量员公式的原因，因为“测量员”位于原点；如果逆时针方向，从原点看，左->右时加正面积，右->左加负面积。

数学公式如下，但不提供其背后的直觉(如上所示):

编辑(问题已更改后)

没有额外的假设，例如，绝对没有办法“得到他们的订单”。 “多边形是凸的”。

• 如果多边形是凹的，在一般情况下，如果不进行大量额外假设，这几乎是不可能的(证明:考虑一个位于凸包内但其邻居不在凸包内的点；有许多可能的有效多边形你可以使用那个点、它的邻居和它们的邻居来构造)。

• 如果多边形是凸的，您需要做的就是根据多边形内任意点的角度排序(例如，三个任意点的质心)。