Как узнать, пересекает ли луч прямоугольник?

Question

У нас есть луч, который начинается в точке A(X, Y) и продолжается вечно через заданную точку B(X, Y) != A. У нас есть прямоугольник, определяемый точками K,L,M,N каждый со своим (X, Y).

Интересно, как определить, пересекается ли наш луч с любой точкой нашего прямоугольника (получить 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, который пересекает прямоугольник. Если ваш прямоугольник выровнен по оси, это будет проще вычислять в цифровом смысле, но логика должна быть аналогичной.

---

Вы можете представить направленную линию L, как [a, b, c] таким образом, что, если точка P является (X, Y):

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 

Обратите внимание, что это является излишним в том смысле, что для любого k > 0, [к * а , 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), можно вычислить однородные координаты линии через P и Q с использованием 3-D поперечного произведения их однородных координат:

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 

Вы можете проверить математически, что точки Р и Q оба на описанном выше линиях PQ.

---

Представлять отрезок линии AB, которая пересекает прямоугольник, первый вектор вычислений V = B - A, как в @ btilly отвечают.Для однородных координат, это работает следующим образом:

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, но делать это таким образом избежать ненужных деления на ноль случаи ...)

---

Теперь мы можем вычислить луч пересечение: мы представляем сегмент линии AB параметрическими [u,v] координатами каждой конечной точки: { 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-loop; и, если прямоугольник выровнен по оси, вы можете значительно упростить арифметику. Однако решение из 4 случаев во внутреннем цикле должно оставаться неизменным для каждого ребра.

Answer 4

Менее умный, но концептуально более простой подход: луч пересекает прямоугольник тогда и только тогда, когда он пересекает хотя бы одну из сторон. Поэтому для каждой стороны прямоугольника найдите пересечение (если оно есть) линии, проходящей через конечные точки с лучом AB; то это просто проверка диапазона, чтобы определить, лежит ли это пересечение, является частью отрезка линии на границе прямоугольника или если она находится снаружи.