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

Question

我遇到了这个小问题,而我解决这个问题的算法并不适用于所有情况.有人知道如何解决这个问题吗？

这是一个示例多边形:

例如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数组中,您有一个切割的多边形.记住它.递归地重复该过程,从属于cutset 的每个节点的位置开始,并且不属于全局done集.

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

对于我们的示例,从b以下开始:

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