我被这个小问题困住了,我解决这个问题的算法并不适用于所有情况。有人知道如何解决这个问题吗?
这是一个示例多边形:
例如 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
。