1

我在输入上有两个凹多边形，表示为两个点向量。我想对它做一些多边形操作——联合、交叉和差异。我找到了这些多边形之间的交点，并将它们插入到每个多边形的正确位置。然后我给出关于它的位置的信息（内部 - 它在另一个多边形内，外部 - 它在另一个多边形之外，交点 - 多边形的两条边相交的点）到每个顶点。现在我知道哪些点创建了这些多边形（外部和交叉点）等的联合，但我需要知道如何将它们按正确的顺序排序。在相交操作的情况下，我需要将这些排序点分成正确数量的集合，因为相交的结果可能不止一个多边形。

我正在使用 C++，但我不一定需要代码，我只需要如何对这些最终的多边形点进行排序。而且我不想为这些操作使用任何库，因为我已经有了自己的函数并想使用它们。

我看着这个问题如何相交两个多边形？还有一些其他的，但没有一个是解决点的最终排序。我还阅读了这篇文章http://www.gvu.gatech.edu/~jarek/graphics/papers/04PolygonBooleansMargalit.pdf，但我可能不明白。

任何帮助，将不胜感激。

4

1 回答 1

1

如果您遵循我的评论中的所有建议：

  • 区分交点和接触点
  • 在两个多边形中的交叉点的两个等效项之间保持链接

工会的解决方案是：

  1. 只考虑外部点、接触点和交叉点
  2. 确保两个多边形中的点按不同方向排序（其中一组为顺时针方向，另一组为逆时针方向）
  3. 从两个多边形中的任何一个中的随机点开始。
  4. 对于两个多边形中的任何一个中的每个顶点，如果您访问过它，请保留它
  5. 每次遇到一个交点时，请继续从另一个多边形中的下一个跟随点遍历相当于该交点的点。
  6. 如果您回到从这里开始的点，则关闭两个多边形连接的组件之一。如果没有遍历所有顶点，则从任何未访问的顶点重复整个顶点。
  7. 最后计算你找到的所有多边形的面积。面积最大的将是真正的工会。其余的将是工会的漏洞。

加入的解决方案将是：

  1. 只考虑内部和交叉点
  2. 确保两个多边形中的点按相同方向排序
  3. 从两个多边形中的任何一个中的随机点开始。
  4. 对于两个多边形中的任何一个中的每个顶点，如果您访问过它，请保留它
  5. 每次遇到一个交点时，请继续从另一个多边形中的下一个跟随点遍历相当于该交点的点。
  6. 如果您回到从这里开始的点，则关闭两个多边形连接的组件之一。如果没有遍历所有顶点，则从任何未访问的顶点重复整个顶点。

编辑：正如我已经提到的，我觉得我的多边形方向方法需要修改。但是，在网上搜索时，我发现了可能为您工作的算法描述：The Vatti clipping algorithm

EDIT2 另 一篇描述这种裁剪算法的文章。

于 2013-01-03T10:24:27.347 回答