对多边形的操作 - 如何对找到的顶点进行排序

Question

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

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

我看了一下这个问题How to intersect two polygons?还有其他一些问题，但是他们都没有解决最终的点排序问题。 我也读过这篇文章http://www.gvu.gatech.edu/~jarek/graphics/papers/04PolygonBooleansMargalit.pdf，但我可能不明白。

任何帮助，将不胜感激。

Answer 1

如果你遵循我的意见我所有的建议：

• 交集和接触点之间的区别
• 请两个多边形交点的两个当量之间的联系

联合的解决方案将为：

1. 只考虑外，触摸并交点
2. 确保在两个多边形点在不同方向（集之一是在顺时针方向，另一个逆时针）
是有序
3. 从任意两个多边形中的随机点开始。
4. 对于任何两个多边形的每个顶点保持如果你访问它
5. 你遇到一个交点每次继续从下一个遍历交点相当于后跟随其他多边形点。
6. 如果您回到从此处开始的位置，则会关闭两个多边形连接的其中一个组件。如果不是所有顶点都被遍历，则从任何未访问的顶点重复它的全部。
7. 最后计算你找到的所有多边形的面积。面积最大的将是真正的联盟。其余的将是工会的漏洞。

为解决方案加入将是：

1. 只考虑内部和交叉点
2. 确保在两个多边形的点相同方向有序
3. 从任意两个多边形中的随机点开始。
4. 对于任何两个多边形的每个顶点保持如果你访问它
5. 你遇到一个交点每次继续从下一个遍历交点相当于后跟随其他多边形点。
6. 如果您回到从此处开始的位置，则会关闭两个多边形连接的其中一个组件。如果不是所有顶点都被遍历，则从任何未访问的顶点重复它的全部。

编辑：正如我已经提到，我有上帝的感觉我与多边形方向办法需要修改。然而，通过网络搜索时，我发现算法的描述，可能为你做的工作：The Vatti clipping algorithm

EDIT2One more article描述这样的裁剪算法。