Вычислительная геометрия ( англ. computational geometry ) - отрасль компьютерных наук посвящена изучению алгоритмов что описуюються в терминах геометрии.
Основным стимулом развития вычислительной геометрии как дисциплины был прогресс в компьютерной графике и системах автоматизированного проектирования и автоматизированных систем технологической подготовки производства, однако многие задачи вычислительной геометрии является классическим по своей природе, и могут появляться при математической визуализации.
Другим важным применением вычислительной геометрии является робототехника (планирование движения и задачи распознавания образов ), геоинформационные системы(геометрический поиск, планирование маршрута), дизайн микросхем, программирование станков с числовым программным управлением.
Основными разделами вычислительной геометрии являются:
Комбинаторная вычислительная геометрия, или также названа алгоритмическая геометрия, которая рассматривает геометрические объекты как дискретные сущности. Основополагающей книгой по этой теме является книга Препараты и Шеймоса, в которой впервые в 1975 был использован термин "вычислительная геометрия".
Численное вычислительная геометрия, также названа машинная геометрия или геометрическое моделирование, которая имеет дело в основном с представлением объектов реального мира в форме пригодной для дальнейшей компьютерной обработки. Этот раздел можно рассматривать как дальнейшее развитие начертательной геометрии и часто рассматривается как раздел компьютерной графики. Термин "вычислительная геометрия" в таком смысле употреблялся с 1971.
Комбинаторная вычислительная геометрия
Основной целью исследований в комбинаторной вычислительной геометрии является разработка эффективных алгоритмов и структур данных для решения задач которые заданы в терминах базовых геометрических объектов: точек, отрезков, многоугольников, многогранников, и других.
Некоторые из этих задач выглядят такими простыми, что они вообще не рассматривались как задачи до момента изобретения компьютеров. Рассмотрим например задачу поиска ближайшей пары точек :
Имея n точек на плоскости, найти две расстояние между которыми наименьшее
Можно вычислить расстояния между каждой парой точек, (их n (n-1) / 2 ), затем выбрать пару с наименьшим расстоянием. Такой полный перебор имеет сложность O ( n 2 ) есть время его выполнения пропорционально квадрату числа точек. Классическим результатом в вычислительной геометрии был алгоритм со сложностью O ( N Log N ). Также открыты рандомизированные алгоритмы, работающие за O ( n ) шагов, и детерминированные алгоритмы работающие за O ( N Log Log N ).
Вычислительная геометрия главным образом сосредотачивается на вычислительной сложности, так как алгоритмы предназначены для работы над очень большими наборами данных, из десятков или сотен миллионов точек. Для больших наборов данных разница между O ( n 2 ) и O ( N Log N ) может быть такой же, как разница между днями и секундами.
Классы задач
Основные задачи вычислительной геометрии можно классифицировать различными способами, и с различными критериями. Различают следующие классы:
Статические задачи
В задачах этой категории на вход подаются определенные данные, и за ними алгоритм должен вычислить соответствующие результаты. Примерами фундаментальных задач такого рода являются:
Выпуклая оболочка: Имея набор точек, найти наименьший выпуклый многоугольник содержащий все точки.
Пересечение отрезков: найти все сечения в наборе отрезков.
Триангуляция Делоне
Диаграмма Вороного: Имея набор точек, разделить пространство на сектора, каждая точка из которых ближе к своей из набора, чем к другим.
Линейное программирование
Задача ближайшей пары точек: Имея набор точек найти две расстояние между которыми наименьшее.
Евклидово кратчайший путь: Соединить две точки евклидова пространства (с полигональными препятствиями) кратчайшим образом.
Триангуляция многоугольника: Имея многоугольник, разбить его внутренность на треугольники
Генерация Меша англ. Mesh generation
Вычислительная сложность для этого типа задач оценивается по времени и пространства (размера памяти), которые необходимы для решения конкретной задачи.
Задачи геометрического поиска (запросу)
В задачах геометрического поиска входные данные состоят из двух частей: пространство поиска и запроса, которые различаются в разных видах задач. Обычно пространство поиска требует предварительной обработки, для обеспечения эффективного выполнения нескольких запросов.
Примеры задач геометрического поиска:
Региональный поиск ( en: Range searching ): Обработать набор точек, с целью эффективного поиска набора точек содержащейся в запрошенному регионе.
Локализация точки ( en: Point location ): Имея разбиения пространства на регионы, создать структуру данных что позволит эффективно определить в каком регионе находится данная точка.
Поиск ближайшего соседа : Обработать набор точек доступа ко всем возможностям эффективно найти какие точки ближе к запрошенной.
Трассировка лучей : Имея набор объектов в пространстве, создать структуру данных, которая позволит эффективно определять какие объекты персикае востребован луч.
Если пространство поиска фиксированный, вычислительная сложность задач обычно определяется
время и место необходимыми для предварительной обработки (построения эффективной структуры данных)
время (возможно редко месту) нужными для получения ответа на каждый запрос.
В случаях когда пространство поиска может варьироваться смотрите раздел "Динамические задачи".
Динамические задачи
Динамические задачи - это тип задач входные данные в которые постепенно изменяются (например добавляются или удаляются объекты). Алгоритмы решения таких задач включают в себя поддержку динамических структур данных. Любую задачу вычислительной геометрии можно решать динамично, но за счет дополнительных вычислительных ресурсов. Региональный поиск или построение опуколои оболочки можно проводить над множеством точек, которые изменяются.
Вычислительная сложность для этого класса задач задается такими параметрами:
ресурсами необходимыми для построения структуры данных для поиска
ресурсами необходимыми для модификации построенной структуры
и ресурсами необходимыми для ответа на запросы
Некоторые задачи могут рассматриваться как принадлежащие нескольким категориям в зависимости от контекста.
Например, рассмотрим следующие задачи:
Принадлежность точки многоугольнике: Определить точка находится снаружи или внутри данного многоугольника.
Вариации
Во многих программах эта задача рассматривается как задача первого класса. Тем не менее, во многих случаях нужно определить курсор мыши лежит внутри данного многоугольника. Курсор постоянно перемещается, а многоугольник не меняется. Аналогично можно проверять определенный летательный аппарат который показан на экране радара не пересек границу страны. Такие задачи можно считать задачами геометрического запроса. А в CAD-системах сам многокунтик может варьироваться, поэтому задача может считаться динамичной.