我想查找一个点是否位于矩形内。矩形可以以任何方式定向,并且不需要轴对齐。
我能想到的一种方法是旋转矩形和点坐标以使矩形轴对齐,然后简单地测试点的坐标是否位于矩形坐标内。
上述方法需要旋转,因此需要浮点运算。还有其他有效的方法吗?
矩形如何显示?三分?四分?点,边和角度?一分两分?还有吗 不知不觉中,任何回答您的问题的尝试都将仅具有学术价值。
在任何情况下,对于任何 凸 多边形(包括矩形)的测试是非常简单的:检查多边形的每个边缘,假设每个边缘被定向在反时针方向,以及测试是否点位于 向左 的边缘的(在左-手半平面)。如果所有边缘均通过测试,则该点在内部。如果至少有一个失败-该点在外面。
为了测试该点是否(xp, yp)位于边缘的左侧(x1, y1) - (x2, y2),您只需要计算
(xp, yp)
(x1, y1) - (x2, y2)
D = (x2 - x1) * (yp - y1) - (xp - x1) * (y2 - y1)
如果为D > 0,则该点在左侧。如果为D < 0,则该点在右侧。如果为D = 0,则该点在线上。
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
但是,该测试同样适用于任何凸多边形,这意味着它对于矩形可能太通用了。矩形可能允许更简单的测试…例如,在矩形(或任何其他平行四边形)中,的值A和值B具有相同的大小,但相对(即平行)边缘的符号不同,可以利用该值简化测试。
A
B