如何确定线段是否在多边形内部？

Question

我们有一条由两个点从多边形定义的线段L和一个由4个或更多点定义的多边形P，我需要一个算法来确定L是否在P内部？

编辑：线段必须完全在多边形内部，如果只是部分在内，则被认为是外部。

例如看下面的图片： 还有几个例子：

- user3878881

---

线段的端点是否是多边形的顶点？ - chmike

如果线段部分在多边形内怎么办？ - chmike

你需要进一步定义问题。有一些不清楚的事情会影响算法。例如，chmike上面的第二个问题：线段可以部分在多边形内吗？（考虑线段1->4） - David Rodríguez - dribeas

在您的情况下，如果所有点都在同一侧且相反，则线段将位于多边形内：3在一侧，5、6、0和1在另一侧。 - Francis Colas

P是如何定义的？你如何得到点之间的连通性？ - Rubix Rechvin

Answer 1

步骤1：L是否与P的任何边相交？如果是，则L不在P内。如果没有，请参阅步骤2。 步骤2：L的中点M在哪里？如果M在P内，则L在P内。 提示：http://en.wikipedia.org/wiki/Point_in_polygon 编辑，更多解释：有两种情况：

• L至少与P的一条边相交。那么L至少部分位于P内。
• L不与P的任何边相交。然后L要么在外面，要么在里面。由于整个L在外面或里面，因此测试L的任何一点的位置（除了L的两个端点）就足够了。测试点是否在多边形内部或外部是一个经典问题（拥有专门的维基百科页面）。

- Fumidu

---

这是一个非常复杂的第二步骤。 - QuestionC

我删除了我的负面评论。你的算法确实正确而简单。测试一个点是否在多边形内相当简单。我们考虑以该点为原点的水平半线，并计算多边形边界穿过该线的次数。如果是奇数，那么该点就在多边形内。我删除了我的不完整回答。我编辑了你的回答以便撤销我的反对票。 - chmike

@chmike 谢谢。我还添加了更多细节。我应该加一张图片以便更容易理解，但我真的没有时间。 - Fumidu

实际上你的算法并不完全正确。存在一些情况，其中_L_与_P_的任何边都不相交，而中心_M_在_P_内部但_L_在_P_外部。当_M_位于_P_的一个或多个边缘上时，这种情况就会发生。而这又发生在如果该边和_L_共线或者如果_M_是_P_的一个顶点的情况下。 - Dolma

@Dolma 确实如此。 有一些边缘情况需要注意。 但首先，需要精细化问题：我们需要决定 P 的边界是否是 P 的一部分，但原始问题并没有指定。 无论如何：对于 L 的中点 _M_（但让我们定义 L = AB_），如果 M 在 P 的边界上，则使用 AM 和 MB 递归地重复算法：只有当 AM 和 MB 在 P 中时，_AB 才在 P 中。 - Fumidu

Answer 2

如果一条线段完全在一个多边形内部，那么这条线段的两侧至少会有一个多边形顶点。 请参考如何判断一个点在直线的左侧还是右侧来确定一个点在哪一侧。

更新： 然而，反过来不一定成立。应该按顺序遍历所有多边形顶点，从线段的一端开始。从起点到终点遍历时遇到的所有顶点都应该在同一侧，其余的则在另一侧。

如果线段与多边形的边之一重合，则上述情况不成立。在这种情况下，线段的一侧将没有任何顶点。但是，在这种情况下，线段也不完全位于多边形内部。

- sray

---

这是完全错误的。1->4怎么办？两侧都有点，线段不完全在内部。也可以有两侧都有点但线段完全在外部。 - ElderBug

更新了我的答案以处理相反的情况。 - sray

这仍然是错误的。你可以在其中有一个不符合你提到的要求的段落。 - ElderBug