두 직사각형의 교차점을 감지하는 알고리즘은 무엇입니까?

https://stackoverflow.com/questions/115426

02-07-2019
|

문제

두 개의 직사각형이 교차하는지(하나는 임의의 각도로, 다른 하나는 수직/수평선만 포함) 감지하는 알고리즘을 찾고 있습니다.

한 모서리가 다른 모서리에 있는지 테스트하는 것이 거의 작동합니다.직사각형이 십자형 모양을 형성하면 실패합니다.

수직선에 특별한 경우가 필요한 선의 경사를 사용하지 않는 것이 좋은 생각인 것 같습니다.

해결책

표준 방법은 다음을 수행하는 것입니다. 분리 축 테스트 (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);

이제 직사각형 B의 가장자리에 대해 직사각형 A의 모든 점을 테스트하고 그 반대도 마찬가지입니다.분리된 가장자리를 찾으면 객체가 교차하지 않습니다(B의 다른 모든 점이 테스트 중인 가장자리의 반대쪽에 있는 경우 - 아래 그림 참조).분리되는 가장자리가 없으면 직사각형이 교차하거나 하나의 직사각형이 다른 직사각형에 포함되어 있습니다.

이 테스트는 모든 볼록 다각형에서 작동합니다.

개정: 분리 모서리를 식별하려면 한 직사각형의 모든 점을 다른 직사각형의 각 모서리에 대해 테스트하는 것만으로는 충분하지 않습니다.후보 간선 E(아래)는 A의 모든 점이 E의 동일한 절반 평면에 있으므로 분리 간선으로 식별됩니다.그러나 B의 정점 Vb1과 Vb2도 해당 절반 평면에 있기 때문에 분리된 가장자리가 아닙니다.그렇지 않았다면 그것은 단지 분리된 가장자리였을 것입니다.http://www.iassess.com/collision.png

다른 팁

기본적으로 다음 그림을 보세요.

두 상자가 충돌하면 선 A와 B가 겹칩니다.

이 작업은 X축과 Y축 모두에서 수행되어야 하며 직사각형이 충돌하려면 둘 다 겹쳐야 합니다.

에 좋은 글이 있어요 gamasutra.com 질문에 대한 답변입니다(사진은 기사에서 가져온 것입니다).나는 5년 전에 비슷한 알고리즘을 수행했고 나중에 여기에 게시하려면 내 코드 조각을 찾아야 합니다.

개정:분리축 정리(Separating Axis Theorem)는 두 개의 볼록한 모양이 하지 마라 분리 축이 존재하는 경우 중첩됩니다(예:표시된 것과 같이 투영되는 곳 하지 마라 중복).따라서 "분리축이 존재합니다" => "겹침 없음"입니다.이는 양방향 함축이 아니므로 대화를 결론지을 수 없습니다.

m_pGladiator의 답변이 옳고 저는 그것을 선호합니다.분리축 테스트 직사각형 겹침을 감지하는 가장 간단하고 표준적인 방법입니다.투영 간격이 겹치지 않는 선을 우리는 분리축.Nils Pipenbrinck의 솔루션은 너무 일반적입니다.그것은 사용 내적 한 모양이 다른 모양의 가장자리 한쪽에 완전히 있는지 확인합니다.이 솔루션은 실제로 n-모서리 볼록 다각형을 유도할 수 있습니다.그러나 두 개의 직사각형에는 최적화되어 있지 않습니다.

m_pGladiator 답변의 중요한 점은 두 축(x 및 y)에서 두 직사각형의 투영을 확인해야 한다는 것입니다.두 개의 투영이 겹친다면 이 두 직사각형이 겹친다고 말할 수 있습니다.따라서 m_pGladiator의 답변에 대한 위의 설명은 잘못되었습니다.

단순한 상황의 경우 두 개의 사각형이 회전하지 않으면 구조가있는 사각형을 나타냅니다.

struct Rect {
    x, // the center in x axis
    y, // the center in y axis
    width,
    height
}

