问题标签 [polygon]

我再次对多边形算法有一些疑问。

我将尝试解释我的问题：

我正在使用名为 Geometric Tools(GT) 的第三方库的一个子集来对我的多边形执行布尔运算。为此，我必须将我的内部多边形格式转换为 GT 使用的格式。

我们的内部多边形格式由一个顶点数组组成，而 GT 多边形由一个索引顶点数组组成，其中每条边由一对索引表示。

用于澄清的正方形示例：

内部格式：

外部格式：

现在，我编写了一个在大多数情况下都有效的算法，但是当两条边共享相同的起始顶点时会崩溃和烧毁。让我首先解释一下我当前的算法是如何工作的。

创建一个 std::map ，其中键是表示顶点索引的整数。该值表示边缘数组中的哪条边以键索引作为起始索引。

样机示例：

要从正确的边缘跳到正确的边缘，我现在可以在 while 循环中执行以下操作：

在这个循环中进行了一些优化，并将顶点索引添加到数组中。

每次关闭多边形时，我都会找到第一个未遍历的边并开始制作另一个多边形。我继续这样做，直到 GTPolygon 中不再有未遍历的边缘。

所以每个 GTPolygon 可以产生几个 Polygon(internal) 对象。

当有两条边共享同一个顶点作为起始顶点时，该算法的缺陷就很明显了。例子：

当遍历我的边时，我如何知道这些边中的哪一个属于我当前正在遍历的多边形？当发生这种重复情况时，我可以尝试向后遍历边缘。那么问题将是如果在反转时发现另一个重复项，则遍历可能会无限地来回进行。

我的问题是，我该如何解决这个问题？完全可以解决吗？我可以使用 BSP 树以某种方式解决这个问题吗？角落案例的数量有点令人生畏。

非常感谢任何帮助，因为 5 个月的工作取决于这项工作。

编辑：

澄清一下：我想从几何工具使用的多边形的索引表示转换为我们的内部多边形格式，这只是列表中的一系列连接顶点。

I guess that my problem is related to "convex hull", but no the same. All shapes in the drawing are rectangles with same width and height. Many are adjacent to each other. I want to combine those adjacent rectangles into polygons. Unlike "convex hull", the resuled polygons could be "hollow" inside.

Is there any open source algorithm available?

我正在编写一个程序（.net）来创建体育场风格的布局，并且需要确定每个多边形相对于水平面的旋转角度。

这样我就可以构建多边形的内容并正确旋转它以适应内部。

以下图为例来模拟面对方向的每个变体（由红线表示），我如何确定使形状在顶部有红线所需的旋转角度，如形状 5 所示。

http://i40.tinypic.com/16ifhoo.gif

我找到了确定构成红线的点的角度的逻辑，但我还需要知道旋转以使其恢复水平。

我不确定我是否需要所有多边形的中心参考点来提供帮助。

我怎样才能最好地解决这个问题？

凹（非凸）多边形的对角线（对角线是连接不相邻顶点的线段）可以完全在多边形内部或外部（或可以与多边形的边相交）。如何判断是否完全在多边形内？（一种不用多边形内点测试的方法）。

对于使用 OpenGL 绘制复杂的凹多边形，最好将其细分为三角形，还是使用模板缓冲区？我猜模板缓冲区对于单帧会更快，但如果多边形不改变，三角剖分对于多帧会更好。但是，我还没有真正尝试过，所以我不知道。

假设在一个平面上有许多凸多边形，也许是一张地图。这些多边形可以相互碰撞并共享一条边，但不能重叠。

要测试两个多边形P和Q是否重叠，首先我可以测试P中的每条边，看看它是否与Q中的任何边相交。如果找到一个交点，我声明P和Q相交。如果没有相交，那么我必须测试P完全被Q包含的情况，反之亦然。接下来，存在P == Q的情况。最后，有些情况共享一些边缘，但不是全部。（这最后两种情况可能被认为是相同的一般情况，但这可能并不重要。）

我有一个算法可以检测两条线段相交的位置。如果这两个线段是共线的，则出于我的目的，它们不被视为相交。

我是否正确列举了这些案例？对这些案例的测试有什么建议吗？

请注意，我不是要找到作为交叉点的新凸多边形，我只想知道是否存在交叉点。有许多有据可查的算法可以找到交叉点，但我不需要付出所有努力。

希望这次是一个明智的问题......

在图片中看到上半部分的纹理看起来不错，但下半部分（在旋转一点之后）纹理正在分解，你可以看到形状的内部吗？多边形消失了？

这个问题叫什么？我需要知道，所以我知道修复它时要寻找什么！

顺便说一句，我正在 Papervision 中执行此操作。如果你有机会知道解决方法（或者如果可能的话），如果你能指出我正确的方向，我会允许你对自己感觉特别好。

多谢！

我正在开发一个使用多边形（凹面或凸面）的 matlab 程序。我需要在多边形上使用 imdilate 或 imerode 等图像处理功能。为此，我应该将我的多边形转换为图像。我想知道是否有办法直接在二进制矩阵中绘制多边形（1 代表前景，0 代表背景）？

目前，我使用“getframe”，然后使用“frame2im”，然后使用“im2bw”函数来执行此操作。但它的缺点是我无法控制最终图像的大小（=矩阵）（即，将帧转换为图像时图像的大小（以像素为单位），因为 matlab 不以像素为单位显示其图（？）。因此，每次有人在绘图上“放大”或“缩小”时，生成的矩阵（=图像）都会有所不同。

我的代码：

我有一组点 S（2D：由 x 和 y 定义），我想找到 P，最小的（意思是：点数最少的）多边形包围该集合的所有点，P 是的有序子集S。

有没有已知的算法来计算这个？（我在这个领域缺乏文化令人惊讶......）

谢谢你的帮助

我正在使用 NLCD 数据处理一个巨大的区域、7 个森林和非森林状态。在一些森林区域内有一块地块（这是我正在研究的硕士论文）。我用这个大数据集难倒了我问过的每个人，但我们确信那里有一个解决方案。森林/非森林区域是带符号的离散栅格。通过对森林区域进行细分，我能够将森林区域变成多边形。我无法将非森林区域变成多边形（太大）。所以我试图让点距离（点在多边形内）到森林多边形的边缘。您对获取点到森林边缘的距离有什么建议吗？