선분이 직사각형과 교차하는지 확인하는 방법은 무엇입니까?

Question

사각형의 대각선 모서리를 나타내는 (x1, y1) 및 (x2, y2) 2 점과 2 개의 종점을 나타내는 (x3, y3) 및 (x4, y4) 선분이 직사각형과 교차하는지 어떻게 확인할 수 있습니까?

(라인 세그먼트가 주어진 엔드 포인트 사이에 포함 바로 세그먼트입니다. 그것은 두 점으로 정의 무한 길이의 선이 아니다.)

Answer 1

라인 여부를 확인하기 위해 a standard algorithm for checking whether two line segments intersect를 사용하는 한 아주 간단한 옵션이 될 것이다 세그먼트는 상자의 모서리를 구성하는 4 개의 선분과 교차합니다. 두 선분이 교차하는지 확인하는 것이 계산 상 매우 효율적이므로이 작업이 매우 빠르게 수행 될 것으로 기대합니다.

희망이 도움이됩니다.

Answer 2

모든 4 개의 꼭지점 (직사각형 모서리)의 내적을 선분의 방향 벡터와 함께 가져옵니다. 4 개 모두에 같은 부호 값이있는 경우 모든 정점은 선의 동일한면 (선분이 아니라 무한 선)에 있으므로 선이 직사각형을 교차하지 않습니다. 이 접근법은 2D 교차 탐지에서만 실행 가능합니다. 이것은 대다수를 신속하게 필터링하는 데 사용될 수 있습니다 (곱셈과 덧셈 만 사용). 선 대신 선분을 추가로 확인해야합니다.

Answer 3

선분이 직사각형과 교차하는지 테스트하는 수식을 유도하는 방법을 이해하려면 vector dot product의 속성을 기억하는 것이 중요합니다.

선분을 단위 벡터 및 선분 시작점과 원점 사이의 거리로 나타냅니다. 또한 수직 벡터를 계산해야합니다

Vector vecLine = new Vector(a_ptEnd.X - a_ptStart.X, a_ptEnd.Y - a_ptStart.Y); 
double dLengthLine = vecLine.Length; 
vecLine /= dLengthLine; 
double dDistLine = Vector.Multiply(vecLine, new Vector(a_ptStart.X, a_ptStart.Y)); 

하고, 선분에 대한 원점에서의 거리 : 여기 Vector 사용하여 PointF 변수 a_ptStart 및 a_ptEnd에서 해당을 계산하는 몇 가지 C# 코드입니다. 단위 벡터를 9°으로 회전하는 것은 easy입니다.

: 사각형의 네 구석을 가정

Vector vecPerpLine = new Vector(-vecLine.Y, vecLine.X); 
double dDistPerpLine = Vector.Multiply(vecPerpLine, new Vector(a_ptStart.X, a_ptStart.Y)); 

가 VectorvecRect1라는 변수 vecRect2, vecRect3 및 vecRect4에, 선분 대상의 경계 - 사각형의 네 모서리의 distance을 계산할

double dPerpLineDist1 = Vector.Multiply(vecPerpLine, vecRect1) - dDistPerpLine; 
double dPerpLineDist2 = Vector.Multiply(vecPerpLine, vecRect2) - dDistPerpLine; 
double dPerpLineDist3 = Vector.Multiply(vecPerpLine, vecRect3) - dDistPerpLine; 
double dPerpLineDist4 = Vector.Multiply(vecPerpLine, vecRect4) - dDistPerpLine; 
double dMinPerpLineDist = Math.Min(dPerpLineDist1, Math.Min(dPerpLineDist2, 
    Math.Min(dPerpLineDist3, dPerpLineDist4))); 
double dMaxPerpLineDist = Math.Max(dPerpLineDist1, Math.Max(dPerpLineDist2, 
    Math.Max(dPerpLineDist3, dPerpLineDist4))); 

모든 거리가 양수이거나 모든 거리가 음수이면 직사각형이 선의 한쪽면 또는 다른면에 있으므로 교차점이 없습니다. (제로 정도 직사각형 어떤 선분과 교차하지 않도록 고려된다.)

if (dMinPerpLineDist <= 0.0 && dMaxPerpLineDist <= 0.0 
     || dMinPerpLineDist >= 0.0 && dMaxPerpLineDist >= 0.0) 
    /* no intersection */; 

다음 프로젝트 선분 상 대상의 경계 사각형의 네 모서리. 이렇게하면 선의 원점과 해당 선의 사각형 모서리 투영 사이의 거리가 표시됩니다.

double dDistLine1 = Vector.Multiply(vecLine, vecRect1) - dDistLine; 
double dDistLine2 = Vector.Multiply(vecLine, vecRect2) - dDistLine; 
double dDistLine3 = Vector.Multiply(vecLine, vecRect3) - dDistLine; 
double dDistLine4 = Vector.Multiply(vecLine, vecRect4) - dDistLine; 
double dMinLineDist = Math.Min(dDistLine1, Math.Min(dDistLine2, 
    Math.Min(dDistLine3, dDistLine4))); 
double dMaxLineDist = Math.Max(dDistLine1, Math.Max(dDistLine2, 
    Math.Max(dDistLine3, dDistLine4))); 

사각형의 점이 선분의 범위 내에 있지 않으면 교차가 없습니다.

if (dMaxLineDist <= 0.0 || dMinLineDist >= dLengthLine) 
    /* no intersection */; 

나는 그것이 충분하다고 생각한다.