우리는 직사각형 A, B를 ectA, ectB로 명명합니다.

    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 축에 대한 투영을 결정하려면 약간의 노력이 필요할 수 있습니다.RotatedRect 구조체를 다음과 같이 정의합니다.

struct RotatedRect : Rect {
    double angle; // the rotating angle oriented to its center
}

차이점은 너비'가 이제 약간 다르다는 것입니다.retA의 경우 widthA': Math.sqrt(rectA.width*rectA.width + rectA.height*rectA.height) * Math.cos(rectA.angle)직사각형 B의 경우 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 직사각형이 회전된 NSView의 프레임 직사각형과 교차하는지 여부를 쉽게 감지할 수 있습니다.다각형이나 법선을 계산할 필요조차 없습니다.NSView 하위 클래스에 이러한 메소드를 추가하기만 하면 됩니다.예를 들어, 사용자가 NSView의 슈퍼뷰에서 영역을 선택한 다음 selectedArea 렉트를 전달하는 DoesThisRectSelectMe 메소드를 호출합니다.API ConvertRect:그 일을 할 것입니다.NSView를 클릭하여 선택할 때도 동일한 트릭이 작동합니다.이 경우 아래와 같이 hitTest 메서드를 재정의하면 됩니다.API 변환점:그 일을 할 거예요 ;-)

