确定2D点是否在四边形内

Question

我正在研究一个JS程序,我需要确定点是否在坐标系的四个角内.

有人能指出我的答案吗？

我正在看我认为被称为凸四边形的东西.也就是说,四个相当随机选择的角位置,所有角度都小于180°.

谢谢.

Answer 1

有两种相对简单的方法.第一种方法是从点到"无限"(实际上,到多边形外的任何点)绘制光线,并计算光线相交多边形的边数.当且仅当计数为奇数时,该点在多边形内.

第二种方法是按顺序绕过多边形,对于每对顶点v _i和v _{i + 1}(必要时环绕第一个顶点),计算数量(x - x _i)*(y _{i + 1)} - y _i) - (x _{i + 1} - x _i)*(y - y _i).如果这些数量都具有相同的符号,则该点位于多边形内.(这些量是向量(v _{i + 1} - v _i)和(p - v _i)的叉积的Z分量.它们都具有相同符号的条件与p在上的条件相同每个边缘的同一侧(左侧或右侧).)

两种方法都需要处理点恰好位于边缘或顶点上的情况.首先需要确定是否要将这些点计数在多边形内部.然后你需要相应地调整测试.请注意,轻微的数字舍入错误可能会给出错误的答案.这只是你必须要忍受的东西.

由于你有一个凸四边形,还有另一种方法.选择任意三个顶点并计算点和第四个顶点相对于由三个选定顶点形成的三角形的重心坐标.如果该点的重心坐标都是正的并且都小于第四个顶点的重心坐标,那么该点在四边形内部.

PS刚刚在这里找到一个很好的页面列出了很多策略.其中一些非常有趣.