11

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

这是一个示例多边形:

例如 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

4

4 回答 4

5

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

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

  • 通常的多边形节点,将其推送到数组result
  • ckk奇数的节点,寻找c(k+1)并继续从它的位置遍历。
  • ck节点,在哪里k是偶数,寻找c(k-1),跳到它的位置并继续向前遍历。

对于最后两种情况,按照遇到的顺序将这些节点添加到result数组中。将ck节点添加到 set cut,并将另一个节点(c(k+1)c(k-1),无论您拥有)添加到全局 set done

如果您必须超出最后一个元素,请转到输入数组中的第一个元素。

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

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


对于我们的示例,从b

  1. done={},从 开始b。第一次通过后,您将获得result=[b,c4,c3,f,c2,c1], cut={c4,c2}, done={c3,c1}; 递归到c4c2节点。
  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]. 如果您不需要它们,您可以在后期消除它们。无论如何,它是具有大量边界情况的计算几何。我不能将它们全部包含在一个答案中...

于 2009-11-21T14:02:56.437 回答
3

您可以应用Weiler Atherton剪裁(实际上是 Pavel 所建议的),但有一个很大的警告。

由于浮点错误,W/A 剪裁算法很难正常工作——在剪裁线穿过一个顶点或恰好沿着多边形的边缘等情况下,算法可能会混淆哪个“路径” " 围绕它应该遵循的多边形的边界,然后输出不正确的结果。

于 2009-11-21T14:24:22.460 回答
0

1 找到边每个点是

选择一个未切割的 pont(例如 a)并将其设置在左侧(它不会实际发生)

当您越过切入点时,到达点的一侧会发生变化。所以你找到左/右点。

问题是您还应该考虑点的顺序应该是预先定义的。(例如顺时针)

2 从 cx 的每个中间部分开始,顺时针和逆时针走一次。

对于每个多边形,您只在一个方向上击中中间部分一次。

如果您“溢出” c,则意味着您达到了外部多项式。如果您定义位于 polgon 上的 c0 和 cmax 并且您拥有比

input =  {a, c1, c0 ,c1, b, c4, c, c5, d, c6, c7, c6, e, c3, f, c2}
于 2009-11-21T14:55:01.950 回答
0

最简单的实现是Sutherland-Hodgman。它的一个问题是它在连接线一侧的多晶硅上留下了很少的零面积条。在你的例子中,这会给你类似的东西:

{a c2 c3 e c6 c5 c c4 c1} 和 {b c1 c2 f c3 c6 d c5 c4}

如果您可以忍受这一点或弄清楚如何将它们分解成您想要的部分,那么您会发现进行实际剪辑的代码将尽可能简单。

该实现只需要两个堆栈和一次通过多边形的顶点。在每个顶点上,您检查是否从上一个顶点开始越线。如果是这样,计算交叉点并将其推送到其中一个堆栈上。然后将新顶点推送到其中一个堆栈上。真的很容易。

于 2009-12-02T17:13:51.567 回答