[algorithm] 두 직사각형의 교차를 감지하는 알고리즘?

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를 참조 할 수 있음

답변

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