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

Question

우리는 점 A(X, Y)에서 시작하여 주어진 지점 B(X, Y) != A을 통해 영원히 계속되는 광선을가집니다. 우리는 각각 (X, Y)을 가진 점 K,L,M,N에 의해 정의 된 직사각형을 가지고 있습니다.

우리 광선이 우리 직사각형의 어떤 점과 교차하는지 감지하는 방법을 궁금합니다 (bool, 좌표는 아닙니다)? 그런 값을 계산하는 알고리즘은 무엇입니까?

Answer 1

나를 똑바로 세우자. 벡터 v은 (b_x - a_x, b_y - a_y) 방향으로 출발하고 (a_x, a_y)에서 시작합니다.

벡터 w = (b_y - a_y, a_x - b_x)을 고려하십시오. 그것은 첫 번째에 직각이다. 따라서 점 (p_x, p_y)에 대해 (p_x - a_x, p_y - a_y)의 내적 값을 w으로 찍고 기호를 보면 쉽게 벡터의 어느쪽에 있는지 알 수 있습니다.

그래서 네 모퉁이가 네 모퉁이 인 점 제품을 가져 오십시오. 만약 어떤 도트 상품이 0이라면, 벡터 상에 있습니다. 부호가 바뀌면 교차가 있습니다. 부호가 항상 같으면 교차가 없습니다.

Answer 2

스윕 라인 알고리즘을 사용하여이를 수행 할 수 있습니다.

http://en.wikipedia.org/wiki/Sweep_line_algorithm

Answer 3

당신은 아마도 사각형을 교차하는 선 AB의 세그먼트 (있는 경우)를 계산합니다. 직사각형이 축으로 정렬되어 있으면 수치 적으로 계산하기 쉽지만 논리는 비슷해야합니다. 이 모든 k > 0 [케이 *에 해당한다는 점에서 중복이라고

let L(P) = a*X + b*Y + c 

then, if L(P) == 0, point P is on L 
     if L(P) > 0, point P is to the left of L 
     if L(P) < 0, point P is to the right of L 

참고 점 P는 (X, Y) 경우 이러한 것을 L[a, b, c]로

---

당신은 방향 선을 나타낼 수 , k * b, k * c]는 동일한 줄을 나타냅니다 (이 속성은 homogeneous coordinate system이됩니다). 당신은 라인의 균일 한 좌표를 계산할 수 있습니다, 어떤 경우

2D point P = (X, Y) 
-> homogeneous coordinates [x, y, w] for P are [X, Y, 1] 
    L(P) = L.a*P.x + L.b*P.y + L.c*P.w == a*X + b*Y + c*1 

당신의 사각형의 주어진 두 개의 코너 (예를 들어, P 및 Q 일) : 우리는 또한 좌표 세 번째로 보강하여 균일 한 좌표 점을 나타낼 수 그 동차 좌표를 3-D 간 제품을 사용하고 PQ 통해 :

는

homogeneous coordinates for line PQ are: [P.X, P.Y, 1] cross [Q.X, Q.Y, 1] 
    -> PQ.a = P.Y - Q.Y 
    PQ.b = Q.X - P.X 
    PQ.c = P.X*Q.Y - Q.X*P.Y 

하면 P가 가리키는 수학적으로 확인할 수 있으며, Q는 상술 한 선 PQ에 모두.

---

는 @ btilly의 대답으로, 사각형, 첫째 컴퓨팅 벡터 V = B - A 교차 라인 AB의 세그먼트를 나타냅니다.다음과 같이 균일 한 좌표를 들어,이 작품 :

A = [A.X, A.Y, 1] 
B = [B.X, B.Y, 1] 
-> V = B - A = [B.X-A.X, B.Y-A.Y, 0] 

for any point C on AB: homogeneous coordinates for C = u*A + v*V 
    (where u and v are not both zero) 

포인트 C는 경우에만 u 및 v은 음이 아닌 모두 줄의 선 부분에있을 것입니다. (이 표현은 C = A + lambda * V의 일반적인 공식에 비해, 모호한 것 같다,하지만이 방법을 수행하는 것은 불필요한으로 나누기의 경우 ...을 피할 수)

---

이제, 우리는 광선의 교차점을 계산할 수있다 : 우리가 대표 각 끝점의 파라 메트릭 [u,v] 좌표에 의한 AB 행의 세그먼트 : { start = [start.u, start.v]; end = [end.u, end.v] }.

우리는 반 시계 방향으로 직사각형의 가장자리를 계산하여 직사각형 내부의 점이 모든 가장자리의 왼쪽/양면 (L(P)>0)이되도록합니다.

Starting segment is entire ray: 
    start.u = 1; start.v = 0 
    end.u = 0; end.v = 1 

for each counterclockwise-directed edge L of the rectangle: 
    compute: 
    L(A) = L.a*A.X + L.b*A.Y + L.c 
    L(V) = L.a*V.X + L.b*V.Y 
    L(start) = start.u * L(A) + start.v * L(V) 
    L(end) = end.u * L(A) + end.v * L(V) 
    if L(start) and L(end) are both less than zero: 
    exit early: return "no intersection found" 
    if L(start) and L(end) are both greater or equal to zero: 
    do not update the segment; continue with the next line 
    else, if L(start) < 0: 
    update start coordinates: 
     start.u := L(V) 
     start.v := -L(A) 
    else, if L(end) < 0: 
    update end coordinates: 
     end.u := -L(V) 
     end.v := L(A) 

on normal loop exit, the ray does intersect the rectangle; 
the part of the ray inside the rectangle is the segment between points: 
    homog_start = start.u * A + start.v * V 
    homog_end = end.u * A + end.v * V 
return "intersection found": 
    intersection_start.X = homog_start.x/homog_start.w 
    intersection_start.Y = homog_start.y/homog_start.w 
    intersection_end.X = homog_end.x/homog_end.w 
    intersection_end.Y = homog_end.y/homog_end.w 

이는 사각형이 아닌 임의의 볼록한 다각형에 적용됩니다. 위의 것은 실제로 일반적인 광선/볼록 다각형 교차 알고리즘입니다. 사각형의 경우 for 루프를 언 롤할 수 있습니다. 직사각형이 축 정렬되어 있으면 산술을 대폭 단순화 할 수 있습니다. 그러나 내부 루프의 4 가지 경우 결정은 각 에지마다 동일하게 유지되어야합니다.

Answer 4

덜 영리하지만 개념적으로 더 간단한 접근법입니다. 광선은 적어도 하나의 측면과 교차하는 경우에만 직사각형과 교차합니다. 따라서 사각형의 각면에 대해 광선 AB로 끝점을 통과하는 선의 교차점 (있는 경우)을 찾습니다. 교차점이 직사각형의 경계에있는 선분의 ​​일부인지 또는 외부에 있는지 여부를 결정하는 것은 단순히 범위 검사입니다.