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

本文介绍了生成切割面的新多边形（2D）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我只能和这个小问题，我的算法来解决，这并不适用于所有的情况。是否有人有一个想法如何解决这个问题？

I'm stuck with this little problem and my algorithm to solve this doesn't hold for all cases. Does anybody has an idea how to solve this?

下面是一个例子多边形：

正式描述

我们有个在CW为了确定多边形的列表。我们也可以查询某个点是否是一个切入点与 is_cut（P），其中 P 是一个给定的点。现在，我们要计算所致，这种腰斩。

We have a list of points in CW order defining the polygon. We also can query whether a point is a cutting point with is_cut(p), where p is a given point. Now we want to compute new polygons caused by this "cut".

的算法应该这样做：

输入： {A，C，B，C 4，C，C5，D，C6，E，C，F C2}

输出： {A，C1，C2} ， {B，C4，C3，女，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 。

This algorithm doesn't hold if you'd start at c or f.

推荐答案

首先，你应该计算一下切割线的部分属于原来的多边形的内部。这是一个经典的问题，它的解决方法很简单。鉴于您的积分 C1，C2，C3 ... C6 被布置沿线的正是这个顺序，那么段 C1-C2 ， C3-C4 等永远属于多边形内部（*）。

First you should calculate what segments of the cutting line belong to internals of your original polygon. That's a classical problem, and its solution is simple. Given that your points c1, c2, c3 ... c6 are laid out along the line in exactly this order, then segments c1-c2, c3-c4 etc will always belong to polygon internals (*).

现在我们可以构造简单的递归算法切割面。鉴于你的大输入数组，{A，C，B，C 4，C，C5，D，C6，E，C，F C2}，从任何多边形点开始，例如， B ;将它添加到阵列的 结果 的。向前遍历输入数组。如果遇到

Now we can construct simple recursive algorithm for cutting polygons. Given your big input array, {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}, start from any polygon point, for example, b; add it to array result. Traverse the input array forward. If you encounter

• 平常多边形节点，将其推到阵列的 结果 的
• CK 节点，其中 K 是奇数，查找 C（K + 1）并保持其位置穿过。
• CK 节点，其中 K 甚至，查找 C（K-1），跳转到它的位置，并保持尽管如此遍历前进。

• usual polygon node, push it to array result.
• ck node, where k is odd, look for c(k+1) and keep traversing from its position.
• ck node, where k is even, look for c(k-1), jump to its position and keep nevertheless traversing forward.

有关后两种情况下，在你遇到它们的 结果 的排列顺序添加这些节点。添加 CK 节点设置的 削减 的，并添加另一个节点（ C（K + 1）或 C（K-1），无论你已经有了），成为全球集的 完成 的。

For last two cases, add these nodes in the order you encountered them to result array. Add ck node to set cut, and add another node (c(k+1) or c(k-1), whichever you've got) into a global set done.

如果你必须超越的最后一个元素，电路的第一个元素的输入数组中开始。

If you'll have to go beyond the last element, circuit to the first element in the input array.

迟早你会遇到你是遍历初始节点。现在在 结果 的数组你有你剪一个多边形。记住它。重复此过程递归，从属于每个节点的位置开始的 剪切 的设置，不属于全球性的 完成 的设置。

Sooner or later you'll encounter the initial node you were traversing from. Now in the result array you have a polygon you've cut. Remember it. Repeat the procedure recursively, starting from position of each node that belongs to cut set and doesn't belong to the global done set.

这就是解决方案，因为我看到了。但它的计算geomentry，所以它可能会变成一个复杂一点似乎比。

That's the solution as I see it. But it's computational geomentry, so it may turn a bit more complex than it seems.

在本例中，从首部b ：

的 完成= {} 的，从首部b 。经过第一轮，你会得到的 的结果= [B，C4，C3，女，C2，C1] 的 切= {C4，C2} 的 完成= {C3，C1} 的;改乘 4 和 C2 节点。

的 完成= {C3; C1} 的，从 4 启动（递归从1）。该过程之后，您将获得的 的结果= [C4，C，C5，C6，E，C3，C4] 的 切= {C5，C3} 的 做+ = {C6，C4} ;改乘 C5 。

的 完成= {C3，C1，C4，C6} 的，从 C2 （递归从1）。该过程之后，您将获得的 的结果= C2，A，C1] 的 切= { C1} 的 做+ = {C2} 的;不要改乘 C1 ，因为它是在的 完成 的设置;

的 完成= {C3，C1，C4，C6，C2} 的，从 C5 （2递归）。该过程之后，您将获得的 的结果= [C5，D，C6] 的 切= { C5} 的 做+ = {6} 的;不要改乘 C5 ，因为它是在的 完成 的设置;

done={}, start from b. After first pass, you'll get result=[b,c4,c3,f,c2,c1], cut={c4,c2}, done={c3,c1}; Recurse to c4 and c2 nodes.

done={c3;c1}, start from c4 (recursion from 1). After this pass, you'll get result=[c4,c,c5,c6,e,c3,c4], cut={c5,c3}, done+={c6,c4}; Recurse to c5.

done={c3;c1;c4;c6}, start from c2 (recursion from 1). After this pass, you'll get result=[c2,a,c1], cut={c1}, done+={c2}; Don't recurse to c1, since it's in done set;

done={c3;c1;c4;c6;c2}, start from c5 (recursion from 2). After this pass, you'll get result=[c5,d,c6], cut={c5}, done+={c6}; Don't recurse to c5, since it's in done set;

瞧 - 你得到4个多边形你需要

Voila - you get 4 polygons you've needed.

（*）请注意，它需要更多的数学再$ P $行psentation。例如，如果多边形顶点之一就行了，顶点应增加一倍，即如果 C 的一点是有点接近右侧和红线，该线将有 [C1，C2，C3，C，C，C6] 点就可以了，而多边形阵列将 [一， C1，B，C，C，C，D，C6，E，C，F C2] 。

(*) Note that it requires more "mathematical" representation of the line. For example, if one of the polygon vertexes is on the line, the vertex should be doubled, i.e. if c point was a bit closer to the right side and on the red line, the line would have [c1, c2, c3, c, c, c6] points on it, and the polygon array would be [a, c1, b, c, c, c, d, c6, e, c3, f, c2].

有时（未在本示例中），它可能会导致切割空的多边形，如并[a，一，一个] 。如果您不需要它们，你可以在后期消除它们。无论如何，它与边界的情况下一个巨大的数字计算几何。我无法将它们包含在同一个答案......

Sometimes (not in this example), it may lead to cutting "empty" polygons, such as [a, a, a]. If you don't need them, you can eliminate them at late stages. Anyway, it's computational geometry with an immense number of border cases. I can't include them all in one answer...