当前位置：文江博客话题详情

Arduino凸包算法

发布于 2024-11-10 13:56:09 字数 353 浏览 3 评论 0原文

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

揽月 2024-11-17 13:56:09

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

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，并通过取叉积（其中给出平行四边形的面积）并将其切成两半（系数 1/2）。当环绕多边形时，这些正三角形和负三角形将重叠，原点和多边形之间的区域将被抵消并为 0，而仅保留内部区域。这就是为什么该公式被称为测量员公式，因为“测量员”是其起源；如果逆时针方向，从原点来看，向左→右时添加正面积，向右→左时添加负面积。

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

<强>编辑（问题改变后）

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

如果多边形是凹的，那么在一般情况下，如果没有很多额外的假设，这几乎是不可能的（证明：考虑一个位于凸包内的点，但其邻居不在凸包内；您可以构造许多可能的有效多边形使用该点、它的邻居以及它们的邻居）。
如果多边形是凸的，您需要做的就是按照多边形内任意点（例如三个任意点的质心）的角度排序。

You don't need to find the convex hull. Just use the area formula from a bunch of points ordered counterclockwise:

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

The area formula comes from taking each edge AB, and calculating the (signed) area between the edge and the origin (triangle ABO) by taking the cross-product (which gives you the area of a parallelogram) and cutting it in half (factor of 1/2). As one wraps around the polygon, these positive and negative triangles will overlap, and the area between the origin and the polygon will be cancelled out and sum to 0, while only the area inside remains. This is why the formula is called the Surveyor's Formula, since the "surveyor" is at the origin; if going counterclockwise, positive area is added when going left->right and negative area is added when going right->left, from the perspective of the origin.

The mathematical formula is given below, but does not provide the intuition behind it (as given above):

edit (after question has been changed)

There is absolutely no way to "get their order" without additional assumptions, e.g. "the polygon is convex".

If the polygon is concave, it becomes nearly impossible in the general case without lots of extra assumptions (proof: consider a point which lies within the convex hull, but whose neighbors do not; there are many possible valid polygons you can construct using that point, its neighbors, and their neighbors).
If the polygon is convex, all you need to do is sort by the angle from some arbitrary point inside the polygon (e.g. centroid of three arbitrary points).

回复收藏 0 原文

痴梦一场 2024-11-17 13:56:09

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

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

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

请注意，随机的点集并不能描述单个唯一的多边形。因此，此方法只会为您提供可能的多边形之一，而不一定是您手动连接点时获得的多边形。

You could find the center of gravity (cx,cy) of the points and then calculate the angles of the points relative to (cx,cy).

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

Then sort the points by angle.

Just beware that a random set of points does not describe a single unique polygon. So this method will just give you one of the possible polygons, and not necessarily the polygon you would have obtained if you had manually connected the dots.

回复收藏 0 原文

~没有更多了~