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

于 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 回答