凹多边形（非凸多边形）的对角线（对角线是连接非相邻顶点的线段）可能完全在多边形内或外（或与多边形的边相交）。如何确定它是否完全在多边形内？（一种不需要点-多边形测试的方法）。
6个回答
7
如果对角线至少与边界相交一次，它部分在多边形内部，部分在外部；然而，如果对角线与边界没有相交，只有两种状态：完全在多边形内或完全在外。
要确定它是在多边形内还是外部：
假设多边形的顶点按逆时针排序。考虑对角线的一个端点，它位于名为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之间，则对角线完全在多边形内。
我使用这种方法编写了一个程序，它运行效果很好。
要确定它是在多边形内还是外部：
假设多边形的顶点按逆时针排序。考虑对角线的一个端点，它位于名为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之间，则对角线完全在多边形内。
我使用这种方法编写了一个程序，它运行效果很好。
- Kamran Bigdely Shamloo
4
如何确定是否完全在多边形内？
如果要确定对角线是否永远不会离开多边形的边界，只需确定它是否与相邻顶点之间的任何线段相交。
- 如果相交，则部分在多边形内，部分在外。 - 如果没有相交，则要么完全在多边形内，要么完全在外。从这里开始，使用对角线上的任意一点进行点在多边形内判断是最简单的方法，但如果您不想这样做，可以使用winding algorithm。
如果要确定对角线是否永远不会离开多边形的边界，只需确定它是否与相邻顶点之间的任何线段相交。
- 如果相交，则部分在多边形内，部分在外。 - 如果没有相交，则要么完全在多边形内，要么完全在外。从这里开始，使用对角线上的任意一点进行点在多边形内判断是最简单的方法，但如果您不想这样做，可以使用winding algorithm。
- John Feminella
3
我认为John的答案忽略了一个重要情况: 当对角线从一开始就完全在多边形外部时。 想象一下，将对角线“桥接”他的“u”形多边形的两个塔。
我几年前曾经解决过这个问题，所以请原谅如果我的回忆有点模糊。
我解决这个问题的方法是对每条多边形边缘执行对角线的线相交测试。然后你有两种可能的情况: 你要么至少有一个交点，要么没有交点。如果你得到任何交点，则对角线不在多边形内。
如果你没有得到任何交点，则需要确定对角线是否完全在多边形内或完全在多边形外。假设对角线连接p[i]和p[j]，其中i完成此操作后，对角线的2D角度将为正，如果对角线在多边形外，则为负，如果在多边形内，则为负。
我几年前曾经解决过这个问题，所以请原谅如果我的回忆有点模糊。
我解决这个问题的方法是对每条多边形边缘执行对角线的线相交测试。然后你有两种可能的情况: 你要么至少有一个交点，要么没有交点。如果你得到任何交点，则对角线不在多边形内。
如果你没有得到任何交点，则需要确定对角线是否完全在多边形内或完全在多边形外。假设对角线连接p[i]和p[j]，其中i完成此操作后，对角线的2D角度将为正，如果对角线在多边形外，则为负，如果在多边形内，则为负。
- DK
4
你说得对，我完全没有注意到！我已经相应地编辑了我的回答。 - John Feminella
我对此有一点看法，我正在尝试用与你方法略有不同的方法解决它...坦白地说，我几乎不太理解你确切的意思。 - Kamran Bigdely
我不理解你的“正角度”方法。在下面的例子中，角度是正的，对角线在多边形内部：http://imgur.com/a/4zz1T - Ella Sharakanski
@EllaShar "...对角线连接p[i]和p[j]，其中i < j，并且您拥有一个顺时针缠绕的多边形。" 在这个例子中，您似乎有j < i。虽然，现在我想一想，这将是一个顶点编号环绕的问题...重要的是让对角线和参考边以相同的卷绕方向进行。话虽如此，自从我写下这篇文章已经过去17年了，甚至我自己也有点困惑这是否有效。 - DK.
2
我知道这个问题已经在很多年前得到了解答，但我有一个新的方法，它很容易实现。
如先前的答案所建议的那样，您应该首先计算多边形的所有边是否与对角线线段相交。计算相交并确定是否存在交点的代码在此处描述here。
如果所有边（不包括与对角线共享顶点的边）都没有与对角线相交，则您知道对角线要么完全位于多边形内部，要么完全位于多边形外部，这意味着对角线的中点也完全位于内部或者完全位于外部。中点是对角线两个端点的平均值。
我们现在已经将问题转化为计算对角线是否在多边形内部或外部，以及中点是否在多边形内部或外部。处理单个点比处理线更容易。
确定点是否在多边形内部的方法在此处描述here，并可以通过计算从该点开始的水平射线的交点数量来总结，看看这条射线与多少个多边形边相交。如果射线与奇数条边相交，则该点在多边形内部，否则在多边形外部。
这种实现容易实现的原因是，在您迭代所有边以检查是否与对角线相交时，您现在也可以计算对角线中点的射线是否与正在处理的当前边相交。如果您的for循环返回没有对角线和边之间的相交，则可以查看偶数/奇数计数以确定对角线是否在内部或外部。
- stantheman
1
关于检查线段之间的交点（这可能是您需要执行的第一步），我发现SoftSurfer上的解释很有帮助。您需要检查对角线和多边形任何一条边之间的交点。如果您正在使用MATLAB，您应该能够使用矩阵和向量运算同时有效地检查所有边的交点（我已经处理过射线三角形交点的计算）。
- gnovice
0
John的回答非常准确：
如果您想确定对角线是否永远不会离开多边形的边界，只需确定它是否与相邻顶点之间的任何线段相交。如果是，则已经离开了多边形。
检查这个的一种有效方法是在数据上运行Bentley-Ottman扫描线算法。它很容易实现，但很难使其数值稳定。如果您的多边形边少于...比如...20条，那么暴力搜索很可能更快。
- Nils Pipenbrinck
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接