- (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 may gmail dot com으로 이메일을 보내주세요.

가능한 모든 경우를 처리할 것이라고 생각하는 것은 다음과 같습니다.다음 테스트를 수행하십시오.

직사각형 1의 정점이 직사각형 2 내부에 있는지 확인하고 그 반대의 경우도 마찬가지입니다.다른 직사각형 내부에 있는 꼭지점을 찾을 때마다 해당 꼭지점이 교차한다고 결론을 내리고 검색을 중지할 수 있습니다.이것은 완전히 다른 직사각형 안에 있는 하나의 직사각형을 처리합니다.
위의 테스트가 결론에 이르지 못한 경우 한 직사각형의 각 선과 다른 직사각형의 각 선의 교차점을 찾으십시오.교차점이 발견되면 해당 4개의 점으로 생성된 가상 직사각형 내부 사이에 있는지 확인합니다.그러한 지점이 발견되면 그들이 교차한다고 결론을 내리고 검색을 중단합니다.

위의 2개 테스트가 false를 반환하면 이 2개의 직사각형은 겹치지 않습니다.

Java를 사용하는 경우 Shape 인터페이스의 모든 구현에는 교차한다 직사각형을 취하는 메소드.

음, 무차별 대입 방법은 수평 직사각형의 가장자리를 걷고 가장자리를 따라 각 점을 확인하여 그것이 다른 직사각형 위에 있는지 또는 안에 있는지 확인하는 것입니다.

수학적 답은 두 직사각형의 각 모서리를 설명하는 방정식을 형성하는 것입니다.이제 직사각형 A의 네 선 중 하나가 직사각형 B의 선과 교차하는지 간단히 찾을 수 있습니다. 이는 간단한(빠른) 선형 방정식 해결기입니다.

-아담

각진 직사각형의 각 측면과 축 정렬된 직사각형의 각 측면의 교차점을 찾을 수 있습니다.각 변이 놓인 무한선의 방정식을 찾아 이를 수행합니다(즉,기본적으로 v1 + t(v2-v1) 및 v'1 + t'(v'2-v'1)), 두 방정식이 동일할 때(만일 평행하게 테스트할 수 있음) 그런 다음 해당 점이 두 꼭지점 사이의 선분에 있는지 테스트합니다. 즉,0 <= t <= 1이고 0 <= t' <= 1이라는 것이 사실인가요?

그러나 하나의 직사각형이 다른 직사각형을 완전히 덮는 경우는 포함되지 않습니다.두 직사각형의 네 점이 모두 다른 직사각형 안에 있는지 테스트하여 다룰 수 있습니다.

이것이 내가 할 일이다. 3D 이 문제의 버전:

2개의 직사각형을 방정식 P1과 P2로 설명된 평면으로 모델링한 다음 P1=P2라고 쓰고 그로부터 평면이 평행하거나(교차가 없음) 동일한 평면에 있는 경우 존재하지 않는 교차 선 방정식을 파생합니다. 이 경우 0=0이 됩니다.이 경우 2D 직사각형 교차 알고리즘을 사용해야 합니다.

그런 다음 두 직사각형의 평면에 있는 선이 두 직사각형을 통과하는지 확인합니다.만약 그렇다면, 2개의 직사각형의 교차점이 있는 것입니다. 그렇지 않으면 그렇지 않습니다(또는 그러지 말아야 합니다. 내 머릿속에서 코너 케이스를 놓쳤을 수도 있습니다).

선이 동일한 평면의 직사각형을 통과하는지 확인하려면 선과 직사각형 측면의 교차점 2개를 찾은 다음(선 방정식을 사용하여 모델링) 교차점이 다음과 같은지 확인합니다. 범위.

그것은 수학적 설명입니다. 불행히도 위의 작업을 수행할 코드가 없습니다.

분리 축 테스트를 사용하는 것보다 약간 더 빠른 테스트를 수행하는 또 다른 방법은 굴곡 숫자 알고리즘을 사용하는 것입니다(사분면에서만 - ~ 아니다 끔찍할 정도로 느린 각도 합산)(임의로 선택됨) 두 직사각형의 각 꼭지점에서.정점 중 하나에 0이 아닌 굴곡 수가 있는 경우 두 직사각형이 겹칩니다.

이 알고리즘은 분리 축 테스트보다 다소 시간이 오래 걸리지만 가장자리가 두 사분면을 교차하는 경우 반 평면 테스트만 필요하기 때문에 더 빠릅니다(분리 축 방법을 사용하는 최대 32개의 테스트와 반대).

이 알고리즘은 중복을 테스트하는 데 사용할 수 있다는 추가 장점이 있습니다. 어느 다각형(볼록 또는 오목).내가 아는 한, 알고리즘은 2D 공간에서만 작동합니다.

다른 것이 빠졌는데 왜 이렇게 복잡하게 만드는 걸까요?

(x1,y1)과 (X1,Y1)이 직사각형의 모서리인 경우 교차점을 찾으려면 다음을 수행하십시오.

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

저는 다음과 같이 구현했습니다.

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

mB 행렬은 B 공간의 점을 A 공간의 점으로 변환하는 아핀 변환 행렬입니다.여기에는 단순 회전 및 변환, 회전 및 크기 조정, 전체 아핀 워프가 포함되지만 원근 워프는 포함되지 않습니다.

가능한 한 최적이 아닐 수도 있습니다.속도는 크게 문제가 되지 않았습니다.그러나 그것은 나에게 괜찮은 것 같습니다.

다음은 허용되는 답변의 MATLAB 구현입니다.

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

이는 일반적인 방법으로, 한 줄씩 이동하여 선이 교차하는지 확인합니다.이것은 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

InterX 기능은 다음에서 다운로드할 수 있습니다. https://in.mathworks.com/matlabcentral/fileexchange/22441-curve-intersections?focused=5165138&tab=function

2개의 직사각형이 있는 경우 나만의 더 간단한 방법이 있습니다.

R1 = (min_x1, max_x1, min_y1, max_y1)

R2 = (min_x2, max_x2, min_y2, max_y2)

다음과 같은 경우에만 중복됩니다.

중첩 = (max_x1 > min_x2) 및 (max_x2 > min_x1) 및 (max_y1 > min_y2) 및 (max_y2 > min_y1)

3D 상자에도 이 작업을 수행할 수 있으며 실제로는 모든 차원에서 작동합니다.

다른 답변에서는 충분히 언급되었으므로 의사코드를 한 줄로 추가하겠습니다.

!(a.left > b.right || b.left > a.right || a.top > b.bottom || b.top > a.bottom);

라이센스 : CC-BY-SA ~와 함께 속성

제휴하지 않습니다 StackOverflow