Точки и вектора. Геометрия

Точки и вектора
Любую геометрическую задачу можно решить оперируя только точками и векторами.
Отрезок можно представить как 2 точки. Ломаную – как последовательный набор точек. Любой многоугольник – это замкнутая ломаная.
Прямую или луч можно представить как точку и направляющий вектор.
Окружность или сферу – как точку, задающую центр, и радиус-вектор.
Для решения задач определяются структуры, описывающие точку и вектора, после чего реализуется алгоритм, который уже не содержит в себе координатного метода.

Реализация вектора 1
Создадим структуру Vector. Сделаем её шаблонной так, как некоторые задачи решаются в целых числах, а некоторые в вещественных. Шаблонность добавляет универсальности но обычно не нужна в условиях соревнования.

Реализация вектора 2
Одной из характеристик вектора является его длина, которая равна sqrt(x2 + y2). Заметим, что даже если сам вектор имеет целочисленные координаты, его длина, скорее всего, имеет вещественное значение. Однако в некоторых задачах достаточно узнавать квадрат длины.
Слово const после имени метода позволяет его вызывать у констант типа данной структуры.

Реализация вектора 3
Сумма двух векторов – это вектор начало которого совпадает с началом первого, а конец – с концом второго, отложенного от конца первого.
Разность двух векторов – это вектор, который начинается в конце второго и заканчивается в конце первого, если первый и второй отложить от одной точки.
Унарный минус меняет направление вектора на обратное.

Реализация вектора 4
Скалярное произведение векторов a и b – это число, равное произведению длин этих векторов на косинус угла между ними. Зная координаты векторов, скалярное произведение можно вычислить как a.x * b.x + a.y * b.y в двухмерном пространстве или a.x * b.x + a.y * b.y + a.z * b.z в трёхмерном пространстве.
Векторное произведение векторов a и b в трёхмерном пространстве – это вектор c направленный перпендикулярно плоскости, задаваемой данными векторами, длина которого равна произведению длин этих векторов на синус угла между ними. В двухмерном пространстве векторное произведение – это число, равное a.x * b.y - a.y * b.x. По знаку этого числа можно определить, как по отношению к вектору a повёрнут вектор b
(векторное произведение > 0 – против часовой стрелки, < 0 – по часовой стрелке, 0 – коллинеарные).

Реализация вектора 4
Произведения вектора a на число b – это вектор с, коллинеарный вектору а, его длина равна длине а, умноженной на b, а направление совпадает с а, если k > 0, иначе является противоположным. Для того чтобы получить произведение вектора на число нужно каждую координату вектора умножить на это число.
a
b
a^b < 0
b^a > 0

Реализация вектора 5
Для удобства будет не лишним переопределить и операторы потокового ввода-вывода.
Деление вектора a на число b – это операция, эквивалентная произведению вектора а на число 1/b.

Реализация вектора 6
В качестве вспомогательных шагов часто может понадобиться получить вектор в вещественных числах (если изначально он в целых), нормализовать вектор (получить вектор длиной 1 и с тем же направлением) и изменить длину на заданную.

Реализация вектора 7
Для того что бы повернуть вектор на определённый угол нужно умножить матрицу поворота на этот вектор.
Стандартные функции С++ работают с радианами.

Проекция вектора на вектор
a
b
c
alpha
Вектор с – проекция вектора а на вектор b.
Длина вектора с равна произведению длины вектора а на косинус угла alpha. Она относиться к длине b как некоторый коэффициент
k = |a|*cos(alpha)/|b|.
Тогда c = b * k.
Если вспомнить, что a * b = |a| * |b| * cos(alpha), то можно определить k как a * b / |b|2.

Реализация вектора 8
Метод ProjectionK возвращает коэффициент, на который нужно умножить вектор, у которого вызван метод, чтобы получить проекцию на него вектора, который является аргументом.
Метод Projection возвращает вектор-проекцию вектора v1 на вектор, у которого вызван метод.

