从切割后的多边形（2D）生成新的多边形

Question

我被这个小问题卡住了，我的解决算法对于所有情况都不适用。有人有什么想法如何解决吗？

这里是一个多边形的示例：

示例 http://img148.imageshack.us/img148/8804/poly.png

形式化描述：

我们有一个由顺时针方向定义的点列表来定义此多边形。我们还可以查询一个点是否是切点，使用 is_cut(p) ，其中p 是给定的点。现在，我们要计算由这个“切割”引起的新多边形。

该算法应该执行以下操作：

输入：{a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}

输出：{a, c1, c2}，{b, c4, c3, f, c2, c1}，{d, c6, c5}，{e, c3, c4, c, c5, c6}

这是我的当前算法：

follow your points, CW
if the point is a cut point
-> go back trough the list looking for cut points
--- if next cut point is connected to the current cut point 
    and not part of the current poly, follow it
--- else keep searching
else
-> continue until you hit your starting point.
that's a poly
do this for every non-cut-point

如果你从c或者f开始，这个算法就不适用了。

- sulf

---

当我看到你的图片时，我终于理解了输出。然而，我认为，在给定这个输入的情况下，计算机不可能神奇地猜出所有C坐标都属于一起。因此，我认为除了多边形的坐标之外，您还需要一个单独的输入数组来指定哪些索引是要切割的索引。更合理的做法是：一个多边形和一个定义切割线的向量。 - Toad

