선분이 정사각형과 교차하는지 감지

Question

누구든지 이것에 대한 간단한 알고리즘을 가지고 있습니까?회전이나 ​​다른 것이 필요하지 않습니다.두 점으로 이루어진 선분이 정사각형과 교차하는지 알아내는 것

Answer 1

이 코드는 트릭을 수행해야 합니다.선이 측면과 교차하는 위치를 확인한 다음 그것이 사각형의 너비 내에 있는지 확인합니다.교차 횟수가 반환됩니다.

float CalcY(float xval, float x0, float y0, float x1, float y1)
{
    if(x1 == x0) return NaN;
    return y0 + (xval - x0)*(y1 - y0)/(x1 - x0);
}

float CalcX(float yval, float x0, float y0, float x1, float y1)
{
    if(x1 == x0) return NaN;
    return x0 + (yval - y0)*(y1 - y0)/(x1 - x0);
}

int LineIntersectsSquare(int x0, int y0, int x1, int y1, int left, int top, int right, int bottom)
{
    int intersections = 0;
    if(CalcX(bottom, x0, y0, x1, y1) < right && CalcX(bottom, x0, y0, x1, y1) > left  ) intersections++;
    if(CalcX(top   , x0, y0, x1, y1) < right && CalcX(top   , x0, y0, x1, y1) > left  ) intersections++;
    if(CalcY(left  , x0, y0, x1, y1) < top   && CalcY(left  , x0, y0, x1, y1) > bottom) intersections++;
    if(CalcY(right , x0, y0, x1, y1) < top   && CalcY(right , x0, y0, x1, y1) > bottom) intersections++;
    return intersections;
}

참고:이 코드는 이론적이며 테스트되지 않았으므로 정확하지 않을 수 있습니다.

Answer 2

벡터를 캐스팅하고 교차하는 가장자리 수를 세어 이를 수행할 수 있습니다.

교차하는 가장자리가 짝수이면 개체 외부에 있고, 교차하는 가장자리가 홀수이면 개체 내부에 있습니다.

이는 모든 닫힌 다각형에 적용됩니다.

Answer 3

방법은 다음과 같습니다.
- x 좌표를 기준으로 정사각형의 꼭지점을 정렬합니다.
- x 좌표로 선의 끝점을 정렬합니다.
- 선의 minX 끝에서 가운데 ​​두 개의(x 좌표 기준) 정사각형 꼭지점 각각까지의 각도를 계산합니다.
- 선의 각도를 계산
- 선의 각도가 가능한 각도 내에 있는 경우 길이를 확인하기만 하면 됩니다. 선의 maxX 끝 > 사각형의 minX 정점인지 확인하세요.

사각형이 선을 직접 향하고 있으면 아마도 깨질 것입니다. 이 경우 사각형의 첫 번째 가장자리를 확인하여 특별한 경우로 하겠습니다.