점이 사각형 안에 있는지 확인하고 싶습니다. 직사각형은 어떤 방식 으로든 방향이 지정 될 수 있으며 축 정렬이 필요하지 않습니다.
제가 생각할 수있는 한 가지 방법은 직사각형과 점 좌표를 회전하여 직사각형 축을 정렬 한 다음 단순히 점의 좌표가 직사각형의 좌표 내에 있는지 여부를 테스트하는 것입니다.
위의 방법에는 회전이 필요하므로 부동 소수점 연산이 필요합니다. 이를 수행하는 다른 효율적인 방법이 있습니까?
답변
직사각형은 어떻게 표현됩니까? 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입니다. 측면 AB의 투영이 세그먼트 AB 내부가 아니기 때문에 P는 직사각형 내부가 아닙니다.
답변
나는 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
답변
나는 이것이 오래된 스레드라는 것을 알고 있지만 순전히 수학적 관점에서 이것을 보는 데 관심이있는 사람에게는 수학 스택 교환에 대한 훌륭한 스레드가 있습니다.
/math/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"
그리고 그게 다야. 평행 사변형에서도 작동합니다.
답변
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)가 모양 안에 있는지 여부를 확인했습니다.
답변
직사각형의 문제를 해결할 수 없다면 문제를 더 쉬운 문제로 나누십시오. 사각형을 2 개의 삼각형으로 나누고 여기에 설명 된 것처럼 점이 그 안에 있는지 확인합니다.
기본적으로 한 점에서 두 쌍의 선마다 가장자리를 순환합니다. 그런 다음 외적을 사용하여 점이 외적을 사용하여 두 선 사이에 있는지 확인합니다. 세 점 모두에 대해 확인 된 경우 점은 삼각형 내부에 있습니다. 이 방법의 좋은 점은 각도를 확인할 때 발생하는 부동 소수점 오류를 생성하지 않는다는 것입니다.
