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 位于多边形内。

有一个很好的tutorial on TopCoder对于多边形不必是凸面的更一般的问题。他们所做的是从测试点发出一条射线，并检查它与多少条边相交。

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