没错，我之前计算了c_n个点，因此我可以提供一个函数is_cut(p)，它将形成这样的列表{c1,...,cn}，其中n mod 2 == 0。对于图片我很抱歉，但是stackoverflow目前还不允许我发布图片:(。 - sulf

我还添加了一个伪代码算法，这是我用来了解的。 - sulf

嗯...那张图片让我想起了我每天在地铁里看到的东西。(图片) http://alloyfirms.ru/bank/5295_moscow.gif - P Shved

@pavel：这是我的地铁地图 http://www.ecampmany.com/NY/Subwaymap.gif - sulf

Answer 1

首先，您应该计算切割线段属于原多边形内部的部分。这是一个经典问题，其解决方案很简单。假设您的点沿着该线依次排列，则段，等将始终属于多边形内部(*)。

现在，我们可以构建简单的递归算法来切割多边形。给定您的大输入数组{a，c1，b，c4，c，c5，d，c6，e，c3，f，c2}，从任何多边形点（例如）开始；将其添加到数组结果中。向前遍历输入数组。如果你遇到：

·常规多边形节点，请将其推入结果数组。

·ck节点，其中k为奇数，请查找c(k+1)并从其位置继续遍历。

·ck节点，其中k为偶数，请查找c(k-1)，跳转到其位置，并继续向前遍历。

对于后两种情况，请按照遇到它们的顺序将这些节点添加到result数组中。将ck节点添加到集合cut中，并将另一个节点（c(k+1)或c(k-1)，无论您得到哪个）添加到全局集合done中。

如果您必须超出最后一个元素，则电路转到输入数组中的第一个元素。

迟早你会遇到你从中遍历的初始节点。现在，在result数组中，您已经切割了一个多边形。记住它。从属于cut集并且不属于全局done集的每个节点的位置开始，递归地重复该过程。

这是我所看到的解决方案。但这是计算几何，所以可能比看起来更加复杂。

对于我们的示例，请从开始：

1. done={}，从b开始。第一次遍历后，您将得到result=[b,c4,c3,f,c2,c1]，cut={c4,c2}，done={c3,c1}；递归到c4和c2节点。
2. done={c3;c1}，从c4开始（从1递归）。此次遍历后，您将得到result=[c4,c,c5,c6,e,c3,c4]，cut={c5,c3}，done+={c6,c4}；递归到c5。
3. done={c3;c1;c4;c6}，从c2开始（从1递归）。此次遍历后，您将得到result=[c2,a,c1]，cut={c1}，done+={c2}；不要递归到c1，因为它在done集合中；
4. done={c3;c1;c4;c6;c2}，从c5开始（从2递归）。此次遍历后，您将得到result=[c5,d,c6]，cut={c5}，done+={c6}；不要递归到c5，因为它在done集合中；

瞧，你得到了你需要的4个多边形。

---

(*) 注意，它需要更多“数学”表示线。例如，如果多边形的一个顶点在直线上，则该顶点应该加倍，即如果c点离右侧更近并且在红线上，则该线将具有[c1，c2，c3，c，c，c6]点，并且多边形数组将是[a，c1，b，c，c，c，d，c6，e，c3，f，c2]。

有时（不在此示例中），它可能会导致切割“空”多边形，例如[a，a，a]。如果您不需要它们，可以在后期消除它们。无论如何，这是具有大量边界情况的计算几何。我无法在一个答案中包含它们所有...

- P Shved

---

“...段c1-c2、c3-c4等将始终属于多边形内部...”并不总是成立。例如，移除切割点c4和c5，让c成为切割点。” - Bart Kiers

@Bart K.，这里没有错误。已添加解释。 - P Shved

抱歉，我并不是想暗示你错了。只是你让它听起来很容易，而实际上（正如你自己提到的）有很多棘手的角落情况需要考虑。 - Bart Kiers

惊人的答案！很棒，你解释完之后还演示了一遍。 - Adam Harte

Answer 2

你可以应用Weiler Atherton裁剪（实际上是Pavel建议的），但有一个巨大的注意事项。

由于浮点误差，W / A剪辑算法非常难以正常工作-在剪辑线穿过顶点或精确沿多边形边缘的情况下，算法可能会混淆它应该遵循多边形周长的哪个“路径”，然后输出不正确的结果。

- Jason Williams

---

我建议的方法可以很容易地扩展到处理这些情况，但我的算法不需要了解浮点数运算，它只需遍历给定的数组（这些数组也不需要太高的精度）。 - P Shved

哪个是正确的：“这是具有大量边界情况的计算几何”还是“[它]可以轻松扩展以处理这些情况”？任何尝试实现这些方法的人都可以告诉您，上面的算法只需要几分钟就可以实现，但要使其在广义和有用的意义下真正起作用，则需要更长时间。如果在遍历节点层次结构时做出错误决策（很容易做到，因为众所周知“计算机无法进行数学运算”），则会生成不正确的输出。 - Jason Williams

Answer 3

1 找到每个点的侧面

选择一个不在切割线上的点（例如a），并将其设置为左侧（实际上无所谓）。

当您经过切割线上的点时，您到达的点的侧面会发生变化。因此，您需要找到左/右侧的点。

问题是您还应该考虑点的顺序应按预定义的方式进行排序。（例如顺时针）

2 从cx的每个中心开始，顺时针和逆时针各走一次。

对于每个多边形，您只能在一个方向上一次到达中心。

如果您“溢出”c，则表示您到达了外部多边形。如果您定义了位于多边形上的c0和cmax，则可以解决此问题。

input =  {a, c1, c0 ,c1, b, c4, c, c5, d, c6, c7, c6, e, c3, f, c2}

- Luka Rahne

Answer 4

最简单的实现方法是Sutherland-Hodgman。它的一个问题是它会留下一些连接到线的多边形的零面积小片段。在你的例子中，这会给你类似于：

{a c2 c3 e c6 c5 c c4 c1} 和 {b c1 c2 f c3 c6 d c5 c4}

如果你可以接受这个或者想出如何将它们分成你想要的部分，那么你会发现实际剪切的代码非常简单。

实现只需要两个堆栈和对多边形顶点的单次遍历。在每个顶点处，检查是否自上一个顶点以来已经越过了线。如果是这样，计算交点并将其推入其中一个堆栈。然后将新的顶点推入其中一个堆栈。非常容易。

- MPG