Как определить пересечение отрезка и полигона?

Question

[i_v]

Посоветуйте пожалуйста быстрый алгоритм для поиска факта пересечения отрезка, определенного 2-мя точками, и полигона (повернутого прямоугольника). Координаты пересечения не нужны.

уточнение:
На самом деле задача заключается в отсеивании отрезков, которые не попадают в экран монитора. Слой, на котором лежат отрезки может быть повернут. Координаты отрезков даны в системе координат повернутого слоя.

Comments

[Евгений Шатунов]

Пространство тебе нужно 2D или 3D? Методы отличаться будут кардинально.

Answer 1

[Сергей]

Мне кажется Вам нужно перейти в систему координат прямоугольника, а дальше просто изучить частные случаи нахождения отрезка вне и в прямоугольнике

Answer 2

[Mrrl]

Сначала лучше перейти в систему координат, в которой стороны прямоугольника параллельны координатным осям, а центр - в точке (0,0): пусть при преобразовании (x,y) -> (p*x+q*y+r,-q*x+p*y+s) прямоугольник переходит в abs(X) <= A, abs(Y) <= B.
Пусть (X1,Y1) и (X2,Y2) - координаты вершин отрезка после преобразования.
Если max(X1,X2) < -A || min(X1,X2) > A || max(Y1,Y2) < -B || min(Y1,Y2) > B, то не пересекается: отрезок находится за одной из сторон прямоугольника.
В противном случае условием пересечения, насколько я понимаю, будет
abs(X1*Y2-Y1*X2) <= abs(A*(Y2-Y1)) + abs(B*(X2-X1))
Тщательно не проверял, но шансы, что формула правильная, хорошие.