寻找一个点是否在矩形内

我想找出一个点是否在矩形内。 矩形可以以任何方式定向，不需要轴alignment。

我能想到的一种方法是旋转矩形和点坐标以使矩形轴alignment，然后通过简单地testing点的坐标是否位于矩形的坐标之内。

上述方法需要旋转，因此需要浮点操作。 有没有其他有效的方法来做到这一点？

Answer 1

矩形是如何表示的？ 三点？ 四点？ 点，侧面和angular度？ 两点和一边？ 别的东西？ 不知道，回答你的问题的任何尝试只会有纯粹的学术价值。

在任何情况下，对于任何凸多边形（包括矩形），testing都非常简单：检查多边形的每个边，假定每个边都以逆时针方向定向，并testing该点是否位于边的左侧（在左侧半手）。 如果所有的边都通过了testing – 点在里面。 如果一个失败 – 这个问题就在外面。

为了testing点(xp, yp)位于边(x1, y1) - (x2, y2)的左侧，需要为包含边的线构build线方程。 等式如下

 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 ，则该点在线上。

但是，这个testing再次适用于任何凸多边形，这意味着它可能对矩形来说过于通用。 矩形可能允许更简单的testing…例如，在矩形（或任何其他平行四边形）中， A和B的值具有相同的幅度，但对于相对（即平行）的边缘具有不同的符号，可以利用它来简化考试。

Answer 2

假设矩形由A，B，C三点表示，AB和BC垂直，则只需检查AB和BC上查询点M的投影：

 0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC) 

AB是vectorAB，坐标为（Bx-Ax，By-Ay）， dot(U,V)为vectorU和V的点积： Ux*Vx+Uy*Vy 。

更新 。 我们举一个例子来说明：A（5,0）B（0,2）C（1,5）和D（6,3）。 从点坐标得到AB =（ – 5,2），BC =（1,3），点（AB，AB）= 29，点（BC，BC）= 10。

对于查询点M（4,2），我们有AM =（ – 1,2），BM =（4,0），点（AB，AM）= 9，点（BC，BM）= 4。 M在矩形内。

对于查询点P（6,1），我们有AP =（1,1），BP =（6，-1），点（AB，AP）= – 3，点（BC，BP）= 3。 P不在矩形内，因为它在AB侧的投影不在AB段内。

Answer 3

 # Pseudo code # Corners in ax,ay,bx,by,dx,dy # Point in x, y bax = bx - ax bay = by - ay dax = dx - ax day = dy - ay if ((x - ax) * bax + (y - ay) * bay < 0.0) return false if ((x - bx) * bax + (y - by) * bay > 0.0) return false if ((x - ax) * dax + (y - ay) * day < 0.0) return false if ((x - dx) * dax + (y - dy) * day > 0.0) return false return true 

Answer 4

我意识到这是一个古老的线索，但是对于那些有兴趣从纯粹的mathangular度来看这个问题的人来说，math交换中有一个很好的线索，在这里：

https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle

编辑：这个线程的启发，我已经把一个简单的vector方法，以快速确定你的观点在哪里。

假设你有一个矩形，点p1 =（x1，y1），p2 =（x2，y2），p3 =（x3，y3），p4 =（x4，y4），顺时针旋转。 如果一个点p =（x，y）位于矩形内部，那么点积（p – p1）。（p2 – p1）将位于0和| p2 – p1 | ^ 2和（p – p1）之间。 （p4 – p1）将介于0和| p4 – p1 | ^ 2之间。 这相当于沿着长方形的长度和宽度以p1为原点投影vectorp-p1。

如果我显示一个等效的代码，这可能会更有意义：

 p21 = (x2 - x1, y2 - y1) p41 = (x4 - x1, y4 - y1) p21magnitude_squared = p21[0]^2 + p21[1]^2 p41magnitude_squared = p41[0]^2 + p41[1]^2 for x, y in list_of_points_to_test: p = (x - x1, y - y1) if 0 <= p[0] * p21[0] + p[1] * p21[1] <= p21magnitude_squared: if 0 <= p[0] * p41[0] + p[1] * p41[1]) <= p41magnitude_squared: return "Inside" else: return "Outside" else: return "Outside" 

就是这样。 它也适用于平行四边形。

Answer 5

我从Eric Bainville的回答中借用：

 0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC) 

在JavaScript中看起来像这样：

 function pointInRectangle(m, r) { var AB = vector(rA, rB); var AM = vector(rA, m); var BC = vector(rB, rC); var BM = vector(rB, m); var dotABAM = dot(AB, AM); var dotABAB = dot(AB, AB); var dotBCBM = dot(BC, BM); var dotBCBC = dot(BC, BC); return 0 <= dotABAM && dotABAM <= dotABAB && 0 <= dotBCBM && dotBCBM <= dotBCBC; } function vector(p1, p2) { return { x: (p2.x - p1.x), y: (p2.y - p1.y) }; } function dot(u, v) { return ux * vx + uy * vy; } 

例如：

 var r = { A: {x: 50, y: 0}, B: {x: 0, y: 20}, C: {x: 10, y: 50}, D: {x: 60, y: 30} }; var m = {x: 40, y: 20}; 

然后：

 pointInRectangle(m, r); // returns true. 

这是一个codepen绘制输出作为视觉testing:) http://codepen.io/mattburns/pen/jrrprN

