Какова формула пересечения отрезков на шахматной доске?
Привет,
на тему пересечений отрезков и проекции точки на линию - все готовое уже есть, много примеров и формул. Как можно упростить формулы, если геометрическое пространство - это шахматная доска? Т.е.
1. Координаты точки, или начала и конца отрезка - целочисленные.
2. Отрезки могут располагаться в трех направлениях: вертикально, горизонтально, по диагонали.
Т.е. в этом "мире" нет иных углов, кроме 0, 45 и 90.
Задача:
1. Найти точку пересечения двух отрезков.
2. Найти точку пересечения отрезка и линии, проведенной (до первого пересечения) из некой точки в одном из 8 возможных направлений.
Готового кода, конечно, не прошу, просто куда копнуть, чтобы посчитать это быстро (нужна высокая скорость вычислений).
UPD1: еще проще, есть точка с двумя координатами, и из нее направление (одно из 8 возможных, по сторонам света). Где-то на этой же плоскости есть отрезок, заданный координатами начала и конца. Если двигаясь из точки мы в итоге пересечем отрезок, то только под углом 90 или 45 градусов. Нужно найти точку пересечения, имяя координаты точки, направление движения, и координаты отрезка.
Средний