我想确定一个点是否在一个矩形内，这个矩形可以以任意方式定向，不一定是轴向对齐的。
我能想到的一种方法是将矩形和点坐标旋转，使矩形轴向对齐，然后通过测试点的坐标是否在矩形内来确定。
以上方法需要旋转和浮点运算。有没有其他有效的方法来做到这一点？
确定一个点是否在矩形内部
99
- avd
4
您可以快速检查点是否落在旋转矩形的正交边界框内，如果不是，则快速失败。 （是的，这只是一半的答案（嗯，通过角点可以形成三个正交框...而且现在已经很晚了（概念几何学首先被遗忘））。） - msw
但是我必须先进行旋转，对吗？ - avd
1除非您告诉我们如何定义矩形，否则答案的实际价值不会太大。当您使用整数坐标时，在选择算法时表示形状的方法非常重要。 - AnT stands with Russia
也许这个简单的答案可以：https://programming-idioms.org/idiom/178/check-if-point-is-inside-rectangle/4108/csharp？ - NoWar
10个回答
92
矩形是如何表示的？三个点？四个点？点、边和角度？两个点和一条边？还是其他方式？不知道这个信息的话，任何试图回答你问题的尝试都只有纯学术价值。
无论如何，对于任何凸多边形（包括矩形），测试都非常简单：检查多边形的每条边，假设每条边的方向都是逆时针方向，并测试点是否位于该边的左侧（在左半平面）。如果所有边都通过了测试，则该点在内部。如果至少有一条边未通过测试，则该点在外部。
为了测试点(xp, yp)是否位于边(x1, y1)-(x2, y2)的左侧，您只需要计算:
这个答案的早期版本描述了一个看似不同的左侧测试版本（见下文）。但很容易证明它计算的是相同的值。
...为了测试点
然而，这个测试对于任何凸多边形都有效，这意味着它可能对矩形来说太通用了。例如，在矩形（或任何其他平行四边形）中，
无论如何，对于任何凸多边形（包括矩形），测试都非常简单：检查多边形的每条边，假设每条边的方向都是逆时针方向，并测试点是否位于该边的左侧（在左半平面）。如果所有边都通过了测试，则该点在内部。如果至少有一条边未通过测试，则该点在外部。
为了测试点(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的值具有相同的大小但对于相对的（即平行的）边缘具有不同的符号，可以利用这一点来简化测试。- AnT stands with Russia
6
这只对数学家的坐标系成立。在PC屏幕和GPS上，轴的方向是不同的，你不能确定你是否有正确的不等式组。或者你可以确定你没有。我的答案更好 :-). - Gangnus
AndreyT @Gangnus，简单明了地说，你只需要检查凸形状的所有点与P相关的方程符号是否相同，这样就不用担心坐标系或凸形状的定义方向了；）） - Jason Rogers
3有几个扩展可以加快速度。1. 由于矩形的两条对边是平行的，它们的A、B系数可以相同。2. 由于另外两条边垂直于这些边，它们的系数
A'和B'可以分别用A'=B和B'=-A表示。3. 没有必要在两条边上都计算A xp + B yp，因此将它们合并成一个单一的测试。那么你判断是否在矩形中的测试变成了(v_min < A xp + B yp < v_max) && (w_min < B xp - A yp < w_max)。 - Michael Anderson@MichaelAnderson
v_min是什么，等等？ - pretzlstylev_min 是矩形内所有值 A x + B y 的最小值（在角落处计算时为最小值）。v_max 是相应的最大值。w_? 值也是一样的，但是针对的是 Bx - A y。 - Michael Anderson我明白了...你的意思是说，在每个角落处，
A x + B y 和 B x - A y 的值应该是相同的吗？ - pretzlstyle58
假设矩形由三个点A、B、C表示，其中AB和BC垂直，你只需要检查查询点M在AB和BC上的投影：
0 <= dot(AB,AM) <= dot(AB,AB) &&
0 <= dot(BC,BM) <= dot(BC,BC)
AB是向量AB，其坐标为(Bx-Ax,By-Ay)，dot(U,V)是向量U和V的点积：Ux*Vx+Uy*Vy。
更新。我们来举一个例子来说明：A（5,0）B（0,2）C（1,5）和D（6,3）。 从点的坐标中，我们得到AB=(-5,2)，BC=(1,3)，dot(AB,AB)=29，dot(BC,BC)=10。
对于查询点M（4,2），我们有AM=(-1,2)，BM=(4,0)，dot(AB,AM)=9，dot(BC,BM)=4。M在矩形内。
对于查询点P（6,1），我们有AP=(1,1)，BP=(6,-1)，dot(AB,AP)=-3，dot(BC,BP)=3。P不在矩形内，因为它在边AB上的投影不在线段AB内。
- Eric Bainville
7
10,2 - 10,2 - 10,10 - 2,10 不是一个矩形。 - Eric Bainville
4请绘制这些点，并考虑验证你的第一条评论的准确性。 - Eric Bainville
4这是最好的答案！ - Tahlil
1我喜欢这个答案的简洁性，它将操作数量保持在其他好答案的水平之下，但也具有非常直观和可视化的优势。 - pretzlstyle
这是我制作的一个视频，用来可视化这个洞察力，帮助我理解这些术语。https://youtu.be/srqhPL4nWlI - undefined
显示剩余2条评论
35
我借鉴了Eric Bainville的答案：
0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC)
在 JavaScript 中看起来像这样：
function pointInRectangle(m, r) {
var AB = vector(r.A, r.B);
var AM = vector(r.A, m);
var BC = vector(r.B, r.C);
var BM = vector(r.B, 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 u.x * v.x + u.y * v.y;
}
例如：
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，可以将输出绘制为视觉测试 :) http://codepen.io/mattburns/pen/jrrprN
- matt burns
4
嗨@matt burns，我使用了您的方法并将其放入了我的测试项目中：https://jsfiddle.net/caymanbruce/06wjp2sk/6/ 但是我无法使它工作。不知道为什么它仍然在测试原始矩形内的点而没有旋转。我在我的项目中使用
mouseover事件，因此每当鼠标悬停在应该在矩形内的点上时，它将在鼠标周围显示一个黑色圆点，并且在矩形外部它不应该显示任何东西。我需要帮助让它工作，但我很困惑。 - newguymouseover 应该是 mousemove，只是打错了。 - newguy16
# 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
- Jonas Elfström
5
如果我们将该点连接到矩形的三个顶点，则这些线段与边之间的角度应为锐角。 - P Shved
3这种方法的问题在于它在理论上是可行的，但在实践中可能会遇到问题。楼主并没有说矩形是如何表示的。这个答案假设它由三个点 -
a，b和d表示。虽然在理论上三个点是表示任意矩形的一种有效方式，但在实践中，通常情况下无法用整数坐标精确地表示一个矩形。一般情况下，最终会得到一个平行四边形，该平行四边形非常接近于矩形，但仍不是一个矩形。 - AnT stands with Russia3即该形状中的角度将不会完全为90度。在进行任何基于角度的测试时，必须非常小心。同样，这取决于发帖者对于一个不精确表示的“矩形”如何定义“内部”。再次强调，也取决于矩形是如何表示的。 - AnT stands with Russia
+1 给你们两个的评论。只有 @avd 可以告诉我们这是否足够好。 - Jonas Elfström
对我来说完美无缺...经常使用三角学和几何学，不用自己想出一个公式来解决常见问题真的很好。谢谢。 - sq2
13
我知道这是一个旧的帖子，但对于任何对纯数学角度感兴趣的人来说，这里有一个在数学堆栈交换上的优秀帖子：
https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle
编辑: 受到这个帖子的启发，我编写了一个简单的矢量方法，用于快速确定您的点所在的位置。
假设你有一个矩形，其点为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之间。这相当于沿着矩形的长度和宽度取向量p - p1的投影，以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"
就是这样。它也适用于平行四边形。
- Matt Thompson
1
你能否总结一下到目前为止的讨论？否则，这可能应该是一个评论，而不是一个答案。有了更多的声望，你将能够发布评论。 - Nathan Tuggy
8
bool pointInRectangle(Point A, Point B, Point C, Point D, Point m ) {
Point AB = vect2d(A, B); float C1 = -1 * (AB.y*A.x + AB.x*A.y); float D1 = (AB.y*m.x + AB.x*m.y) + C1;
Point AD = vect2d(A, D); float C2 = -1 * (AD.y*A.x + AD.x*A.y); float D2 = (AD.y*m.x + AD.x*m.y) + C2;
Point BC = vect2d(B, C); float C3 = -1 * (BC.y*B.x + BC.x*B.y); float D3 = (BC.y*m.x + BC.x*m.y) + C3;
Point CD = vect2d(C, D); float C4 = -1 * (CD.y*C.x + CD.x*C.y); float D4 = (CD.y*m.x + CD.x*m.y) + 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）是否在形状内。
- Alghyaline
3
在这里解释一下你正在做什么会非常有帮助。 - Brad
只是想说谢谢。我把你的代码转换成了适用于Unity Shader，并将其从4个点减少到3个点。效果很好！干杯。 - Dustin Jensen
1它对我有用，这是我为Unity DOTS制作的C#实现：https://gist.github.com/rgoupil/04b59be8ddb56c992f25e1489c61b310 - Robin Goupil
6
如果你无法解决矩形问题，请尝试将问题分解成更简单的问题。将矩形分成2个三角形，并检查点是否在其中任何一个三角形内，就像他们在这里所解释的那样。
基本上，您需要从一个点开始循环遍历每两对线段的边缘。然后使用叉积来检查点是否在两条线段之间，如果叉积对所有3个点都验证成功，则该点在三角形内。这种方法的好处是它不会产生浮点错误，而这种错误会在检查角度时发生。
基本上，您需要从一个点开始循环遍历每两对线段的边缘。然后使用叉积来检查点是否在两条线段之间，如果叉积对所有3个点都验证成功，则该点在三角形内。这种方法的好处是它不会产生浮点错误，而这种错误会在检查角度时发生。
- Cristian T
1
1这是正确的，但非常低效的算法。 - Gangnus
5
如何判断一个点是否在平面矩形内，适用于数学家和测量（GPS）坐标
- 设矩形的顶点为A，B，C，D，点为P，坐标为x，y。
- 延长矩形的边，得到4条直线lAB，lBC，lCD，lDA。简称l1，l2，l3，l4。
为每个li列出一个方程：
fi(P)=0.
P是一个点。对于属于li的点，该方程成立。
- 我们需要左侧方程的函数，它们是f1、f2、f3、f4。
- 注意，对于li一侧的每个点，函数fi都大于0，而对于另一侧的点，fi小于0。
- 因此，如果我们要检查P是否在矩形内，只需要检查所有四条直线上的函数的符号是否正确。因此，我们需要检查四个函数的符号。
- 但是，矩形所属的线的哪一侧是正确的呢？它是不属于该线的矩形顶点所在的一侧。为了检查，我们可以选择任意一个不属于该线的顶点。
因此，我们需要检查以下内容：
fAB(P) fAB(C) >= 0
fBC(P) fBC(D) >= 0
fCD(P) fCD(A) >= 0
fDA(P) fDA(B) >= 0
这些不等式并不严格，因为如果一个点在边界上，它也属于矩形内。如果您不需要边界上的点，则可以将不等式改为严格的。但是在使用浮点操作时，这个选择无关紧要。
- 对于一个在矩形内的点，四个不等式都成立。需要注意的是，这同样适用于任何凸多边形，只是不等式的数量会有所不同。
现在我们需要得到通过两个点的直线方程，这是一个众所周知的线性方程。让我们以AB线和点P为例来写出它：
fAB(P) ≡ (xA-xB) (yP-yB) - (yA-yB) (xP-xB)
检查可以简化 - 沿着矩形顺时针走 - A，B，C，D，A。然后所有正确的边将在直线右侧。因此，我们不需要与另一个顶点所在的边进行比较。我们需要检查一组较短的不等式：
fAB(P) >= 0
fBC(P) >= 0
fCD(P) >= 0
fDA(P) >= 0
但是，对于正常的数学家（来自学校数学）坐标系，其中X在右侧，Y在顶部，这是正确的。对于GPS中使用的测地学坐标系，其中X在顶部，Y在右侧，我们需要调整不等式：
fAB(P) <= 0
fBC(P) <= 0
fCD(P) <= 0
fDA(P) <= 0
如果您不确定轴的方向，请小心使用此简化检查 - 使用已知位置的一个点检查您选择的正确不等式。
- Gangnus
2
"其中X指向上方，Y指向右方，我们需要转换不等式：这取决于您如何确定“顺时针”。如果您认为坐标是数学坐标，则顺时针将自动变为逆时针，并且仍然可以使用第一组不等式。换句话说，如果您在所有方面都将坐标视为数学坐标，则可以避免这种混乱。反转或交换坐标对此谓词没有影响。" - Palo
@Palo 数学本身没有方向性。是的。但算法有几个关键点，如果能在任何一个点上得到可理解和合理（在现实生活中）的结果，那将会更好，以便进行测试。如果没有这些，你几乎无法检查自己是否正确地解决了不等式，也无法利用空间想象力。 - Gangnus
0
我想到的最简单的方法是将点投影到矩形的轴上。让我解释一下：
如果你可以得到从矩形中心到顶部或底部边缘和左侧或右侧边缘的向量，以及从矩形中心到你的点的向量，那么你可以将该点投影到宽度和高度向量上。
P = 点向量，H = 高度向量，W = 宽度向量
通过将向量除以其大小来获取单位向量W'，H' proj_P，H = P - (P.H')H' proj_P，W = P - (P.W')W'
除非我弄错了，但我不认为我错了...（如果我错了，请纠正我），但如果你的点在高度向量上的投影的大小小于高度向量的大小（即矩形高度的一半），并且在宽度向量上的投影的大小大于等于宽度向量的大小，则你有一个点在矩形内。
如果你有一个通用坐标系，你可能需要使用向量减法来确定高度/宽度/点向量。向量投影很棒！记住这一点。
如果你可以得到从矩形中心到顶部或底部边缘和左侧或右侧边缘的向量，以及从矩形中心到你的点的向量，那么你可以将该点投影到宽度和高度向量上。
P = 点向量，H = 高度向量，W = 宽度向量
通过将向量除以其大小来获取单位向量W'，H' proj_P，H = P - (P.H')H' proj_P，W = P - (P.W')W'
除非我弄错了，但我不认为我错了...（如果我错了，请纠正我），但如果你的点在高度向量上的投影的大小小于高度向量的大小（即矩形高度的一半），并且在宽度向量上的投影的大小大于等于宽度向量的大小，则你有一个点在矩形内。
如果你有一个通用坐标系，你可能需要使用向量减法来确定高度/宽度/点向量。向量投影很棒！记住这一点。
- Matthew
0
在继续回答 Matt 的问题之前，我们需要使用以下方案https://math.stackexchange.com/questions/190111/how-to-check-if-a-point-is-inside-a-rectangle/190373#190373 以使其正常工作。
以下代码不起作用：
0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(BC,BM) <= dot(BC,BC)
以下代码可行：
0 <= dot(AB,AM) <= dot(AB,AB) && 0 <= dot(AM,AC) <= dot(AC,AC)
您可以通过将以下内容粘贴到 JavaScript 控制台中进行检查 //JavaScript 解决方案
var screenWidth = 320;
var screenHeight = 568;
var appHeaderWidth = 320;
var AppHeaderHeight = 65;
var regionWidth = 200;
var regionHeight = 200;
this.topLeftBoundary = {
A: {x: 0, y: AppHeaderHeight},
B: {x: regionWidth, y: AppHeaderHeight},
C: {x: 0, y: regionHeight + AppHeaderHeight},
D: {x: regionWidth, y: regionHeight + AppHeaderHeight}
}
this.topRightBoundary = {
A: {x: screenWidth, y: AppHeaderHeight},
B: {x: screenWidth - regionWidth, y: AppHeaderHeight},
C: {x: screenWidth, y: regionHeight + AppHeaderHeight},
D: {x: screenWidth - regionWidth, y: regionHeight + AppHeaderHeight}
}
this.bottomRightBoundary = {
A: {x: screenWidth, y: screenHeight},
B: {x: screenWidth - regionWidth, y: screenHeight},
C: {x: screenWidth, y: screenHeight - regionHeight},
D: {x: screenWidth - regionWidth, y: screenHeight - regionHeight}
}
this.bottomLeftBoundary = {
A: {x: 0, y: screenHeight},
B: {x: regionWidth, y: screenHeight},
C: {x: 0, y: screenHeight - regionHeight},
D: {x: regionWidth, y: screenHeight - regionHeight}
}
console.log(this.topLeftBoundary);
console.log(this.topRightBoundary);
console.log(this.bottomRightBoundary);
console.log(this.bottomLeftBoundary);
checkIfTapFallsInBoundary = function (region, point) {
console.log("region " + JSON.stringify(region));
console.log("point" + JSON.stringify(point));
var r = region;
var m = point;
function vector(p1, p2) {
return {
x: (p2.x - p1.x),
y: (p2.y - p1.y)
};
}
function dot(u, v) {
console.log("DOT " + (u.x * v.x + u.y * v.y));
return u.x * v.x + u.y * v.y;
}
function pointInRectangle(m, r) {
var AB = vector(r.A, r.B);
var AM = vector(r.A, m);
var AC = vector(r.A, r.C);
var BC = vector(r.B, r.C);
var BM = vector(r.B, m);
console.log("AB " + JSON.stringify(AB));
console.log("AM " + JSON.stringify(AM));
console.log("AM " + JSON.stringify(AC));
console.log("BC " + JSON.stringify(BC));
console.log("BM " + JSON.stringify(BM));
var dotABAM = dot(AB, AM);
var dotABAB = dot(AB, AB);
var dotBCBM = dot(BC, BM);
var dotBCBC = dot(BC, BC);
var dotAMAC = dot(AM, AC);
var dotACAC = dot(AC, AC);
console.log("ABAM " + JSON.stringify(dotABAM));
console.log("ABAB " + JSON.stringify(dotABAB));
console.log("BCBM " + JSON.stringify(dotBCBM));
console.log("BCBC " + JSON.stringify(dotBCBC));
console.log("AMAC " + JSON.stringify(dotAMAC));
console.log("ACAC" + JSON.stringify(dotACAC));
var check = ((0 <= dotABAM && dotABAM <= dotABAB) && (0 <= dotBCBM && dotBCBM <= dotBCBC));
console.log(" first check" + check);
var check = ((0 <= dotABAM && dotABAM <= dotABAB) && (0 <= dotAMAC && dotAMAC <= dotACAC));
console.log("second check" + check);
return check;
}
return pointInRectangle(m, r);
}
//var point = {x: 136, y: 342};
checkIfTapFallsInBoundary(topLeftBoundary, {x: 136, y: 342});
checkIfTapFallsInBoundary(topRightBoundary, {x: 136, y: 274});
checkIfTapFallsInBoundary(bottomRightBoundary, {x: 141, y: 475});
checkIfTapFallsInBoundary(bottomRightBoundary, {x: 131, y: 272});
checkIfTapFallsInBoundary(bottomLeftBoundary, {x: 131, y: 272});
- codeninja
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接