Реализация точки 1
Структура точки довольно похожа на структуру вектора. В некоторых случаях из точки может понадобиться получить вектор. Операторы ввода-вывода переопределяются аналогичным образом.

При прибавлении к точке вектора получается новая точка.
Соответственно, при вычитании из одной точки другой получается вектор.
Реализация точки 2
В рамках соревнований, когда времени мало, а готовом шаблоном воспользоваться нельзя, большинство предпочитает реализовывать только структуру вектора в той степени, в какой необходимо, т.к. она по сути полностью покрывает возможности структуры точки.

Нахождение угла между двумя векторами
Разделив векторное произведение векторов на произведение их длин получим синус угла между ними.
Разделив скалярное произведение векторов на произведение их длин получим косинус угла между ними.

Немного прекода от себя…

Полярный угол точки
Полярный угол точки – это угол между вектором, с началом в точке пересечения координатных осей и концом в этой точке, и осью Х.
Самая точная функция для нахождения полярного угла – это atan2(double Y, double X). Она возвращает значения в диапазоне
[-π; π).
Сравнение вещественных чисел на равенство / неравенство
Так как вычисления в вещественных числах происходят с некоторой погрешностью, нельзя гарантировать, что результат вычислений будет равен ожидаемому числу со 100% точностью, а значит эти числа нельзя сравнивать через ‘==‘ или ‘!=‘.
Корректная проверка вещественных чисел на равенство:
fabs(a - b) <= EPS (fabs(a - b) > EPS – проверка на неравенство).

Алгоритм нахождения ориентированной площади многоугольника
Пусть даны вершина N-угольника в порядке обхода.
Заведём переменную res, изначально равную нулю.
Переберём все вершины. На каждом шаге будем рассматривать ребро между вершинами i и i+1 прибавлять к результату удвоенную площадь трапеции, образуемой данным ребром, нормалями к оси Х и самой осью: res += (pi+1.x - pi.x) * (pi+1.y + pi.y).
В конце возьмём результат по модулю и разделим пополам, т.к. изначально суммировали удвоенную площадь. Это делается для увеличения точности подсчётов. Если координаты точек даны целыми числами, то до последнего шага вычисления можно проводить не прибегая к вещественным числам.

Алгоритм нахождения ориентированной площади многоугольника
Y
X
1
2
3
4
5
6
7
8
9

Уравнение прямой
Каноническое уравнение прямой имеет вид a*x + b*y + c = 0.
Пусть известны коэффициенты уравнения задающего прямую, и нужно найти точку и направляющий вектор для описания этой прямой.
Y
X
p
v
v.x
v.y
v
Рассмотрим прямую, параллельную заданной и проходящую через начало координат.
Она имеет такой же направляющий вектор v и коэффициент c = 0.
Получаем, что a*v.x + b*v.y = 0
Откуда v.x = b и v.y = -a
Если прямая не вертикальная (b != 0), то в качестве p.x возьмём 0, тогда уравнение прямой принимает вид b*p.y + c = 0, откуда p.y = -c/b.
Иначе возьмём 0 в качестве p.y, тогда
p.x = -c/a

Уравнение прямой 2
Пусть известна точка p и направляющий вектор v, задающие прямую. Требуется найти коэффициенты канонического уравнения для этой прямой.
Y
X
p
v
v.x
v.y
Подставим в уравнение
a*x + b*y + c = 0 коэффициенты a, b и координаты p, получим:
-v.y*p.x + v.x*p.y + c = 0, откуда
с = p.x*v.y - p.y*v.x = p.ToVector() ^ v
v
Рассмотрим прямую, параллельную заданной и проходящую через начало координат.
Она имеет такой же направляющий вектор v и коэффициент c = 0.
Получаем, что a*v.x + b*v.y = 0
Откуда a = -v.y и b = v.x