凹（非凸）多边形的对角线（对角线是连接不相邻顶点的线段）可以完全在多边形内部或外部（或可以与多边形的边相交）。如何判断是否完全在多边形内？（一种不用多边形内点测试的方法）。
Kamran Bigdely Shamloo
问问题
5984 次
6 回答
6
如果对角线与边至少有一个交点，则部分在多边形内，部分在多边形外，如果对角线与边不相交，则只有两种状态：完全在多边形内或完全在多边形外.
要确定它是在多边形内还是在多边形外：
假设多边形的顶点逆时针排序。考虑位于名为 P[i] 的顶点上的对角线端点之一（另一个端点是 p[j]）。然后，制作三个向量，其第一个点是 p[i] ：
V1 : p[i+1] - p[i]
V2 : p[i-1] - p[i]
V3 : p[j] - p[i]
当我们从 V1 逆时针移动到 V2 时，当且仅当 V3 在 V1 和 V2 之间时，对角线完全在多边形中。
逆时针从V1到V2怎么判断V3是否在V1和V2之间？去这里。
我已经使用这种方法编写了一个程序，它可以有效地工作。
于 2009-03-30T02:33:33.163 回答
4
如何判断是否完全在多边形中？
如果要确定对角线是否永远不会离开多边形的边界，只需确定它是否与两个相邻顶点之间的任何线相交。
如果是这样，则它部分在多边形内，部分在多边形外。
如果不是，它要么完全在多边形内，要么完全在多边形外。从那里开始，最简单的方法是在对角线上的任何点上使用多边形中的点，但如果您不想这样做，请使用缠绕算法。
于 2009-03-29T00:27:01.273 回答
3
我相信约翰的回答错过了一个重要的案例：当对角线从一开始就完全在多边形之外时。想象一下他的“u”形多边形的两座塔对角线“桥”。
几年前我不得不解决这个问题，所以如果我的回忆有点参差不齐，请原谅。
我解决这个问题的方法是对多边形中的每条边执行对角线的线相交测试。然后您有两种可能的情况：您至少有一个交叉口，或者您没有交叉口。如果有任何交点，则对角线不在多边形内。
如果没有得到任何交点，则需要确定对角线是完全在多边形内部还是完全在多边形外部。假设对角线将 p[i] 连接到 p[j]，即 i < j 并且您有一个顺时针缠绕的多边形。您可以通过查看连接 p[i] 和 p[i+1] 的边来确定对角线是否在多边形之外。计算出这条边的 2D 角度（例如，使用 x 轴作为基线。）旋转对角线，使 p[i]-p[i+1] 边是它的基线并计算它的 2D 角度。
完成此操作后，如果对角线在多边形外部，对角线的 2D 角度将为正，如果在多边形内部，则为负。
于 2009-03-29T00:37:46.867 回答
1
关于检查线段之间的交叉点（这是您可能必须做的第一步），我发现SoftSurfer上的解释很有帮助。您必须检查对角线和多边形的任何边缘之间的交点。如果您使用的是 MATLAB，您应该能够找到一种有效的方法来使用矩阵和向量运算同时检查所有边缘的交点（我已经处理了以这种方式计算射线三角形交点的交点）。
于 2009-03-30T03:09:29.113 回答
1
我知道这个问题在很多年前就得到了回答，但我有一种易于实施的新方法。
正如前面的答案所建议的，如果多边形的所有边与对角线段相交，您应该首先计算它们。此处描述了计算交集并确定是否存在交集的代码。
如果所有边（不包括与对角线共享顶点的边）不与对角线相交，那么您知道对角线完全在多边形内部或完全在多边形外部，这意味着对角线的中点也分别完全在内部或完全外部. 中点是对角线的两个端点的平均值。
我们现在已经将问题转化为计算对角线是在多边形内部还是外部，而计算中点是在多边形内部还是外部。使用单点比使用线更容易。
这里描述了确定一个点是否在多边形内的方法，可以通过计算从该点开始的水平射线的交集量并查看该射线与多少个多边形边缘相交来总结。如果光线相交奇数次，则该点位于多边形内部，否则位于多边形外部。
此实现易于实现的原因是，当您遍历所有边以检查是否与对角线相交时，您现在还可以计算对角线的中点光线是否与正在处理的当前边相交。如果您的 for 循环返回时对角线和边之间没有交集，那么您可以查看偶数/奇数计数以确定对角线是在内部还是外部。
于 2019-12-27T06:14:03.970 回答
0
约翰的回答很到位：
如果要确定对角线是否永远不会离开多边形的边界，只需确定它是否与两个相邻顶点之间的任何线相交。如果是这样，它就留下了多边形。
执行此检查的一种有效方法是对数据运行 Bentley-Ottman 扫描线算法。这很容易实现，但很难使数值稳定。如果您的多边形中的边少于...比如说... 20 条，那么蛮力搜索很可能会更快。
于 2009-03-29T00:32:07.317 回答