algorithm - 判断一个点是否在矩形内

Question

我想知道一个点是否在矩形内。矩形可以以任何方式定向，不需要轴对齐。

我想到的一种方法是旋转矩形和点坐标，使矩形轴对齐，然后通过简单地测试点坐标是否在矩形坐标内。

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

Answer 1

矩形是如何表示的？三分？四分？点、边和角？两点和一边？还有别的吗？在不知道这一点的情况下，任何试图回答您的问题的尝试都将只具有纯粹的学术值(value)。

无论如何，对于任何凸多边形(包括矩形)，测试都非常简单:检查多边形的每条边，假设每条边都是逆时针方向，并测试该点是否位于到边缘的左侧(在左侧半平面中)。如果所有边都通过测试 - 该点在内部。如果至少有一个失败 - 点在外面。

为了测试是否点(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相对(即平行)边具有相同大小但符号不同，可用于简化测试。