algorithm - 确定线段是否在多边形内

Question

假设我们有带顶点的凸多边形

(v0,v1,....vn)

我的目标是确定给定点是否有p(x,y)任何线段连接该点和多边形的任何顶点是否在多边形内，甚至对于给定的两个点

p(x0,y0)  `p(x1,y1)`

连接这两个点的线段在多边形内？我已经搜索了很多关于这个的网站，但我仍然很困惑，一般我认为我们必须比较顶点的坐标，并通过确定哪个点的坐标小于或大于另一个点的坐标，我们可以确定任何线段的位置，但是我不确定这有多正确，请帮助我

Answer 1

假设一个点P和一个n顶点V_1为V_n(n > 2) 的凸多边形。

按相对于选定顶点的角度对多边形的顶点进行排序，以便它们按顺时针或逆时针顺序排列。那么多边形的边是V_1 -> V_2, V_2 -> V_3, ..., V_(n-1) -> V_n, V_n -> V_1。

现在，对于每条边，检查叉积的值(V_(i+1) - V_i) x (P - V_i)。如果所有值都 >= 0 或所有值 <= 0，则现在P位于多边形内。

TopCoder 上有一个很好的教程，用于解决多边形不必是凸面的更普遍的问题。他们所做的是从测试点发送一条射线并检查它与多少条边相交。

注意：此处使用的叉积定义为(u1, u2) x (v1, v2) := u1*v2 - u2*v1

Answer 2

如果您的多边形是凸的，并且您在当前多边形之外添加一个新点，即您要检查它是在多边形外部还是内部的点，则生成的多边形将是凸的。实际上，这意味着上述格雷厄姆扫描永远不会失败，并且添加的点位于多边形之外。

然而，更快更好的方法是将点投影到多边形边缘的法线轴上。这依赖于分离平面定理。如果点和多边形的边缘之间有一条线，则它在外面。对于多边形的每条边，取法线。将该点投影到该边的法线轴上。对所有法线​​执行此操作，并检查该点是否在该投影轴的多边形的最大和最小投影内。如果总是这样，则该点位于多边形内。如果它失败了，你可以停下来，因为它在外面由于一个分离的平面。

这将使算法以线性时间而不是 O(n log n) 运行，因为您不必根据顶点的角度对顶点进行排序。当您有大量顶点时，这是理想的选择。