判断一个二维点是否在四边形内部

Question

我正在开发一个JS程序，需要确定坐标系中的点是否在四个角之内。我在寻找一个答案。我所说的可能是一个凸四边形。也就是说，四个相对随意选择的顶点位置使得所有角度小于180°。谢谢。

- Henrik

---

我尝试了这里使用的inpolygon方法链接，但它不起作用。它给我返回“无法调用未定义的'inpolygon'方法”。 if (Math.inpolygon(5,6,[1,22,13,1],[1,1,21,31])){ return "是的"; } - Henrik

为什么不能仅仅比较坐标？您能更详细地描述问题吗？点和角是什么？ - 4pie0

我有大量随机生成的四边形。然后我需要检查一些（同样是随机生成的）点是否“可用”或已被四边形占据。 - Henrik

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在每条边的同侧（左侧或右侧）的条件相同。）

这两种方法都需要处理点恰好在边缘或顶点上的情况。首先，您需要决定是否将这些点视为多边形内部的点。然后，您需要相应地调整测试。请注意，轻微的数值舍入误差可能会导致错误答案。这只是您必须面对的问题。

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

P.S.刚刚发现 这里 有一页不错的页面，列出了许多策略。其中一些非常有趣。

- Ted Hopp

---

你的第二种方法是计算点是否在由四边形边界形成的四个半平面的交集中。这个公式有点复杂 :) - Andrew Mao

@AndrewMao - 呃，我是一个程序员。对于程序员来说，我们会写出代码，而不是解释事情。 :) - Ted Hopp

@darksky - 我希望你意识到我的评论本来就是个玩笑！ - Ted Hopp

好吧，无论是开玩笑还是认真的，都没有解释。我不是有意冒犯，但是。 - darksky

@darksky - 好的，我加了一个解释。 - Ted Hopp

Answer 2

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

通过绕线法，你可以确定任何点是否在由线段构建的任何形状内部。

基本上，你需要将每个线段与该点进行叉积运算，然后将所有结果相加。这是我用来判断星座中的恒星是否在一组星座线中的方法。我知道还有其他方法...

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

在几个地方一定有相关代码。

- Tom Andersen

Answer 3

判断一个点是否在三角形内要容易得多。

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

如果该点位于构成四边形的两个三角形中的任意一个内部，则该点位于四边形内部。

- Ogen