Нужно найти алгоритм для пересечения отрезка с набором прямоугольников

[Trinock]

Здравствуйте, задача состоит в следующем: есть направленный отрезок, который задается в 2d пространстве координата своих точек {(x1, y1), (x2, y2)}. Пространство разбивается на прямоугольные клетки, у каждой есть свой номер. Имея координаты концов отрезка нужно узнать, через какие клетки он проходит. Помогите найти алгоритм, решающий такую задачу, думаю задача довольно распространненая и не хотелось бы изобретать велосипед.

[Kostia]

Можно легко рассчитать номера(координаты) клеток в которые попали концы отрезка, а потом уже рассчитать клетки, которые находятся между. Для этого алгоритм рисования линии пригодится, помню в книжке DirectX и Delphi Фленов приводил алгоритм как попикселям в DirectDarw нарисовать отрезок.
Просто само название алгоритма не помню, если оно вообще есть )))

[Виталий Желтяков]

Если будет разделение на клетки, то нужно использовать алгоритм А*.

[invizor]

Астар это вообще если препятствия есть, хотя может в какой-нибудь книжке и быть описан. Но думаю тут "велосипед изобрести" быстрее:
Предположим что прямоугольники параллельные по x и y и одинаковые.
h[i] это система горизонтальных линий прямоугольника, v[i]- система вертикальных, массивы начинаются в клетке начала отрезка заканчиваются в клетке на конце. Ищем пересечения отрезка с вертикальнами и горизонтальными прямыми (уравнение y=(y2-y1)/(x2-x1)-y2*x1-y1*x2 и вместо x или y подставляются v[i] и h[i]).
Если есть пересечения, записываем в is_v[i] и is_h[i] 1 иначе записываем 0,
пусть есть матрица matr (1 при наличии пересечения 0 при отсутствии), 1 получается тогда и только тогда, когда есть пересечение с двумя отрезками прямоугольника и в прямоугольниках границ отрезка.(для matr[i,j] это v[i],v[i+1],h[i],h[i+1] а также matr[0,0],matr[m,n])

[Trinock]

Спасибо за помощь, попробую разные варианты.