javascript - 确定二维点是否在四边形内

Question

我正在开发一个 JS 程序，我需要确定点是否在坐标系的四个 Angular 内。

有人可以指出答案的方向吗？

我正在看我认为称为凸四边形的东西。也就是说，四个非常随机选择的 Angular 位置，所有 Angular 都小于 180°。

谢谢。

Answer 1

有两种相对简单的方法。第一种方法是从该点到“无穷大”(实际上，到多边形之外的任何点)绘制一条射线，并计算该射线与多边形的多少条边相交。当且仅当计数为奇数时，该点位于多边形内。

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

这两种方法都需要处理点正好在边上或顶点上的情况。您首先需要决定是否要将这些点计为在多边形内。然后你需要相应地调整测试。请注意，无论哪种方式，轻微的数字舍入误差都可能给出错误的答案。这只是您必须忍受的事情。

由于您有一个凸四边形，因此还有另一种方法。选择任意三个顶点并计算 barycentric coordinates点和第四个顶点相对于由三个选定顶点形成的三 Angular 形。如果该点的质心坐标均为正且均小于第四个顶点的质心坐标，则该点在四边形内。

附言刚找到一个不错的页面 here列出了相当多的策略。其中一些非常有趣。