如何确定对角线是否在凹多边形中?

如果对角线与边至少有一个交点,则它部分在多边形中,部分在多边形外,但是,如果对角线与它们没有交点,则只有两种状态:它完全在多边形中或完全在多边形外。

要确定它是在多边形中还是在多边形外:

假设多边形的顶点按逆时针方向排序。考虑对角线的一个端点,该端点位于名为P[i]的顶点上(另一个端点是P[j])。然后,制作三个向量,其第一个点为p[i]:

V2:p[i]-1]-p[i]

V3:p[j]-p[i]

当我们逆时针从V1到V2时,如何确定V3是否在V1和V2之间?首选 here .

如何确定它是否完全在多边形中?

• 如果是这样,它部分在多边形中,部分在多边形外。

• winding algorithm .

我认为约翰的回答忽略了一个重要的情况:对角线从一开始就完全在多边形之外。想象一下,把他的“u”形多边形的两座塔做成对角线“桥”。

几年前我不得不解决这个问题,所以如果我的记忆有点不完整,请原谅。

我知道这个问题在很多年前就得到了回答,但我有一个易于实施的新方法。

正如前面的答案所建议的,如果多边形的任何边与对角线相交,您应该首先计算多边形的所有边。描述了计算交点并确定交点是否存在的代码 here .

如果所有边(不包括与对角线共享顶点的边)都没有与对角线相交,那么你就知道对角线是 完全在里面 或 完全在外面 多边形的中点意味着对角线的中点也是 完全在里面 或 完全在外面

我们现在已经将问题转化为计算对角线是在多边形内部还是外部,以及中点是在多边形的内部还是外部。使用单点比使用直线更容易。

here 并且可以通过计算从该点开始的水平射线的交点数量并查看该射线与多少多边形边相交来总结。如果光线相交的次数为奇数,则该点位于多边形内部,否则位于多边形外部。

此实现之所以易于实现,是因为当您迭代所有边以检查是否与对角线相交时,现在还可以计算对角线中点的光线是否与正在处理的当前边相交。如果你的for循环返回时对角线和边之间没有交集,那么你可以看到偶数/奇数计数,以确定对角线是在内侧还是外侧。

关于检查线段之间的交点(这可能是您必须做的第一步),我找到了以下解释 SoftSurfer 为了提供帮助。您必须检查对角线和多边形的任何边之间的交点。如果你在使用MATLAB,你应该能够找到一种有效的方法,使用矩阵和向量运算同时检查所有边的交点(我已经用这种方法处理了计算交点的问题 ray-triangle intersections ).

约翰的回答很准确:

如果要确定对角线是否永远不会离开多边形的边界,只需确定它是否与两个相邻顶点之间的任何线相交。如果是这样,它就留在多边形中。

进行此检查的一种有效方法是在数据上运行Bentley Ottman-sweepline算法。它很容易实现,但很难使数值稳定。如果你有少于。..说。..在多边形中搜索20条边,暴力搜索很可能会更快。