假设我们有带有顶点的凸多边形
(v0,v1,....vn)
我的目的是确定对于给定点，p(x,y)连接该点和多边形的任何顶点的线段是否在多边形内，甚至对于给定的两个点
p(x,y)
p(x0,y0) `p(x1,y1)`
连接这两个点的线段在多边形内部？我已经搜索了很多关于此的站点，但是我仍然感到困惑，通常我认为我们必须比较顶点的坐标，并通过确定哪个点小于或大于另一个点的坐标来确定任何线段的位置，但是我不确定这有多正确，请帮助我
假设一个点P和一个凸多边形的n顶点V_1为V_n（n> 2）。
P
n
V_1
V_n
按多边形相对于选定顶点的角度对多边形的顶点进行排序，以使它们处于顺时针或逆时针顺序。然后，多边形的边缘为V_1 -> V_2, V_2 -> V_3, ..., V_(n-1) -> V_n, V_n -> V_1。
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)。现在P在多边形内部，如果所有值均> = 0或所有值均<= 0。
(V_(i+1) - V_i) x (P - V_i)
关于TopCoder，有一个很好的教程可以解决更常见的问题，即多边形不必是凸的。他们要做的是从测试点发出光线，并检查相交的边缘数量。
注意： 此处使用的叉积定义为(u1, u2) x (v1, v2) := u1*v2 - u2*v1
(u1, u2) x (v1, v2) := u1*v2 - u2*v1
