Arduino凸包算法

Question

我正在使用一个需要计算由多个点组成的多边形区域的Arduino的项目。我用surveyor's theorem，

但点是随机的顺序，而不是（计数器）顺时针方向旋转。有些线条是交叉的，并且它们使得多边形像蝴蝶结或沙漏形式，这对于验船师的定理不起作用，所以我需要按顺时针顺序排列它们。最简单的方法是什么？

Answer 1

你可以找到点的重力(cx,cy)的中心，然后计算出点相对于(cx,cy)的角度。

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

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

只要注意一组随机点不能描述一个唯一的多边形。所以这种方法只会给你一个可能的多边形，而不一定是你手动连接点所获得的多边形。

Answer 2

你不需要找到凸包。只需使用面积公式从一堆点的有序逆时针：

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，而只剩下内部区域。这就是为什么这个公式被称为验船师公式，因为“验船师”在原点;如果逆时针旋转，从左到右增加正面积，从原点向右 - >左增加负面面积。

的数学公式如下，但不提供其背后的直觉（如上面给出）：

编辑（问题已被改变之后）

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

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

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