Точки и векторы

Школьная геометрия работает с объектами: треугольник $ABC$, биссектриса, признак равенства. В программе так нельзя — компьютер не умеет «применить теорему».

Поэтому вычислительная геометрия устроена иначе: всё живёт в системе координат, любой объект — это набор чисел, а решение — цепочка формул над этими числами.

Хорошая новость: формул немного, и почти все выводятся из двух произведений, о которых в следующих статьях.

Точка

Точка задаётся парой координат $(x, y)$. Больше про неё сказать нечего.

Вектор

Вектор — направленный отрезок. Вектор из точки $P$ в точку $Q$ имеет координаты

$$\vec{PQ} = (x_Q - x_P,\; y_Q - y_P)$$

то есть «насколько сдвинуться по $x$» и «насколько по $y$».

Здесь возникает вопрос: почему у вектора координат столько же, сколько у точки, хотя задаётся он двумя точками?

Ответ: векторы, равные по длине и направлению, считаются одним и тем же вектором. Начальная точка вектору безразлична — важна только разность. Формально это класс эквивалентности; практически это значит, что любой вектор можно перенести началом в ноль, и тогда его конец окажется в точке с теми же координатами.

Именно поэтому в коде для точки и для вектора используют одну структуру. Различие только в том, как мы её трактуем.

Обратный вектор получается сменой знака у обеих координат: $\vec{QP} = -\vec{PQ}$.

Операции

Сложение. $\vec{a} + \vec{b}$ — это «пройти по $\vec{a}$, затем по $\vec{b}$». В координатах просто:

$$\vec{a} + \vec{b} = (a_x + b_x,\; a_y + b_y)$$

Школьные «правило треугольника» и «правило параллелограмма» — два способа нарисовать одно и то же. В координатах ни то, ни другое не нужно.

Вычитание. $\vec{a} - \vec{b} = (a_x - b_x,\; a_y - b_y)$. Геометрически: если отложить оба вектора из одной точки, разность — вектор из конца $\vec{b}$ в конец $\vec{a}$.

Умножение на число. $\alpha \vec{v} = (\alpha v_x,\; \alpha v_y)$ — растяжение в $\alpha$ раз. При отрицательном $\alpha$ вектор ещё и разворачивается.

Длина. По теореме Пифагора:

$$|\vec{v}| = \sqrt{v_x^2 + v_y^2}$$

Отсюда расстояние между точками — длина вектора между ними.

Длина в квадрате

Отдельно стоит завести функцию, возвращающую квадрат длины, без корня.

long long len2() const { return x * x + y * y; }

Причина практическая: сравнить два расстояния — то же самое, что сравнить их квадраты, а корень вносит погрешность и требует перехода к вещественным числам. Если в задаче нужно «найти ближайшую пару» или «самый длинный отрезок», работайте с квадратами и оставайтесь в целых числах.

Это общий принцип раздела: избегайте корней и делений, пока они действительно не понадобятся.

Поворот на 90 градусов

Единственный поворот, который встречается постоянно и не требует тригонометрии:

$$(x, y) \longmapsto (-y, x) \quad \text{против часовой}$$ $$(x, y) \longmapsto (y, -x) \quad \text{по часовой}$$

Проверяется подстановкой в формулы синуса и косинуса от $\alpha + \frac{\pi}{2}$, но проще запомнить: координаты меняются местами, одна из них меняет знак.

Поворот на произвольный угол тоже существует и выражается через синус и косинус, но в задачах встречается реже — и почти всегда его удаётся обойти.

Что дальше

Пока мы умеем складывать, вычитать, растягивать и мерить длину. Этого мало: неизвестно, как узнать угол, как понять, слева или справа лежит точка, как найти расстояние до прямой.

Всё это даёт пара произведений — скалярное и векторное. Они и есть содержание раздела; остальное — их применения.