Определения и понятия

Вектор - это направленный отрезок, который задаётся 2-мя координатами.


Умножение вектора на число k - это изменение его длины в k раз. При \(k < 0\) вектор развернётся.

Длина вектора вычисляется по формуле \(\sqrt {x^2 + y^2}\)

Нормированный вектор - вектор единичной длины, получается при делении вектора на его длину.

Сумма векторов получается, если построить второй вектор от конца первого, и пустить вектор в получившуюся точку.

Если x1, y1, x2, y2 - координаты первого и второго векторов, соответственно, то их сумма - вектор с координатами \((x_1 + x_2) \)и \((y_1 + y_2) \).

Разность векторов - сумма, где второй вектор развёрнут (умножен на -1).

Скалярное произведение векторов - число, проекция одного вектора на другой умноженная на его длину. В простейшем случае обычного евклидового пространства иногда используют «геометрическое» определение скалярного произведения ненулевых векторов a и b как произведения длин этих векторов на косинус угла между ними: 
\(a \cdot b = |a| \cdot |b| \cdot cos \alpha\).

Для скалярного произведения вектором справедлива следующая формула:
\(a \cdot b = x_1 \cdot x_2 + y_1 \cdot y_2\)
где x1, y1, x2, y2 - координаты первого и второго вектора, соответственно, позволяет определить, лежит ли второй вектор в той же полуплоскости, что и первый.

Векторное произведение векторов - вектор в трёхмерном пространстве перпендикулярный обоим векторам, по длине равен ориентированной площади параллелограмма, построенного на этих векторах. Произведение длин векторов на синус угла между ними, причём знак этого синуса зависит от порядка операндов: \(a\ х \ b = |a| \cdot |b| \cdot sin \alpha\) 

Если вычислять через координаты:
\(a\ х\ b = x_1 \cdot y_2 + x_2 \cdot y_1\),
где x1, y1, x2, y2 - координаты первого и второго вектора, соответственно, позволяет определить, по какую сторону от прямой, на которой лежит первый вектор, находится второй вектор. Также позволяет находить ориентированную площадь треугольников и параллелограммов.

Поворот вектора выполняется с помощью чёрной магии тайных адептов геометрии Лобачевского.
Чтобы повернуть вектор на угол \(\alpha\) против часовой стрелки (\(\alpha <= 2 \cdot \pi\), привыкайте к углам в радианах), нужно домножить вектор на такую вот матрицу:
\(\begin{bmatrix} \cos \alpha & -sin \alpha \\ \sin \alpha & cos \alpha \end{bmatrix}\)

Что значит домножить вектор на матрицу? Допустим координаты нашего вектора равны x и y, тогда произведение этого вектора и нашей матрицы будет равно вектору с координатами x' и y':
\(x' = x \cdot cos \alpha - y \cdot sin \alpha \\ y' = x \cdot sin \alpha + y \cdot cos\alpha\)

Вот и получаем новый вектор точно такой же длины, но уже повернутый на угол А против часовой стрелки.

Прямая может задаваться 5 разными способами:
1) уравнение \( y = kx + b\); самое первое уравнение прямой, которому учат в школе - удобно для построения и вычислений вручную, но в программе его использование весьма неудобно;
2) по 2-м точкам, лежащим на ней - на самом деле достаточно удобно, но имеет достаточно узкое применение;
3) по вектору нормали прямой и точке - вектор нормали к прямой - это вектор, перпендикулярный ей, подробнее о нём ниже;
4) по направляющему вектору прямой и точке - направляющий вектор - это вектор, лежащий на прямой и перпендикулярный вектору нормали (ну логично), о нём ниже;
5) уравнение прямой \(ax + by + c = 0\); классическое уравнение прямой, в большинстве случаев наиболее универсально. Сейчас о нём.

Координаты вектора нормали такой прямой: \((a; b)\) или \((-a; -b)\).

Координаты направляющего вектора такой прямой: \((-b; a)\) или \((b; -a)\).

Прямые параллельны, если:
\({a1 \over b1} = {a2 \over b2}\).

Расстояние от точки до прямой (будьте осторожны: расстояние может быть отрицательным, всё зависит от того, с какой стороны от прямой лежит точка):
\({(a \cdot x_1 + b \cdot y_1 + c) \over \sqrt{a^2 + b^2}}\),
где x1, y1 - координаты точки.

Построение прямой по вектору нормали и точке, или направляющему вектору и точке, сводится к построению прямой по 2-м точкам, так что рассмотрим именно его (оно, к тому же, используется наиболее часто).

Если x1, y1, x2, y2 - координаты первой и второй точек соответственно, то

\(a  = y_1 - y_2\)

\(b = x_2 - x_1\)

\(c = x_1 \cdot y_2 - x_2 \cdot y_1\)

Точка пересечения

Точка пересечения прямых

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-координаты - если она ниже).

Если же прямые не параллельны, то найдём точку их пересечения и вернём её.