점이 직사각형 내부에 있는지 확인

점이 직사각형 내부에 있는지 확인

---

점이 사각형 안에 있는지 확인하고 싶습니다. 직사각형은 어떤 방식 으로든 방향이 지정 될 수 있으며 축 정렬이 필요하지 않습니다.

제가 생각할 수있는 한 가지 방법은 직사각형과 점 좌표를 회전하여 직사각형 축을 정렬 한 다음 단순히 점 좌표가 직사각형 내에 있는지 여부를 테스트하는 것입니다.

위의 방법에는 회전이 필요하므로 부동 소수점 연산이 필요합니다. 이를 수행하는 다른 효율적인 방법이 있습니까?

---

직사각형은 어떻게 표현됩니까? 3 점? 4 점? 포인트, 측면 및 각도? 두 점과 측면? 다른 것? 그 사실을 모르면 질문에 답하려는 시도는 순전히 학문적 가치 만 가질 것입니다.

어쨌든 모든 볼록 다각형 (직사각형 포함)에 대해 테스트는 매우 간단합니다. 각 가장자리가 시계 반대 방향으로 향한다고 가정하고 다각형의 각 가장자리를 확인하고 점이 가장자리의 왼쪽 ( 왼쪽 에 있는지 테스트) -손 반 평면). 모든 모서리가 테스트를 통과하면 점이 안쪽에 있습니다. 적어도 하나가 실패하면 지점이 외부에 있습니다.

점이 (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테스트를 단순화하기 위해 이용 될 수있다 (즉, 병렬) 가장자리 반대에 대해 동일한 크기 만 다른 부호를 가지고 .

---

직사각형이 AB와 BC가 수직 인 세 점 A, B, C로 표시된다고 가정하면 AB 및 BC에서 쿼리 점 M의 투영 만 확인하면됩니다.

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

AB좌표 (Bx-Ax, By-Ay)가있는 벡터 AB 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의 대답을 빌 렸습니다.

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

자바 스크립트에서 다음과 같이 보입니다.

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.

다음은 시각적 테스트로 출력을 그리는 코드 펜입니다. :) http://codepen.io/mattburns/pen/jrrprN

---

# 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

---

나는 이것이 오래된 스레드라는 것을 알고 있지만 순전히 수학적 관점에서 이것을 보는 데 관심이있는 사람에게는 수학 스택 교환에 대한 훌륭한 스레드가 있습니다.

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 사이에 있습니다. 이것은 p1을 원점으로하여 직사각형의 길이와 너비를 따라 벡터 p-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"

그리고 그게 다야. 평행 사변형에서도 작동합니다.

---

사각형의 문제를 해결할 수 없다면 문제를 더 쉬운 문제로 나누십시오. 사각형을 2 개의 삼각형으로 나누고 여기에 설명 된 것처럼 점이 그 안에 있는지 확인합니다.

기본적으로 한 점에서 두 쌍의 선마다 가장자리를 순환합니다. 그런 다음 외적을 사용하여 점이 외적을 사용하는 두 선 사이에 있는지 확인합니다. 세 점 모두에 대해 확인되면 점이 삼각형 내부에 있습니다. 이 방법의 좋은 점은 각도를 확인할 때 발생하는 부동 소수점 오류를 생성하지 않는다는 것입니다.

---

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;}

I just implemented AnT's Answer using c++. I used this code to check whether the pixel's coordination(X,Y) lies inside the shape or not.

---

If a point is inside a rectangle. On a plane. For mathematician or geodesy (GPS) coordinates

• Let the rectangle be set by vertices A, B, C, D. The point is P. Coordinates are rectangular: x, y.
• Lets prolong the sides of the rectangle. So we have 4 straight lines l_AB, l_BC, l_CD, l_DA, or, for shortness, l₁, l₂, l₃, l₄.

• Make an equation for every l_i. The equation sort of:

  f_i(P)=0.

P is a point. For points, belonging to l_i, the equation is true.

• We need the functions on the left sides of the equations. They are f₁, f₂, f₃, f₄.
• Notice, that for every point from one side of l_i the function f_i is greater than 0, for points from the other side f_i is lesser than 0.
• So, if we are checking for P being in rectangle, we only need for the p to be on correct sides of all four lines. So, we have to check four functions for their signs.
• But what side of the line is the correct one, to which the rectangle belongs? It is the side, where lie the vertices of rectangle that don't belong to the line. For checking we can choose anyone of two not belonging vertices.

• So, we have to check this:

  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

The unequations are not strict, for if a point is on the border, it belongs to the rectangle, too. If you don't need points on the border, you can change inequations for strict ones. But while you work in floating point operations, the choice is irrelevant.

• For a point, that is in the rectangle, all four inequations are true. Notice, that it works also for every convex polygon, only the number of lines/equations will differ.

• The only thing left is to get an equation for a line going through two points. It is a well-known linear equation. Let's write it for a line AB and point P:

  f_AB(P)   ≡   (x_A-x_B) (y_P-y_B) - (y_A-y_B) (x_P-x_B)

The check could be simplified - let's go along the rectangle clockwise - A, B, C, D, A. Then all correct sides will be to the right of the lines. So, we needn't compare with the side where another vertice is. And we need check a set of shorter inequations:

f_AB(P) >= 0

f_BC(P) >= 0

f_CD(P) >= 0

f_DA(P) >= 0

But this is correct for the normal, mathematician (from the school mathematics) set of coordinates, where X is to the right and Y to the top. And for the geodesy coordinates, as are used in GPS, where X is to the top, and Y is to the right, we have to turn the inequations:

f_AB(P) <= 0

f_BC(P) <= 0

f_CD(P) <= 0

f_DA(P) <= 0

If you are not sure with the directions of axes, be careful with this simplified check - check for one point with the known placement, if you have chosen the correct inequations.

---

The easiest way I thought of was to just project the point onto the axis of the rectangle. Let me explain:

If you can get the vector from the center of the rectangle to the top or bottom edge and the left or right edge. And you also have a vector from the center of the rectangle to your point, you can project that point onto your width and height vectors.

P = point vector, H = height vector, W = width vector

Get Unit vector W', H' by dividing the vectors by their magnitude

proj_P, H = P-(P.H ') H'proj_P, W = P-(P.W ') W'

내가 틀렸다고 생각하지 않는 한 ... (내가 틀렸다면 정정 해주세요)하지만 높이 벡터에 대한 포인트 투영의 크기가 높이 벡터의 크기보다 작다면 (즉, 직사각형 높이의 절반) 너비 벡터에 대한 점의 투영 크기는 직사각형 내부에 점이 있습니다.

범용 좌표계가있는 경우 벡터 빼기를 사용하여 높이 / 너비 / 점 벡터를 계산해야 할 수 있습니다. 벡터 투영은 놀랍습니다! 기억.

참고 URL : https://stackoverflow.com/questions/2752725/finding-whether-a-point-lies-inside-a-rectangle-or-not