问题标签 [polygon]

我有一堆二维线，它们的起点和终点是已知的。这些线可能偶尔会相互交叉，或者一条线可能会在另一条线的中间结束。我需要从这个线网中形成多边形。如有必要，我可以确保所有线条的左侧都在它们的多边形内。

As far as I am aware there is no inbuilt polygon functionality for Python. I want to create a 3D map and figured that polygons would be the best way to go about it.

Not wanting to reinvent the wheel I did some googling and found that there's a lot of Python stuff out there, but I couldn't find what I wanted. Thus before I reinvent the wheel (or invent it a whole), does anybody know of a Polygon system for Python?

Note that it does need to be 3D (I found quite a few 2D ones). Note also that I am not interested in the displaying of them but in storing them and the datastructure within Python.

Thanks

从手册页XFillPolygon：

• 如果shape是Complex，路径可能会自相交。请注意，路径中的连续重合点不会被视为自相交。

• 如果shape是Convex，则对于多边形内的每一对点，连接它们的线段不会与路径相交。如果客户端知道，指定Convex可以提高性能。如果为非凸路径指定凸路径，则图形结果未定义。

• 如果shape是Nonconvex，则路径不会自相交，但形状不是完全凸的。如果客户知道，指定Nonconvex而不是Complex可能会提高性能。如果为自相交路径指定Nonconvex，则图形结果未定义。

我在填充方面遇到了性能问题XFillPolygon，正如手册页所建议的，我要采取的第一步是指定多边形的正确形状。为了安全起见，我目前正在使用Complex 。

是否有一种有效的算法来确定多边形（由一系列坐标定义）是凸的、非凸的还是复杂的？

我有大量顶点，其中一些是边，一些是多余的（在形状内部），我想删除它们。

我能想到的最简单的算法是一一检查它们是否碰到了其他人形成的形状。但它应该是一个非常慢的算法。

我考虑过从边缘选择一个（每个示例离原点最远的一个）并计算从这个开始的最长路径......应该得到边缘路径，对吗？

有什么建议吗？

如何找到多边形的内角数，大于 180º，只有多边形的顶点？

对于每个顶点，我总是想要内角，而不是外角。

来自巴西的感谢。

好的，我正在尝试根据角度 0.x 的原始位置旋转 Java 多边形，并且 y 在我使用它们结束时最终被转换为 int，所以我可以理解没有看到一些变化，但是当角度差异很大，例如 0 到 180 我想我应该看到一些东西。

我已经有一段时间了，想不出它是什么。这是方法。（对不起，如果代码标签弄乱了，我的火狐把它们弄乱了。）

我正在寻找一种好的算法来在（不一定是凸的）多边形内找到一个轴对齐的矩形。最大矩形会很好，但不是必需的 - 任何可以找到“相当好的”矩形的算法都可以。

多边形也可能有孔，但任何指向仅适用于凸多边形或简单多边形的算法的指针也会有所帮助。

在我的实现中，边的相交测试相当便宜，但“多边形中的点”测试很昂贵，因此理想情况下应该尽量减少。

什么是减少多边形顶点数量而不改变多边形外观的好算法？

输入：一个多边形，表示为一个点列表，具有太多顶点：例如，来自鼠标的原始输入。

输出：一个顶点少得多的多边形，看起来仍然很像原始多边​​形：例如，可用于碰撞检测的多边形（不一定是凸的）。

编辑：对此的解决方案类似于在图表上找到最佳拟合的多段线。在我的算法书中，它被称为分段最小二乘法。

Edit2：Douglas Peucker 算法是我真正想要的。

我有一个关系数据库，其中每个条目都标记为带有纬度/经度坐标的点。我让用户能够在地图上标记任意多边形，并希望返回多边形形状内的所有条目。

实现这一目标的最佳方法是什么？

此外，可能值得指出的是，小错误是可以的（即，如果有一种有效的方法可以将多边形变成一组矩形，那很好）。

我有一个点（纬度/经度）和一个以度数为单位的航向（真北），该点正沿着该点移动。我有许多静止的多边形（点在纬度/经度中定义），它们可能是凸面的，也可能不是凸面的。

我的问题是，如何计算与多边形最近的交点（如果有）。我看过一些关于光线追踪的令人困惑的帖子，但是当光线和多边形不在同一个平面上并且多边形必须是凸面时，它们似乎都与 3D 有关。