我陷入了这个小问题，解决这个问题的算法并不适用于所有情况。有人知道如何解决这个问题吗？
这是一个多边形示例：
例子http://img148.imageshack.us/img148/8804/poly.png
形式描述
我们有按CW顺序定义多边形的点列表。我们还可以使用来查询一个点是否为切割点is_cut(p)，其中p给定点为。现在，我们要计算由此“切”引起的新多边形。
is_cut(p)
p
该算法应执行以下操作：
输入： {a, c1, b, c4, c, c5, d, c6, e, c3, f, c2}
{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}
{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。
c
f
首先，您应该计算切割线的哪些段属于原始多边形的内部。这是一个经典问题，其解决方案很简单。鉴于您的积分c1, c2, c3 ... c6在正是这个顺序沿线摆出来，然后段c1-c2，c3-c4等等永远属于多边形内部（*）。
c1, c2, c3 ... c6
c1-c2
c3-c4
现在我们可以构造用于切割多边形的简单递归算法。给定您的大输入数组{a，c1，b，c4，c，c5，d，c6，e，c3，f，c2}，它从任意多边形点开始，例如b；将其添加到array中 result 。向前遍历输入数组。如果遇到
b
result
ck
k
c(k+1)
c(k-1)
对于后两种情况，请按照遇到它们的顺序将这些节点添加到 result 数组中。将ck节点添加到集合中 cut ，然后将另一个节点（c(k+1)或c(k-1)，以您所拥有的为准）添加到全局集合中 done 。
cut
done
如果您必须超越最后一个元素，请转到输入数组中的第一个元素。
迟早您将遇到要遍历的初始节点。现在，在 result 数组中，您已经切割了一个多边形。记住它。从每个属于 cut 集合但不属于全局 done 集合的节点的位置开始，递归地重复该过程。
我认为这就是解决方案。但这是计算上的风土人情，因此它可能变得比看起来复杂得多。
对于我们的示例，从开始b：
done={}
result=[b,c4,c3,f,c2,c1]
cut={c4,c2}
done={c3,c1}
c4
c2
done={c3;c1}
result=[c4,c,c5,c6,e,c3,c4]
cut={c5,c3}
done+={c6,c4}
c5
done={c3;c1;c4;c6}
result=[c2,a,c1]
cut={c1}
done+={c2}
c1
done={c3;c1;c4;c6;c2}
result=[c5,d,c6]
cut={c5}
done+={c6}
瞧-您会得到4个需要的多边形。
（*）请注意，它需要更多的“数学”表示形式。例如，如果在线上有一个多边形顶点，则顶点应加倍，即，如果c点稍微靠近右侧且在红线上，则该线上将具有[c1, c2, c3, c, c, c6]点，而多边形数组将是[a, c1, b, c, c, c, d, c6, e, c3, f, c2]。
[c1, c2, c3, c, c, c6]
[a, c1, b, c, c, c, d, c6, e, c3, f, c2]
有时（在本示例中不是），它可能导致切割“空”多边形，例如[a, a, a]。如果不需要它们，可以在后期将其消除。无论如何，它是具有大量边界案例的计算几何。我无法将所有内容都包含在一个答案中…
[a, a, a]
