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

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 )。如果这些量都具有相同的符号，则该点位于多边形内部。（这些量是向量 (vi ₊₁ - vi ₎和 (p - v _i ) 的叉积的 Z 分量。它们都具有相同符号的条件与 p 存在的条件相同每个边缘的同一侧（左侧或右侧）。）

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

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

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

Answer 2

您需要使用绕组或光线追踪方法。

使用缠绕，您可以确定任何点是否在使用线段构建的任何形状内。

基本上，您将每个线段与该点相乘，然后将所有结果相加。这就是我在给定一组星座线的情况下确定一颗恒星是否在星座中的方法。我可以看到还有其他方法..

http://en.wikipedia.org/wiki/Point_in_polygon

在一些地方必须有一些代码。

Answer 3

查看一个点是否位于三角形内要容易得多。

任何四边形都可以分成两个三角形。

如果该点在构成四边形的两个三角形中的任何一个中，则该点在四边形内。