dat*_*ili 2 language-agnostic algorithm computational-geometry
假设我们有带顶点的凸多边形
(v0,v1,....vn)
我的目的是确定对于给定点,p(x,y)连接此点和多边形的任何顶点的任何线段是否在多边形内或甚至对于给定的两点
p(x0,y0) `p(x1,y1)`
连接这两个点的线段是多边形内？我已经搜索了很多关于这个的网站,但我仍然感到困惑,一般来说我认为我们必须比较顶点的坐标,并通过确定哪个点的坐标小于或大于另一个点的坐标,我们可以确定任何线段的位置,但是我不确定这是多么正确,请帮助我
假设顶点为(n> 2)的点P和凸多边形.nV_1V_n
按照相对于所选顶点的角度对多边形的顶点进行排序,使它们按时钟顺序或逆时针顺序排列.然后是多边形的边缘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位于多边形内部iif所有值> = 0或所有值都<= 0.
对于更普遍的问题,TopCoder有一个很好的教程,其中多边形不必是凸的.他们所做的是从测试点发送射线并检查它与之相交的边数.
注意:此处使用的叉积定义为(u1, u2) x (v1, v2) := u1*v2 - u2*v1