Точка пересечения прямых:
a1, b1, c1 - коэффициенты первой прямой
a2, b2, c2 - коэффициенты второй прямой
x, y - точка пересечения
x = -(c1 * b2 - c2 * b1)/(a1 * b2 - a2 * b1)
y = -(a1 * c2 - a2 * c1)/(a1 * b2 - a2 * b1)
Мы уже знаем как проверять прямые на пересечение (они не параллельны) и находить точку их пересечения
Теперь научимся делать это с отрезками:
Для начала научимся просто проверять их на пересечение:
Отрезки пересекаются, если концы одного находятся по разные стороны от другого и наоборот (это легко проверяется векторным произведением)
Единственный случай, когда это не сработает - когда отрезки лежат на одной прямой
Для него нужно сделать проверку на пересечение т.н. bounding box (ограничивающий прямоугольник отрезка) - проверяем на пересечение проекции отрезков на оси X и Y
Теперь, когда мы умеем проверять отрезки на пересечение, научимся находить точку (или отрезок) их пересечения:
-Если они не пересекаются, то понятно, что такой точки не существует;
-Иначе построим прямые, на которых лежат эти отрезки
Если они параллельны, то отрезки лежат на одной прямой, и нам надо найти отрезок пересечения - от максимальной из левых границ отрезков до минимальной из правых границ (точка меньше другой точки, если она левее,
в случае равенства X-координаты - если она ниже)
Если же прямые не параллельны, то найдём точку их пересечения и вернём её