두 직사각형의 교차를 감지하는 알고리즘?
두 사각형이 교차하는지 감지하는 알고리즘을 찾고 있습니다 (하나는 임의의 각도로, 다른 하나는 수직 / 수평 선으로 만).
하나의 모서리가 다른 ALMOST에 있는지 테스트합니다. 사각형이 십자형을 형성하면 실패합니다.
수직선에 특별한 경우가 필요한 선의 기울기를 사용하지 않는 것이 좋습니다.
표준 방법은 분리 축 테스트를 수행하는 것입니다 (Google 검색을 수행하십시오).
한마디로 :
- 두 객체를 분리하는 선을 찾을 수 있으면 두 객체가 교차하지 않습니다. 예를 들어 객체의 객체 / 모든 점은 선의 다른 측면에 있습니다.
재미있는 점은 두 사각형의 모든 가장자리를 확인하는 것으로 충분하다는 것입니다. 사각형이 겹치지 않으면 가장자리 중 하나가 분리 축이됩니다.
2D에서는 경사를 사용하지 않고도이 작업을 수행 할 수 있습니다. 가장자리는 단순히 두 꼭지점의 차이로 정의됩니다. 예 :
edge = v(n) - v(n-1)
90도 회전시켜 수직을 얻을 수 있습니다. 2D에서는 다음과 같이 쉽습니다.
rotated.x = -unrotated.y
rotated.y = unrotated.x
삼각법이나 경사가 없습니다. 벡터를 단위 길이로 정규화 할 필요도 없습니다.
점이 선의 한쪽 또는 다른쪽에 있는지 테스트하려면 내적을 사용할 수 있습니다. 표지판은 당신이 어느쪽에 있는지 알려줍니다 :
// rotated: your rotated edge
// v(n-1) any point from the edge.
// testpoint: the point you want to find out which side it's on.
side = sign (rotated.x * (testpoint.x - v(n-1).x) +
rotated.y * (testpoint.y - v(n-1).y);
이제 사각형 A의 모든 점을 사각형 B의 가장자리와 반대로 테스트하십시오. 분리되는 모서리를 찾으면 물체가 교차하지 않습니다 (B의 다른 모든 점이 테스트중인 모서리의 다른쪽에있는 경우 아래 그림 참조). 분리 모서리가 없으면 사각형이 교차하거나 한 사각형이 다른 사각형에 포함됩니다.
이 테스트는 볼록 다각형 btw ..
수정 : 분리 에지를 식별하기 위해 한 직사각형의 모든 포인트를 다른 에지의 각 에지에 대해 테스트하는 것만으로는 충분하지 않습니다. 후보 에지 E (아래)는 A의 모든 점이 E의 동일한 반평면에 있으므로 분리 에지로 식별됩니다. 그러나 B의 정점 Vb1 및 Vb2 때문에 분리 에지가 아닙니다. 그 반평면에도 있습니다. 그렇지 않은 경우에만 분리 된 가장자리 였을 것입니다 http://www.iassess.com/collision.png
기본적으로 다음 그림을보십시오.
두 상자가 충돌하면 선 A와 B가 겹칩니다.
이 작업은 X 축과 Y 축 모두에서 수행해야하며 사각형이 충돌하려면 겹치게해야합니다.
gamasutra.com 에는 질문에 대한 답변 이있는 좋은 기사가 있습니다 (사진은 기사에 있음). 5 년 전에 비슷한 알고리즘을 수행했으며 나중에 여기에 게시 할 코드 스 니펫을 찾아야합니다
개정 : 분리 축 정리 개의 볼록 형상한다고 하지 오버랩 분액 축이 존재하는 경우 (도시 된 바와 같이 돌기 즉 하나 하지 중첩). 따라서 "분리 축이 존재합니다"=> "겹침 없음". 이것은 이중의 의미가 아니므로 대화를 결론 지을 수 없습니다.
m_pGladiator의 답변이 옳으며 선호합니다. 분리 축 테스트 는 사각형 겹침을 감지하는 가장 단순하고 표준적인 방법입니다. 투영 간격이 겹치지 않는 선을 분리 축 이라고합니다 . Nils Pipenbrinck의 솔루션이 너무 일반적입니다. 도트 제품 을 사용 하여 한 모양이 다른 쪽 가장자리의 한쪽에 완전히 있는지 확인합니다. 이 솔루션은 실제로 n-edge 볼록 다각형을 유도 할 수 있습니다. 그러나 두 사각형에는 최적화되지 않았습니다.
m_pGladiator의 대답의 중요한 점은 두 축 (x와 y)에서 두 개의 직사각형 투영을 확인해야한다는 것입니다. 두 개의 투영이 겹치면이 두 사각형이 겹쳤다 고 말할 수 있습니다. 따라서 m_pGladiator의 답변에 대한 위의 의견은 잘못되었습니다.
간단한 상황에서 두 개의 사각형이 회전하지 않으면 구조가있는 사각형이 나타납니다.
struct Rect {
x, // the center in x axis
y, // the center in y axis
width,
height
}
직사각형 A, B의 이름을 rectA, rectB로 지정합니다.
if Math.abs(rectA.x - rectB.x) < (Math.abs(rectA.width + rectB.width) / 2)
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(rectA.height + rectB.height) / 2))
then
// A and B collide
end if
두 사각형 중 하나가 회전되면 x 및 y 축에서 사각형의 투영을 결정하기 위해 약간의 노력이 필요할 수 있습니다. struct RotatedRect를 다음과 같이 정의하십시오.
struct RotatedRect : Rect {
double angle; // the rotating angle oriented to its center
}
차이점은 너비 '가 이제 약간 다른 방법입니다. rectA의 경우 Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle)widthA': rectB의 경우 widthB ':Math.sqrt(rectB.width*rectB.width + rectB.height*rectB.height) * Math.cos(rectB.angle)
if Math.abs(rectA.x - rectB.x) < (Math.abs(widthA' + widthB') / 2)
&& (Math.abs(rectA.y - rectB.y) < (Math.abs(heightA' + heightB') / 2))
then
// A and B collide
end if
GDC (Game Development Conference 2007) PPT www.realtimecollisiondetection.net/pubs/GDC07_Ericson_Physics_Tutorial_SAT.ppt를 참조 할 수 있음
Cocoa에서는 selectedArea rect가 회전 된 NSView의 frame rect와 교차하는지 여부를 쉽게 감지 할 수 있습니다. 다각형, 법선 등을 계산할 필요조차 없습니다. NSView 서브 클래스에 이러한 메소드를 추가하십시오. 예를 들어, 사용자는 NSView 슈퍼 뷰에서 영역을 선택한 다음 selectedArea rect를 전달하는 DoesThisRectSelectMe 메소드를 호출합니다. API convertRect :가 해당 작업을 수행합니다. NSView를 클릭하여 선택하면 동일한 트릭이 작동합니다. 이 경우 단순히 아래와 같이 hitTest 메소드를 대체하십시오. API convertPoint : 해당 작업을 수행합니다. ;-)
- (BOOL)DoesThisRectSelectMe:(NSRect)selectedArea
{
NSRect localArea = [self convertRect:selectedArea fromView:self.superview];
return NSIntersectsRect(localArea, self.bounds);
}
- (NSView *)hitTest:(NSPoint)aPoint
{
NSPoint localPoint = [self convertPoint:aPoint fromView:self.superview];
return NSPointInRect(localPoint, self.bounds) ? self : nil;
}
한 사각형의 선이 다른 사각형의 선과 교차하는지 확인하십시오. 순진한 선분 교차점을 쉽게 코딩 할 수 있습니다.
더 빠른 속도가 필요한 경우 선분 교차점 (스윕 라인)을위한 고급 알고리즘이 있습니다. http://en.wikipedia.org/wiki/Line_segment_intersection을 참조하십시오
하나의 해결책은 No Fit Polygon이라는 것을 사용하는 것입니다. 이 다각형은 두 개의 다각형 (개념적으로 하나를 다른 주변으로 미끄러짐)으로 계산되며 다각형이 상대 오프셋을 기준으로 겹치는 영역을 정의합니다. 이 NFP가 있으면 두 다각형의 상대 오프셋으로 지정된 점으로 포함 테스트를 수행하면됩니다. 이 포함 테스트는 쉽고 빠르지 만 먼저 NFP를 만들어야합니다.
웹에서 No Fit Polygon을 검색하고 볼록 다각형에 대한 알고리즘을 찾을 수 있는지 확인하십시오 (오목 다각형이 있으면 훨씬 복잡해집니다). 아무것도 찾을 수 없다면 howard dot J dot에서 gmail dot com으로 이메일을 보내주십시오.
다음은 가능한 모든 사례를 처리 할 것이라고 생각합니다. 다음 테스트를 수행하십시오.
- 사각형 1의 꼭짓점은 사각형 2 안에 있고 그 반대도 마찬가지입니다. 다른 사각형 안에있는 정점을 찾을 때마다 검색과 교차하고 중지한다고 결론을 내릴 수 있습니다. 하나의 사각형이 다른 사각형 안에 완전히 들어갑니다.
- 위의 테스트가 결정적이지 않으면 1 직사각형의 각 라인과 다른 직사각형의 각 라인의 교차점을 찾으십시오. 교차점이 발견되면 해당 4 점으로 생성 된 가상의 사각형 내부 사이에 있는지 확인하십시오. 그러한 요점이 발견 될 때마다 그들이 교차하고 검색을 중단한다고 결론을 내립니다.
위의 두 테스트에서 false를 반환하면이 두 사각형이 겹치지 않습니다.
Java를 사용하는 경우 Shape 인터페이스의 모든 구현 에는 사각형을 사용 하는 교차 메소드가 있습니다.
무차별 강제 방법은 가로 사각형의 가장자리를 걷고 가장자리를 따라 각 점을 확인하여 다른 사각형에 있는지 또는 다른 사각형에 있는지 확인하는 것입니다.
수학적 답은 두 직사각형의 각 모서리를 설명하는 방정식을 형성하는 것입니다. 이제 사각형 A의 4 개의 선 중 하나가 사각형 B의 선과 교차하는지 간단히 알 수 있습니다. 이는 간단한 (빠른) 선형 방정식 솔버 여야합니다.
-아담
각이 진 사각형의 각면과 축이 정렬 된 각면의 교차점을 찾을 수 있습니다. 각 변이 위치하는 무한 선의 방정식 (예 : v1 + t (v2-v1) 및 v'1 + t '(v'2-v'1))을 찾아서 선은 두 방정식이 같을 때 t를 풀고 (해당하는 경우 테스트 할 수 있음) 해당 점이 두 꼭짓점 사이의 선분에 있는지 여부를 테스트합니다. 즉, 0 <= t <= 1 및 0 <= t '<= 1.
그러나 한 직사각형이 다른 직사각형을 완전히 덮는 경우에는 적용되지 않습니다. 직사각형의 네 점이 모두 다른 직사각형 안에 있는지 테스트하여 커버 할 수 있습니다.
이 문제 의 3D 버전에 대해 다음 과 같이하십시오.
두 개의 직사각형을 방정식 P1 및 P2에 의해 설명 된 평면으로 모델링 한 다음 P1 = P2를 작성하고 그 평면에서 평행하거나 교차하지 않는 경우 존재하지 않는 교차 방정식의 선에서 파생됩니다. 이 경우 0 = 0이됩니다. 이 경우 2D 직사각형 교차 알고리즘을 사용해야합니다.
그런 다음 두 사각형의 평면에있는 그 선이 두 사각형을 통과하는지 확인합니다. 그렇다면 2 개의 직사각형이 교차하고 그렇지 않으면 그렇지 않습니다 (그렇지 않으면 머리에 모서리가 빠졌을 수 있습니다).
선이 동일한 평면의 사각형을 통과하는지 확인하려면 선과 사각형의 측면의 두 교차점을 찾아 (선 방정식을 사용하여 모델링) 교차점이 범위.
그것은 수학적 설명입니다. 불행히도 위의 작업을 수행 할 코드가 없습니다.
Another way to do the test which is slightly faster than using the separating axis test, is to use the winding numbers algorithm (on quadrants only - not angle-summation which is horrifically slow) on each vertex of either rectangle (arbitrarily chosen). If any of the vertices have a non-zero winding number, the two rectangles overlap.
This algorithm is somewhat more long-winded than the separating axis test, but is faster because it only require a half-plane test if edges are crossing two quadrants (as opposed to up to 32 tests using the separating axis method)
The algorithm has the further advantage that it can be used to test overlap of any polygon (convex or concave). As far as I know, the algorithm only works in 2D space.
Either I am missing something else why make this so complicated?
if (x1,y1) and (X1,Y1) are corners of the rectangles, then to find intersection do:
xIntersect = false;
yIntersect = false;
if (!(Math.min(x1, x2, x3, x4) > Math.max(X1, X2, X3, X4) || Math.max(x1, x2, x3, x4) < Math.min(X1, X2, X3, X4))) xIntersect = true;
if (!(Math.min(y1, y2, y3, y4) > Math.max(Y1, Y2, Y3, Y4) || Math.max(y1, y2, y3, y4) < Math.min(Y1, Y2, Y3, Y4))) yIntersect = true;
if (xIntersect && yIntersect) {alert("Intersect");}
I implemented it like this:
bool rectCollision(const CGRect &boundsA, const Matrix3x3 &mB, const CGRect &boundsB)
{
float Axmin = boundsA.origin.x;
float Axmax = Axmin + boundsA.size.width;
float Aymin = boundsA.origin.y;
float Aymax = Aymin + boundsA.size.height;
float Bxmin = boundsB.origin.x;
float Bxmax = Bxmin + boundsB.size.width;
float Bymin = boundsB.origin.y;
float Bymax = Bymin + boundsB.size.height;
// find location of B corners in A space
float B0x = mB(0,0) * Bxmin + mB(0,1) * Bymin + mB(0,2);
float B0y = mB(1,0) * Bxmin + mB(1,1) * Bymin + mB(1,2);
float B1x = mB(0,0) * Bxmax + mB(0,1) * Bymin + mB(0,2);
float B1y = mB(1,0) * Bxmax + mB(1,1) * Bymin + mB(1,2);
float B2x = mB(0,0) * Bxmin + mB(0,1) * Bymax + mB(0,2);
float B2y = mB(1,0) * Bxmin + mB(1,1) * Bymax + mB(1,2);
float B3x = mB(0,0) * Bxmax + mB(0,1) * Bymax + mB(0,2);
float B3y = mB(1,0) * Bxmax + mB(1,1) * Bymax + mB(1,2);
if(B0x<Axmin && B1x<Axmin && B2x<Axmin && B3x<Axmin)
return false;
if(B0x>Axmax && B1x>Axmax && B2x>Axmax && B3x>Axmax)
return false;
if(B0y<Aymin && B1y<Aymin && B2y<Aymin && B3y<Aymin)
return false;
if(B0y>Aymax && B1y>Aymax && B2y>Aymax && B3y>Aymax)
return false;
float det = mB(0,0)*mB(1,1) - mB(0,1)*mB(1,0);
float dx = mB(1,2)*mB(0,1) - mB(0,2)*mB(1,1);
float dy = mB(0,2)*mB(1,0) - mB(1,2)*mB(0,0);
// find location of A corners in B space
float A0x = (mB(1,1) * Axmin - mB(0,1) * Aymin + dx)/det;
float A0y = (-mB(1,0) * Axmin + mB(0,0) * Aymin + dy)/det;
float A1x = (mB(1,1) * Axmax - mB(0,1) * Aymin + dx)/det;
float A1y = (-mB(1,0) * Axmax + mB(0,0) * Aymin + dy)/det;
float A2x = (mB(1,1) * Axmin - mB(0,1) * Aymax + dx)/det;
float A2y = (-mB(1,0) * Axmin + mB(0,0) * Aymax + dy)/det;
float A3x = (mB(1,1) * Axmax - mB(0,1) * Aymax + dx)/det;
float A3y = (-mB(1,0) * Axmax + mB(0,0) * Aymax + dy)/det;
if(A0x<Bxmin && A1x<Bxmin && A2x<Bxmin && A3x<Bxmin)
return false;
if(A0x>Bxmax && A1x>Bxmax && A2x>Bxmax && A3x>Bxmax)
return false;
if(A0y<Bymin && A1y<Bymin && A2y<Bymin && A3y<Bymin)
return false;
if(A0y>Bymax && A1y>Bymax && A2y>Bymax && A3y>Bymax)
return false;
return true;
}
The matrix mB is any affine transform matrix that converts points in the B space to points in the A space. This includes simple rotation and translation, rotation plus scaling, and full affine warps, but not perspective warps.
It may not be as optimal as possible. Speed was not a huge concern. However it seems to work ok for me.
Here is a matlab implementation of the accepted answer:
function olap_flag = ol(A,B,sub)
%A and B should be 4 x 2 matrices containing the xy coordinates of the corners in clockwise order
if nargin == 2
olap_flag = ol(A,B,1) && ol(B,A,1);
return;
end
urdl = diff(A([1:4 1],:));
s = sum(urdl .* A, 2);
sdiff = B * urdl' - repmat(s,[1 4]);
olap_flag = ~any(max(sdiff)<0);
This is the conventional method, go line by line and check whether the lines are intersecting. This is the code in MATLAB.
C1 = [0, 0]; % Centre of rectangle 1 (x,y)
C2 = [1, 1]; % Centre of rectangle 2 (x,y)
W1 = 5; W2 = 3; % Widths of rectangles 1 and 2
H1 = 2; H2 = 3; % Heights of rectangles 1 and 2
% Define the corner points of the rectangles using the above
R1 = [C1(1) + [W1; W1; -W1; -W1]/2, C1(2) + [H1; -H1; -H1; H1]/2];
R2 = [C2(1) + [W2; W2; -W2; -W2]/2, C2(2) + [H2; -H2; -H2; H2]/2];
R1 = [R1 ; R1(1,:)] ;
R2 = [R2 ; R2(1,:)] ;
plot(R1(:,1),R1(:,2),'r')
hold on
plot(R2(:,1),R2(:,2),'b')
%% lines of Rectangles
L1 = [R1(1:end-1,:) R1(2:end,:)] ;
L2 = [R2(1:end-1,:) R2(2:end,:)] ;
%% GEt intersection points
P = zeros(2,[]) ;
count = 0 ;
for i = 1:4
line1 = reshape(L1(i,:),2,2) ;
for j = 1:4
line2 = reshape(L2(j,:),2,2) ;
point = InterX(line1,line2) ;
if ~isempty(point)
count = count+1 ;
P(:,count) = point ;
end
end
end
%%
if ~isempty(P)
fprintf('Given rectangles intersect at %d points:\n',size(P,2))
plot(P(1,:),P(2,:),'*k')
end
the function InterX can be downloaded from: https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function
I have a simplier method of my own, if we have 2 rectangles:
R1 = (min_x1, max_x1, min_y1, max_y1)
R2 = (min_x2, max_x2, min_y2, max_y2)
They overlap if and only if:
Overlap = (max_x1 > min_x2) and (max_x2 > min_x1) and (max_y1 > min_y2) and (max_y2 > min_y1)
You can do it for 3D boxes too, actually it works for any number of dimensions.
Enough has been said in other answers, so I'll just add pseudocode one-liner:
!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);
참고URL : https://stackoverflow.com/questions/115426/algorithm-to-detect-intersection-of-two-rectangles
'development' 카테고리의 다른 글
| 리눅스 우분투에서 시작시 자동으로 프로그램을 실행합니다. (0) | 2020.06.21 |
|---|---|
| 자동 레이아웃으로 모든 하위보기에 맞게 수퍼 뷰 크기를 조정하는 방법은 무엇입니까? (0) | 2020.06.21 |
| MongoDB BSON 문서 크기 제한 이해 (0) | 2020.06.21 |
| 정적이 아닌 내부 클래스에 정적 메서드를 사용할 수없는 이유는 무엇입니까? (0) | 2020.06.21 |
| Google 액세스 토큰 만료 시간 (0) | 2020.06.21 |