선분이 사각형과 교차하는지 확인하는 방법

Question

두 점 a와 b로 구분되는 선분이 있습니다. 나는 또한 x<x<x1 및 y0<y <y1에 의해 결정되는 사각형을 가지고 있는데, 여기서 x1-x0 = y1-y0입니다. 세그먼트의 일부가 사각형 내부의 영역과 교차하는지 확인하려고합니다. (세그먼트가 교차로로 계산되지 않는면을 만지면).

내 생각이 그림

function(a, b, x0, x1, y0, y1) { 
    if (a or b is inside square) 
    return true; 
    else { 
    switch (which quadrant is a in) { 
     case 1: return (ab intersects top of square); 
     case 2: return (ab intersects left of square); 
     case 3: return (ab intersects bottom of square); 
     case 4: return (ab intersects right of square); 
    } 
    } 
} 

이 문제를 접근하는 더 나은 방법이 있는지 궁금 해서요을 사용하고 있었다.

Answer 1

라인 세그먼트를 기울기 및 (경우에 따라 가설적인 경우) y 절편으로 가져 와서 y = mx + b 형식의 함수로 만듭니다 (여기서 m은 기울기이고 b는 절편입니다) . 그런 다음 사각형의 도메인 및 범위에서 해당 함수를 확인하십시오. 즉, 왼쪽과 오른쪽 사이의 임의의 x에 대해 y가 위와 아래 사이에 있습니까?

Answer 2

2 개의 사례 만 확인하면됩니다.

선이 위쪽 꼭지점에서는 1 행 위에 있거나 아래쪽 꼭지점에서 3 행 아래에있는 경우. 이 조건 중 하나라도 true를 반환하면 교차가 없습니다.

예를 들어, 만약 y(x0) > y1와 A, B에 의해 결정 당신의 라인 y=mx+n을 계산하고 확인할 것 1 호선에 대해 확인하는 유사 y(x1) > y1

Answer 3

당신은 분석적 불평등과의 파라 메트릭 방정식을 사용하여이 문제를 해결할 수 있음 선분 (우리가 xb-xa/yb-ya을 표시하기 위해 dx/dy 사용) :

x0 < xa + t.dx < x1 
    y0 < xb + t.dy < y1 
    0 <  t < 1 

그런 다음 같은 기간의 세 bracketings을 수 있도록 재 작성이 나타납니다

(x0 - xa).dy < t.dx.dy < (x1 - xa).dy 
    (y0 - ya).dx < t.dx.dy < (y1 - ya).dx 
       0 < t.dx.dy < dx.dy 

주의 : 음수 인 d을 곱하면 부등식의 멤버가 스왑되어야합니다. 따라서 4 가지 경우가 있습니다. (사실 9d '으로들도 0 할 수있다이 경우 쉽게 여기에 무시됩니다..)

마지막으로, 이러한 bracketings 즉, 호환되는 적어도 하나의 가능한 t 값이 있음을 표현 :

Max((x0 - xa).dy, (y0 - ya).dx, 0) < Min(x1 - xa).dy, (y1 - ya).dx, dx.dy) 

가

밀접하게 살펴보면 접근 방식의 요소를 인식 할 수 있습니다. 예를 들어 0 < (x1 - xa).dy은 오른쪽을 비교 한 것이고 (x0 - xa).dy < (y1 - ya).dx은 대각선을 비교 한 것입니다.

이 방법은 경사 세그먼트 결론 4 -, 5 * 및 5 <> 위해 그리고, 9가지 경우에 대해 논의 dx/dy 다음 4 <> (비교)를 계산하는 2 - 걸린다.

이와 비슷한 것 (주의, 선택 취소!) :

dx= xb - xa; dy= yb - ya; 
if (dx > 0) 
{ 
    if (dy > 0) return Max((x0 - xa).dy, (y0 - ya).dx, 0) < Min(x1 - xa).dy, (y1 - ya).dx, dx.dy); 
    else if (dy < 0) return Max((x1 - xa).dy, (y0 - ya).dx, 0) < Min(x0 - xa).dy, (y1 - ya).dx, dx.dy); 
    else return Max(y0 - ya, 0) < Min(y1 - ya, dy); 
} 
else if (dx < 0) 
{ 
    if (dy > 0) return Max((x0 - xa).dy, (y1 - ya).dx, 0) < Min(x1 - xa).dy, (y0 - ya).dx, dx.dy); 
    else if (dy < 0) return Max((x1 - xa).dy, (y1 - ya).dx, 0) < Min(x0 - xa).dy, (y0 - ya).dx, dx.dy); 
    else return Max(y1 - ya, 0) < Min(y0 - ya, dy); 
} 
else 
{ 
    if (dy > 0) return Max(x0 - xa, 0) < Min(x1 - xa, 0); 
    else if (dy < 0) return Max(x1 - xa, 0) < Min(x0 - xa, 0); 
    else return false; 
} 

Answer 4

내가 생각할 짧은 대답은 당신의 라인과 표준 계산 기하 구조 크로스 제품을 사용하여 사각형 의 4 개 라인 바로 테스트 세그먼트 교차로입니다.

이 빠른 튜토리얼을하다 그러니 그냥 같은 두 줄 AB (세그먼트) 및 CD (사각형의면)

을주고있다 세그먼트 교차점을 테스트 http://web.stanford.edu/class/cs97si/09-computational-geometry.pdf

Define ccw(A,B,C) = (B-A) X (C-A) where A,B,C is some point ccw(A,B,C) < 0 means C lies on the left side of line AB ccw(A,B,C) > 0 means C lies on the right side of line AB

그들은 제대로 교차합니다 (예 : 터치 케이스 제외). iff

ccw(A,B,C) * ccw(A,B,D) < 0 AND ccw(C,D,A) * ccw(C,D,B) < 0

단순히 "C와 D는 AB의 다른면에 있고 A와 B는 CD의 다른면에 있습니다"-> 교차점