Как вычислить наличие препятствий на пути в 2d мире?

Question

Есть массив 2d объектов (в основном прямоугольники и квадраты) .

Нужно вычислить есть ли на пути движения снаряда один из объектов.

Сейчас я проверяю наличие объектов в треугольнике ABC, где медиана AM — и есть путь движения снаряда.
За угол А я взял 30°.

Проблема в том, что объекты двухмерные и имеют различную ширину и длину.
Алгоритм ошибается в ситуации когда объект слишком широкий, но его центр выходит за площадь треугольника.

Думал насчет равномерного нанесения на путь точек и проверке вхождения объекта в эти точки, но у меня нет опыта в этой обрасти.

Как правильно решить данную задачу?

Уже помогли тут http://habrahabr.ru/qa/28551/
Всем спасибо

Алексей Федотов · Accepted Answer

Не понял идею с треугольником.. . 
По-моему, если решать "в лоб", то задача состоит в том, чтобы определить, существуют ли точки пересечения отрезка (траектория снаряда) с каким-то объектом. 
Простейший алгоритм на входе получает массив объектов, координаты отрезка-траектории. В цикле перебираем все объекты, находим точки пересечения с объектом, вычисляем расстояние от начала траектории. В конце алгоритма выбираем пересечение с минимальным расстоянием - это будет точка пересечения с ближайшим объектом. 
 
Пересечение прямоугольника с отрезком в общем случае распадается на подзадачу пересечения с каждой из сторон. Алгоритм можно найти готовый - они обычно очень красивые, построенные на векторной алгебре или на элементах аналитической геометрии. Например, алгоритм отсечения Коэна - Сазерленда - этого, пожалуй, будет достаточно. Можно и самому изобрести. 
 
Возможно, что понадобится так же оптимизация алгоритма. Но это уже отдельный разговор.

Олька Брыкова · Answer

Вы напишите, что у вас из себя представляет мир и какие пересечения нужны?