找到一个点是否位于矩形内

Question

我想找出一个点是否位于矩形内部.矩形可以以任何方式定向,并且不需要轴对齐.

我能想到的一种方法是旋转矩形和点坐标以使矩形轴对齐,然后通过简单地测试点的坐标是否位于矩形的坐标内.

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

Answer 1

矩形是如何表示的？三点？四点？点,侧面和角度？两点一面？别的什么？在不知情的情况下,任何回答你问题的尝试都只具有纯粹的学术价值.

在任何情况下,对于任何凸多边形(包括矩形)的测试是非常简单的:检查多边形的每个边缘,假设每个边缘在反时针方向被取向,并测试点是否位于向左的边缘的(在左 - 半平面).如果所有边都通过测试 - 该点在内部.如果至少有一个失败 - 这一点在外面.

为了测试点是否(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具有相同幅度但不同符号的值,可以利用它来简化测试.

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是矢量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),点(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

我借用了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

Answer 4

# 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 5

我意识到这是一个老线程,但对于那些有兴趣从纯数学角度看待这个问题的人来说,在数学堆栈交换中有一个很好的线程,在这里:

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"

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

Answer 6

如果你无法解决矩形的问题,请尝试将问题分解为更容易的问题.将矩形划分为2个三角形,检查点是否在任何一个内部,就像在这里解释一样

基本上,您从一个点开始循环每两对线的边缘.然后使用叉积使用叉积检查点是否在两条线之间.如果已经验证了所有3个点,则该点在三角形内.这种方法的好处是它不会产生任何浮点错误,如果你检查角度会发生这种错误.

Answer 7

如果一个点在矩形内。在飞机上。对于数学家或大地测量 (GPS) 坐标

\n\n

\n
• 设矩形由顶点 A、B、C、D 组成。点为 P。坐标为矩形：x、y。
\n
• 让我们延长矩形的边。因此，我们有 4 条直线 l _AB、 l _BC、 l _CD、 l _DA，或者简单地说， l ₁、 l ₂、 l ₃、 l ₄。
\n

• _{为每个 l i}建立一个方程。等式如下：

  \n\n

  f _i (P)=0。

\n

\n\n

P是一个点。对于属于 l _i的点，该方程成立。

\n\n

\n
• 我们需要方程左边的函数。它们是f ₁、f ₂、f ₃、f ₄。
\n
• _{请注意，对于 l i}一侧的每个点，函数 f _i都大于 0，而对于另一侧的点 f _i则小于 0。
\n
• 因此，如果我们检查 P 是否在矩形中，我们只需要 p 位于所有四条线的正确边上。因此，我们必须检查四个函数的符号。
\n
• 但是，矩形所属的线的哪一侧才是正确的呢？它是边，即不属于该线的矩形顶点所在的位置。为了进行检查，我们可以选择两个不属于的顶点中的任何一个。
\n

• 所以，我们必须检查一下：

  \n\n

  f _AB (P) f _AB (C) >= 0

  \n\n

  f _BC (P) f _BC (D) >= 0

  \n\n

  f _CD (P) f _CD (A) >= 0

  \n\n

  f _DA (P) f _DA (B) >= 0

\n

\n\n

不等式并不严格，因为如果一个点在边界上，它也属于矩形。如果您不需要边界上的点，您可以将不等式更改为严格的点。但是当您进行浮点运算时，选择是无关紧要的。

\n\n

\n
• 对于矩形中的点，所有四个不等式都成立。请注意，它也适用于每个凸多边形，只是行/方程的数量会有所不同。
\n

• 剩下的唯一一件事就是得到穿过两点的直线的方程。这是一个众所周知的线性方程。我们将其写为线 AB 和点 P：

  \n\n

  f _AB (P) \xe2\x89\xa1 \n(x _A -x _B ) (y _P -y _B ) - (y _A -y _B ) (x _P -x _B )

\n

\n\n

检查可以简化 - 让我们顺时针沿着矩形- A、B、C、D、A。然后所有正确的边都将位于线的右侧。因此，我们不需要与另一个顶点所在的边进行比较。我们需要检查一组较短的不等式：

\n\n

f _AB (P) >= 0

\n\n

fBC ₍ P) >= 0

\n\n

f _CD (P) >= 0

\n\n

f _DA (P) >= 0

\n\n

但这对于正常的数学家（来自学校数学）坐标集来说是正确的，其中 X 位于右侧，Y 位于顶部。对于GPS 中使用的大地测量坐标，其中 X 位于顶部，Y 位于右侧，我们必须转动不等式：

\n\n

f _AB (P) <= 0

\n\n

fBC ₍ P) <= 0

\n\n

f _CD (P) <= 0

\n\n

fDA ₍ P) <= 0

\n\n

如果您不确定轴的方向，请小心进行此简化检查 - 如果您选择了正确的不等式，请检查具有已知位置的一点。

\n

Answer 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)是否位于形状内部.