algorithm - 从切割多边形 (2D) 生成新多边形

Question

我被这个小问题困住了，我解决这个问题的算法并不适用于所有情况。有没有人知道如何解决这个问题？

这是一个示例多边形:

example http://img148.imageshack.us/img148/8804/poly.png

正式说明

我们有一个按 CW 顺序定义多边形的点列表。我们也可以用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 .

Answer 1

首先，您应该计算切割线的哪些段属于原始多边形的内部。这是一个经典的问题，它的解决方案很简单。鉴于您的积分c1, c2, c3 ... c6完全按照此顺序沿线布置，然后分段 c1-c2 , c3-c4等将始终属于多边形内部(*)。

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

普通多边形节点 ，将其推送到数组 result .

ck节点，其中 k奇 ，找c(k+1)并从它的位置继续遍历。

ck节点，其中 k是偶数 ，找c(k-1) ，跳到它的位置并继续向前移动。

对于最后两种情况，按照您遇到的顺序将这些节点添加到 result大批。添加 ck要设置的节点 cut ，然后将另一个节点( c(k+1) 或 c(k-1) ，无论您拥有哪个)添加到全局集 done 中.

如果您必须超越最后一个元素，则循环到输入数组中的第一个元素。

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

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

对于我们的示例，从 b 开始:

done={} , 从 b 开始.第一次通过后，您将获得 result=[b,c4,c3,f,c2,c1] , cut={c4,c2} , done={c3,c1} ;递归到 c4和 c2节点。

done={c3;c1} , 从 c4 开始(从 1 递归)。在此通过后，您将获得 result=[c4,c,c5,c6,e,c3,c4] , cut={c5,c3} , done+={c6,c4} ;递归到 c5 .

done={c3;c1;c4;c6} , 从 c2 开始(从 1 递归)。在此通过后，您将获得 result=[c2,a,c1] , cut={c1} , done+={c2} ;不要递归到 c1 ，因为它在 done放;

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] .如果您不需要它们，则可以在后期阶段消除它们。无论如何，这是具有大量边界情况的计算几何。我不能将它们全部包含在一个答案中...