小编典典

查找点是否位于矩形内

algorithm

我想查找一个点是否位于矩形内。矩形可以以任何方式定向,并且不需要轴对齐。

我能想到的一种方法是旋转矩形和点坐标以使矩形轴对齐,然后简单地测试点的坐标是否位于矩形坐标内。

上述方法需要旋转,因此需要浮点运算。还有其他有效的方法吗?


阅读 256

收藏
2020-07-28

共1个答案

小编典典

矩形如何显示?三分?四分?点,边和角度?一分两分?还有吗 不知不觉中,任何回答您的问题的尝试都将仅具有学术价值。

在任何情况下,对于任何 多边形(包括矩形)的测试是非常简单的:检查多边形的每个边缘,假设每个边缘被定向在反时针方向,以及测试是否点位于 向左
的边缘的(在左-手半平面)。如果所有边缘均通过测试,则该点在内部。如果至少有一个失败-该点在外面。

为了测试该点是否(xp, yp)位于边缘的左侧(x1, y1) - (x2, y2),您只需要计算

D = (x2 - x1) * (yp - y1) - (xp - x1) * (y2 - y1)

如果为D > 0,则该点在左侧。如果为D < 0,则该点在右侧。如果为D = 0,则该点在线上。


此答案的先前版本描述了左侧测试的看似不同的版本(请参见下文)。但是可以很容易地证明它计算出相同的值。

…为了测试点是否(xp, yp)位于边缘的左侧(x1, y1) - (x2, y2),您需要为包含边缘的线构建线方程。公式如下

A * x + B * y + C = 0

哪里

A = -(y2 - y1)
B = x2 - x1
C = -(A * x1 + B * y1)

现在您要做的就是计算

D = A * xp + B * yp + C

如果为D > 0,则该点在左侧。如果为D < 0,则该点在右侧。如果为D = 0,则该点在线上。

但是,该测试同样适用于任何凸多边形,这意味着它对于矩形可能太通用了。矩形可能允许更简单的测试…例如,在矩形(或任何其他平行四边形)中,的值A和值B具有相同的大小,但相对(即平行)边缘的符号不同,可以利用该值简化测试。

2020-07-28