如何区分多边形的入射边和出射边？

Question

4

Weiler-Atherton多边形裁剪算法的基本原理如下：

如何区分多边形的进入和离开边？

似乎找到入边涉及到另一个庞大的算法，从而影响算法的效率。

另一个问题是，如何找到第一个入口交点？这个答案似乎为问题提供了一些启示。但是，遗憾的是它不起作用。

- user366312

3个回答

1

假设有两个多边形P和Q。可以选择P中的任何一个顶点v，通过射线法算法（或任何其他适合问题要求的算法）确定v相对于Q的位置（即在内部还是在外部）。

只需要用这种方法确定P中一个这样的顶点v相对于Q的位置，因为可以通过迭代P的有序顶点和交点集来推断出P的其他顶点的位置。

假设v在Q外面。然后，通过迭代P的有序顶点和交点集，找到的第一个交点位于进入边上。如果v在Q里面，则找到的第一个交点位于退出边上。请记住，一条边可以同时是进入和退出，这取决于沿其的交点数量。

射线投射算法的思想很简单，但是如果|V(P)|>=|V(Q)|，则应选择P的顶点v，否则选择Q的顶点v（为了降低射线投射算法对整体性能的影响，虽然不会显著）。

- cobarzan

1

您不一定需要从第一个入站交叉口开始，这在您查看绘制在纸上的多边形并可以随意放下笔时是可以的，但正如您所指出的，在编码时需要更多的努力来查找。

您只需要确保首先计算出两个多边形的所有交点，沿着源多边形的线段检查与剪辑多边形的线段的相交情况。此时，它是否在内部或外部并不重要。

一旦您获得了所有交点和两个多边形的顺序（我认为我有两个可以相互链接的列表），请沿着源多边形逐点行走。如果您的第一个源多边形点位于剪辑多边形内，则该点是解决方案多边形的第一个点；否则，解决方案多边形的第一个点是与剪辑多边形相交的第一个点。

一旦您获得了第一个解决方案点，每个点都是下一个解决方案点。当您遇到交点时，切换到另一个多边形并继续进行，直到返回到第一个解决方案点为止。

我已经很久没有编写过这个程序了，但如果我记得正确，会导致问题的点是多边形完全位于彼此内部（在这种情况下，包含的多边形是您的解决方案），并确保您已准备好如果您有一些奇怪的多边形形状，则会出现多个解决方案多边形。

- AntK

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Angzuril · Accepted Answer

首先，提醒一下，Weiler-Atherton算法使用按特定顺序排列的顶点定义的多边形，顺时针方向。简而言之，您通过沿多边形顺时针遍历来测试进入或离开的边缘。第一个进入的边缘（因此是第一个入站交点）只是您遍历的第一条从剪辑区域外部开始的边缘（见下文）。

此外，该算法通常分为两个阶段运行。首先查找所有交点，将其添加到多边形的顶点列表中，并插入正确的位置。在此阶段，您通常会标记每个顶点是否在另一个多边形内。对于第二阶段，遍历顶点以确定剪辑多边形。

让我们尝试一些示例。取由顶点A、B、C定义的三角形和矩形w、x、y、z。三角形将是剪辑区域，矩形是主题。

因此，我们为该主题生成的点列表是w、x、R、Q、y、z。三角形列表现在是A、B、Q、C、R。

从w开始，R是第一个交点，它是内部的，因为前一个点(x)是外部的。区域的遍历将是R、Q、C，然后返回R(完成)。

这里的交点没有标签，但它们仍然是R和Q。因此，我们为主题生成的点列表是w、x、R、y、Q、z。三角形列表现在是A、B、C、Q、R。

剪切遍历是R、y、Q，而R已完成。