找到一个点是否位于内部矩形或不 [英] Finding whether a point lies inside a rectangle or not

问题描述

的矩形可以以任何方式被定向...需要不被轴一致。现在，我想找到一个点是否位于矩形内部还是不行。

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

一种方法我能想到的是旋转矩形和点坐标，使矩形轴线对齐，然后通过简单的测试点的坐标是否位于内的矩形的或没有。

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??

推荐答案

如何矩形重新presented？三点？四点？点，侧面和角θ两点和侧？别的东西？如果不知道的是，任何企图回答你的问题将只有纯粹的学术价值。

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 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 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)

现在你需要做的是计算

D = A * xp + B * yp + C

如果 D＆GT; 0 ，系统的点是在左侧。如果D＆LT; 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屋！