Системы координат Введение в вычислительную геометрию. Системы координат.
	Структуры геометрических данных, основные операции Грамотная и безглючная реализация на С++ классов 'Точка', 'Многоугольник', 'Ребро/Линия' с подробными объяснениями и основными операциями.
	Уравнения различных фигур и их составление по разным данным Окружность по трем точкам, уравнение плоскости и т.п.
	Построение выпуклой оболочки конечного множества точек Среди множества произвольных точек выделяем образующие выпуклый многогранник, в котором лежат все остальные.
	Нахождение пересечения и объединения геометрических объектов Отрезки, прямые, окружности и т.п. Установка количества точек пересечения и их координат...
	Принадлежит или не принадлежит? Плоскости, многоугольнику, прямой....
	Нахождение расстояния между различными объектами Точкой, прямой, отрезком....
	Работа с многоугольниками Алгоритмы, не рассмотренные ранее и решающие специфические задачи с многоугольниками на плоскости в целом, а не с их точками/линиями.
	Разное Многие алгоритмы не так-то просто классифицировать. Поэтому они здесь.

Триангуляция Делоне

• Пусть задано множество A точек на плоскости
• Для каждой точки определена высота f(p)
• Как наиболее естественно аппроксимировать высоты точек не из A ?

Такая задача возникает, например, при построении графиков функций, генерации сложных ландшафтов.

Возможное решение этой проблемы состоит в дискретизации: для всех точек не из A пусть f(p) равняется высоте ближайшей точки из A. Получится нечто вроде нарисованного ниже.

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

Формальное определение триангуляции: планарный граф, получающийся при соединении точек A отрезками, такой, что нельзя добавить ни одного нового отрезка без нарушения планарности (т.е без пересечения отрезками друг друга). При этом граница триангуляции будет, очевидно, выпуклой оболочкой множества A.

Одно и то же множество можно триангулировать разными способами. Рассмотрим углы в получающихся треугольниках. Выберем минимальный угол. Триангуляция дает тем лучшую аппроксимацию, чем больше ее минимальный угол, при этом формируемые треугольники 'стремятся к равноугольности'. Особенно важна максимизация минимального угла в задачах вычислительной математики, когда точность производимых вычислений очень сильно зависит от размера минимального угла триангуляции графика. Наилучшей в этом смысле триангуляцией является триангуляция Делоне.

Простейшим способом ее построения является инкрементальный алгоритм, работающий за O(n²) операций. Реализация из соответствующей статьи не поддерживает вырожденные случаи, когда 4 точки из множества лежат на одной окружности: в этом случае триангуляция Делоне не уникальна, их несколько, но минимальные углы этих триангуляций равны.

Иногда даже минимальный угол триангуляции Делоне оказывается слишком малым для устойчивой работы использующего ее алгоритма. Тогда ее можно улучшить, используя метод Раперта. При этом будут добавлены новые вершины триангуляции и образованы дополнительные треугольники, но их количество невелико, а стабильность алгоритма (метода конечных элементов, например) может возрасти многократно за счет появления нижней границы для углов. Метод описан в оригинальной статье^zip. Для его практической реализации также весьма интересны комментарии Максима Щербакова. Существуют и другие методы аналогичного улучшения триангуляции, но они дают худшие результаты.

Много различных алгоритмов построения триангуляции Делоне описываются и сравниваются в статье А. В. Скворцова^zip.

Обычно рассматривают триангуляцию на плоскости, однако триангуляция Делоне аналогично определяется и для n-мерного пространства.

Диаграмма Вороного

Рассмотрим следующую задачу: есть почтовые службы p_i, мы хотим знать, какую область плоскости обслуживает каждая. При этом каждую точку q обслуживает та служба, которая ближе. Ответ на этот и ряд других вопросов, связанных с близостью на плоскости, дает диаграмма Вороного.

Диаграмма Вороного изображена на рисунке выше. Она состоит из вершин(v) диаграммы и ее сторон(e). Формальное определение:

• Пусть P - множество из n различных точек плоскости
• Диаграмма Вороного - деление плоскости на n ячеек, по одной на каждую точку P
• Точка q принадлежит ячейке, относящейся к p_i из P, если расстояние от q до p_i меньше, чем расстояние от q до любой другой точки P.

Можно провести очень интересную аналогию из области кристаллографии. Предположим, что точки представляются в виде зерен кристалла, которые растут с постоянной скоростью во всех направлениях. Предположим также, что рост зерен кристалла продолжается до тех пор, пока два или более зерен не встретятся. Через некоторое достаточное время каждое выросшее зерно будет представлено в виде ячейки диаграммы Вороного для своего ядра(вполне очевидно, что рост крайних неограниченных областей может продолжаться бесконечно). В результате будет получена диаграмма Вороного для множества P.

Весьма забавно представить более быстрый процесс роста в одном из направлений и при расположении ядер в фиксированных точках в пространстве. Полученная в результате диаграмма Вороного в трехмерном пространстве будет состоять из ограниченных и неограниченных полиэдральных областей.

Диаграмма Вороного аналогично определяется для n-мерного пространства. Алгоритм построения диаграммы Вороного описан в англоязычной статье.

Связь между диаграммой Вороного и триангуляцией Делоне

Эти две конструкции двойственны. То есть из одной можно просто получить другую. Вообще говоря, диаграмма Вороного уникальна для данного набора точек, а триангуляция Делоне - не всегда. Однако, если есть несколько триангуляций, то они эквивалентны в том смысле, что их минимальные углы равны.

Так что можно говорить об однозначном соответствии между диаграммой Вороного и триангуляциями Делоне. Посмотрим, например, как из диаграммы получается триангуляция.

1. Если две точки p_i и p_j из P имеют общее ребро диаграммы(их ячейки смежные), провести дугу между p_i и p_j. Получится граф Делоне, обозначенный на первом рисунке буквой G
2. Затем натягиваем дуги, превращая в отрезки.

Таким образом, триангуляция получается соединением всех смежных точек P отрезками. Единственная проблема: четыре или более точек в графе Делоне могут лежать на одной окружности.

Такие точки образуют выпуклые полигоны, которые триангулируются добавлением произвольных непересекающихся диагоналей. Тогда триангуляция будет окончательной. Можно сказать, что триангуляция Делоне получается из графа Делоне добавлением 0 или более ребер.

Связь выпуклой оболочки с триангуляцией Делоне и диаграммой Вороного

N-мерная триангуляция Делоне и диаграмма Вороного могут быть получены путем вычисления N+1-мерной выпуклой оболочки. Процесс довольно простой, но выходит за рамки общего раздела, а потому описан в отдельной статье. Там же описано и получение выпуклой оболочки на плоскости из диаграммы.

Информацию о решении конкретных задач можно также найти в разделе Олимпиадные задачи: геометрия.