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

Если бы мы могли записать прямую как

, то условие пересечения выглядело бы так:

. В общем виде

Тут под векторным произведением понимается определитель из координат, как обычно.

Точка пересечения находится таким образом:

Пусть точка

является пересечением. Тогда существуют такие числа t и \alpha, что

Исключим rf и перепишем это так:

Это система из двух уравнений с двумя неизвестными. Разрешаем (я использовал м-д Краммера) её:

Необходимое нам условие выполняется, если

1. \alpha и t существуют, то есть знаменатель не обращается в нуль, отрезок не параллелен лучу.

2. t>0, то есть точка пересечения находится со стороны \vec{a}.

3.

, то есть точка пересечения принадлежит отрезку.

По идее, из этих условий должно автоматически выполняться условие, выведенное выше:

P.S. лучше перепроверить все выкладки, мог ошибиться.