判断一个点是否在矩形内 [英] Finding whether a point lies inside a rectangle or not

问题描述

我想找出一个点是否位于矩形内.矩形可以以任何方式定向，无需轴对齐.

I want to find whether a point lies inside a rectangle or not. The rectangle can be oriented in any way, and need not be axis aligned.

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

One method I could think of was to rotate the rectangle and point coordinates to make the rectangle axis aligned and then by simply testing the coordinates of point whether they lies within that of rectangle's or not.

上述方法需要旋转，因此需要进行浮点运算.有没有其他有效的方法来做到这一点?

The above method requires rotation and hence floating point operations. Is there any other efficient way to do this?

推荐答案

矩形是如何表示的?三分?四分?点、边和角?两点和一边?还有什么?在不知道这一点的情况下，任何试图回答您的问题的尝试都只会具有纯粹的学术价值.

How is the rectangle represented? Three points? Four points? Point, sides and angle? Two points and a side? Something else? Without knowing that, any attempts to answer your question will have only purely academic value.

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

In any case, for any convex polygon (including rectangle) the test is very simple: check each edge of the polygon, assuming each edge is oriented in counterclockwise direction, and test whether the point lies to the left of the edge (in the left-hand half-plane). If all edges pass the test - the point is inside. If at least one fails - the point is outside.

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

In order to test whether the point (xp, yp) lies on the left-hand side of the edge (x1, y1) - (x2, y2), you just need to calculate

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

如果 D >0，点在左边.如果 D <0，点在右手边.如果D = 0，则点在直线上.

If D > 0, the point is on the left-hand side. If D < 0, the point is on the right-hand side. If D = 0, the point is on the line.

这个答案的前一个版本描述了一个看似不同的左侧测试版本(见下文).但是很容易证明它计算的是相同的值.

The previous version of this answer described a seemingly different version of left-hand side test (see below). But it can be easily shown that it calculates the same value.

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

... In order to test whether the point (xp, yp) lies on the left-hand side of the edge (x1, y1) - (x2, y2), you need to build the line equation for the line containing the edge. The equation is as follows

A * x + B * y + C = 0

哪里

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

现在你需要做的就是计算

Now all you need to do is to calculate

D = A * xp + B * yp + C

如果 D >0，点在左边.如果 D <0，点在右手边.如果D = 0，则点在直线上.

If D > 0, the point is on the left-hand side. If D < 0, the point is on the right-hand side. If D = 0, the point is on the line.

然而，这个测试同样适用于任何凸多边形，这意味着它对于矩形来说可能过于通用.矩形可能允许更简单的测试...例如，在矩形(或任何其他平行四边形)中，A 和 B 的值具有相同的幅度但不同的符号用于相对(即平行)边，可用于简化测试.

However, this test, again, works for any convex polygon, meaning that it might be too generic for a rectangle. A rectangle might allow a simpler test... For example, in a rectangle (or in any other parallelogram) the values of A and B have the same magnitude but different signs for opposing (i.e. parallel) edges, which can be exploited to simplify the test.

这篇关于判断一个点是否在矩形内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！