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