Answer 6

如果你不能解决问题的矩形尝试将问题分为更容易的问题。 将矩形分成2个三angular形，检查点是否在其中，就像他们在这里解释的那样

本质上，你从一个点的每两对线的边缘循环。 然后使用交叉产品来检查点是否在使用交叉产品的两条线之间。 如果对所有3点进行validation，则该点在三angular形内。 这种方法的好处是它不会产生任何浮点错误，如果你检查angular度的话会发生这种错误。

Answer 7

 bool pointInRectangle(Point A, Point B, Point C, Point D, Point m ) { Point AB = vect2d(A, B); float C1 = -1 * (AB.y*Ax + AB.x*Ay); float D1 = (AB.y*mx + AB.x*my) + C1; Point AD = vect2d(A, D); float C2 = -1 * (AD.y*Ax + AD.x*Ay); float D2 = (AD.y*mx + AD.x*my) + C2; Point BC = vect2d(B, C); float C3 = -1 * (BC.y*Bx + BC.x*By); float D3 = (BC.y*mx + BC.x*my) + C3; Point CD = vect2d(C, D); float C4 = -1 * (CD.y*Cx + CD.x*Cy); float D4 = (CD.y*mx + CD.x*my) + C4; return 0 >= D1 && 0 >= D4 && 0 <= D2 && 0 >= D3;} Point vect2d(Point p1, Point p2) { Point temp; temp.x = (p2.x - p1.x); temp.y = -1 * (p2.y - p1.y); return temp;} 

我刚刚使用c ++实现了AnT的答案。 我用这个代码来检查像素的坐标（X，Y）是否在形状内部。

Answer 8

如果一个点在矩形内。 在飞机上。 用于math家或大地测量（GPS）坐标

• 让矩形由顶点A，B，C，D设置。点是P.坐标是矩形的：x，y。
• 让我们延长矩形的边。 所以我们有4条直线l _AB ，l _BC ，l _CD ，l _DA ，或者简写为l ₁ ，l ₂ ，l ₃ ，l ₄ 。

• 为每一个_我做一个方程。 方程式的种类：

  f _i （P）= 0。

P是一个点。 对于属于1的点，方程是正确的。

• 我们需要方程左侧的函数。 它们是f ₁ ，f ₂ ，f ₃ ，f ₄ 。
• 注意，对于l的一边的每一点，函数f _i大于0，对于来自另一边的点f _i小于0。
• 所以，如果我们检查P是在矩形中，我们只需要p在四条线的正确的边上。 所以，我们必须检查它们的标志的四个function。
• 但是该线的哪一边是正确的，矩形属于哪一边呢？ 这是矩形的顶点不属于线的那一边。 为了检查，我们可以select两个不属于顶点的任何一个。

• 所以，我们必须检查这个：

  f _AB （P）f _AB （C）> = 0

  f _BC （P）f _BC （D）> = 0

  f _CD （P）f _CD （A）> = 0

  f _DA （P）f _DA （B）> = 0

不平等是不严格的，因为如果一个点在边界上，它也属于矩形。 如果你不需要边界上的点，你可以改变严格的不平等。 但是，当你在浮点运算中工作时，这个select是不相关的。

• 对于一个点，就是在矩形中，所有四个不等式都是真的。 请注意，它也适用于每个凸多边形，只有线/方程的数量会有所不同。

• 剩下的唯一的事情就是得到一条直线的方程。 这是一个众所周知的线性方程。 让我们写一个AB和点P：

  f _AB （P）≡（x _A -x _B ）（y _P -y _B ） – （y _A -y _B ）（x _P -x _B ）

检查可以简化 – 让我们沿着矩形顺时针走 – A，B，C，D，A。然后所有正确的边将在线的右侧。 所以，我们不需要和另一个顶点相比。 我们需要检查一组较短的不等式：

f _AB （P）> = 0

f _BC （P）> = 0

f _CD （P）> = 0

f _DA （P）> = 0

但是这对正常的math家来说是正确的（从学校的math）坐标集，其中X在右边，Y在顶部。 而对于大地测量坐标，正如在GPS中使用的那样，其中X在顶部，Y在右边，我们必须转换不等式：

f _AB （P）<= 0

f _BC （P）<= 0

f _CD （P）<= 0

f _DA （P）<= 0

如果您不确定轴的方向，如果您select了正确的公式，请仔细检查一个点。

Answer 9

我想到的最简单的方法就是将点投影到矩形的轴上。 让我解释：

如果可以从矩形的中心获取vector，可以获取顶部或底部边缘以及左侧或右侧边缘。 而且你还有一个从矩形中心到你的点的vector，你可以将这个点投影到你的宽度和高度vector上。

P =点vector，H =高度vector，W =宽度vector

通过将vector除以它们的幅度得到单位vectorW'，H'

proj_P，H = P – （P.H'）H'proj_P，W = P – （P.W'）W'

除非我错了，我不认为我是…（纠正我，如果我错了），但如果你的点的高度向量投影的幅度小于高度向量的幅度（这是矩形高度的一半）以及你的点在宽度vector上投影的幅度是，那么你的矩形内有一个点。

如果你有一个通用的坐标系统，你可能需要使用vector减法来计算高度/宽度/点向量。 vector投影是惊人的！ 记住这一点。