查找点是否位于矩形内

Question

我想查找一个点是否位于矩形内。矩形可以以任何方式定向，并且不需要轴对齐。我想到的一种方法是旋转矩形和点的坐标以使矩形轴对齐，然后通过简单地测试点的坐标是否位于矩形的坐标内来进行测试。上述方法需要旋转，因此需要浮点运算。还有其他有效的方法吗？

Answer 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具有相同的大小，但相对（即平行）边缘的符号不同，可以利用该值简化测试。