Вычислительная геометрия

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

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

Основным толчком к развитию вычислительной геометрии как дисциплины стал прогресс в области компьютерной графики и систем автоматизированного проектирования и производства ( CAD / CAM ), однако многие задачи вычислительной геометрии носят классический характер и могут возникнуть в результате математической визуализации .

Другие важные применения вычислительной геометрии включают робототехнику ( планирования движения проблемы и видимости), географические информационные системы (ГИС) (геометрическое местоположение и поиск, планирование маршрута), проектирование интегральных схем (проектирование и проверка геометрии ИС), автоматизированное проектирование (CAE). (генерация сетки) и компьютерное зрение ( 3D-реконструкция ).

Основными разделами вычислительной геометрии являются:

Комбинаторная вычислительная геометрия , также называемая алгоритмической геометрией , рассматривает геометрические объекты как дискретные сущности. В основополагающей книге Препараты и Шамоса по этой теме первое использование термина «вычислительная геометрия» в этом смысле датируется 1975 годом. ^{[ 1 ]}
Численная вычислительная геометрия , также называемая машинной геометрией , компьютерным геометрическим проектированием (CAGD) или геометрическим моделированием , которая занимается в первую очередь представлением объектов реального мира в формах, подходящих для компьютерных вычислений в системах CAD/CAM. Эту ветвь можно рассматривать как дальнейшее развитие начертательной геометрии и часто считают ветвью компьютерной графики или САПР. Термин «вычислительная геометрия» в этом значении используется с 1971 года. ^{[ 2 ]}

Хотя большинство алгоритмов вычислительной геометрии были разработаны (и разрабатываются) для электронных компьютеров, некоторые алгоритмы были разработаны для нетрадиционных компьютеров (например, оптических компьютеров). ^{[ 3 ]})

Комбинаторная вычислительная геометрия

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

Некоторые из этих проблем кажутся настолько простыми, что их вообще не считали проблемами до появления компьютеров . Рассмотрим, например, задачу о ближайшей паре :

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

Можно вычислить расстояния между всеми парами точек, которых имеется n(n-1)/2 , а затем выбрать пару с наименьшим расстоянием. Этот алгоритм грубой силы требует O ( n ²) время; т.е. время его выполнения пропорционально квадрату количества точек. Классическим результатом в вычислительной геометрии была формулировка алгоритма, который принимает O( n log n ). Рандомизированные алгоритмы , требующие ожидаемого времени O( n ), ^{[ 4 ]} а также детерминированный алгоритм, который занимает время O( n log log n ), ^{[ 5 ]} также были обнаружены.

Проблемные классы

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

Статическая проблема

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

Выпуклая оболочка : по заданному набору точек найдите наименьший выпуклый многогранник/многоугольник, содержащий все точки.
Пересечение сегментов линий : найдите пересечения между заданным набором сегментов линий.
Триангуляция Делоне
Диаграмма Вороного : Учитывая набор точек, разделите пространство в соответствии с тем, какие точки находятся ближе всего к заданным точкам.
Линейное программирование
Ближайшая пара точек : Учитывая набор точек, найдите две точки, находящиеся на наименьшем расстоянии друг от друга.
Самая дальняя пара точек
Самый большой пустой круг : по набору точек найдите самый большой круг, центр которого находится внутри выпуклой оболочки и не заключает ни одну из них.
Евклидов кратчайший путь : соедините две точки в евклидовом пространстве (с многогранными препятствиями) кратчайшим путем.
Триангуляция многоугольника : учитывая многоугольник, разделите его внутреннюю часть на треугольники.
Генерация сетки
Булевы операции над многоугольниками

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

Проблемы с геометрическими запросами

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

Некоторые фундаментальные проблемы геометрических запросов:

Поиск по диапазону . Предварительная обработка набора точек для эффективного подсчета количества точек внутри области запроса.
Проблема с расположением точки . Учитывая разделение пространства на ячейки, создайте структуру данных, которая эффективно сообщает, в какой ячейке находится точка запроса.
Ближайший сосед : Предварительная обработка набора точек, чтобы эффективно найти точку, ближайшую к точке запроса.
Трассировка лучей . Учитывая набор объектов в пространстве, создайте структуру данных, которая эффективно сообщает, какой объект первым пересекает луч запроса.

Если пространство поиска фиксировано, вычислительная сложность для этого класса задач обычно оценивается как:

время и пространство, необходимые для создания структуры данных, в которой будет осуществляться поиск.
время (а иногда и дополнительное место) для ответов на вопросы.

О случае, когда пространство поиска может меняться, см. « Динамические задачи ».

Динамические проблемы

Еще одним крупным классом являются динамические задачи , цель которых — найти эффективный алгоритм многократного поиска решения после каждого постепенного изменения входных данных (добавления или удаления входных геометрических элементов). Алгоритмы решения задач этого типа обычно включают динамические структуры данных . Любую вычислительную геометрическую задачу можно преобразовать в динамическую за счет увеличения времени обработки. Например, задача поиска диапазона может быть преобразована в задачу поиска динамического диапазона путем обеспечения добавления и/или удаления точек. Проблема динамической выпуклой оболочки состоит в том, чтобы отслеживать выпуклую оболочку, например, для динамически изменяющегося набора точек, т. е. во время вставки или удаления входных точек.

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

время и пространство, необходимые для создания структуры данных, в которой будет осуществляться поиск.
время и пространство для изменения искомой структуры данных после постепенного изменения в пространстве поиска
время (а иногда и дополнительное пространство) для ответа на запрос.

Вариации

Некоторые проблемы можно отнести к любой из категорий, в зависимости от контекста. Например, рассмотрим следующую проблему.

Точка в многоугольнике : решите, находится ли точка внутри или снаружи данного многоугольника.

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

В некоторых контекстах задач запросов существуют разумные ожидания относительно последовательности запросов, которые можно использовать либо для эффективных структур данных, либо для более точных оценок сложности вычислений. Например, в некоторых случаях важно знать наихудший случай общего времени для всей последовательности из N запросов, а не для одного запроса. См. также « амортизированный анализ ».

Численная вычислительная геометрия

Эта отрасль также известна как геометрическое моделирование и компьютерное геометрическое проектирование (CAGD).

Основными проблемами являются моделирование и представление кривых и поверхностей.

Наиболее важными инструментами здесь являются параметрические кривые и параметрические поверхности , такие как кривые Безье , сплайновые кривые и поверхности. Важным непараметрическим подходом является метод набора уровней .

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

Список алгоритмов

Задача о ближайшей паре : найти пару точек (из набора точек) с наименьшим расстоянием между ними.
Алгоритмы обнаружения столкновений : проверка столкновения или пересечения двух заданных твердых тел.
Алгоритм конуса : определение точек поверхности
Алгоритмы выпуклой оболочки определение выпуклой оболочки набора точек :
- сканирование Грэма
- Квикхалл
- Алгоритм упаковки подарков или Марш Джарвиса
- Алгоритм Чана
- Алгоритм Киркпатрика – Зейделя
Преобразование евклидова расстояния : вычисляет расстояние между каждой точкой сетки и дискретным набором точек.
Геометрическое хеширование : метод эффективного поиска двумерных объектов, представленных дискретными точками, подвергшимися аффинному преобразованию.
Алгоритм расстояния Гилберта – Джонсона – Кирти : определение наименьшего расстояния между двумя выпуклыми формами.
Алгоритм Jump-and-Walk : алгоритм определения местоположения точек в триангуляциях.
Сглаживание по Лапласу : алгоритм сглаживания полигональной сетки.
Пересечение сегментов линий : определение того, пересекаются ли линии, обычно с помощью алгоритма развертки линии.
- Алгоритм Бентли – Оттмана
- Алгоритм Шамоса – Хоуи
Алгоритмы минимальной ограничивающей рамки : найдите ориентированную минимальную ограничивающую рамку, включающую набор точек.
Поиск ближайшего соседа : найдите ближайшую точку или точки к точке запроса.
Алгоритм вложения : максимально эффективно используйте материал или пространство.
Алгоритмы «Точка в полигоне» : проверяет, находится ли данная точка внутри данного многоугольника.
Алгоритмы регистрации набора точек : находит преобразование между двумя наборами точек для их оптимального выравнивания.
Вращающийся штангенциркуль : определите все противоположные пары точек и вершин на выпуклом многоугольнике или выпуклой оболочке .
Алгоритм шнурков : определение площади многоугольника, вершины которого описаны упорядоченными парами на плоскости.
Триангуляция
- Триангуляция Делоне
  - Алгоритм Руперта (также известный как уточнение Делоне): создание качественных триангуляций Делоне.
  - Второй алгоритм Чу : создание триангуляций Делоне с ограниченным качеством.
- Марширующие треугольники : восстановление двумерной геометрии поверхности из неструктурированного облака точек.
- Алгоритмы триангуляции полигона : разложение многоугольника на набор треугольников.
- Диаграммы Вороного , геометрические двойники . триангуляции Делоне
  - Алгоритм Бойера – Ватсона : создание диаграммы Вороного в любом количестве измерений.
  - Алгоритм Фортуны : создаем диаграмму Вороного
- Квазитриангуляция

См. также

Ссылки

^ Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер-Верлаг . ISBN 0-387-96131-3 . 1-е издание; 2-е издание, исправленное и дополненное, 1988 г.
^ А. Р. Форрест, «Вычислительная геометрия», Proc. Королевское общество Лондона , 321, серия 4, 187–195 (1971)
^ Евгений Борисович Карасик (2019). Оптическая вычислительная геометрия . ISBN 979-8511243344 .
^ С. Хуллер и Ю. Матиас. Простой алгоритм рандомизированного сита для решения задачи поиска ближайшей пары . Инф. Comput., 118(1):34—37,1995 ( PDF )
^ С. Форчун и Дж. Э. Хопкрофт. «Заметка об алгоритме ближайшего соседа Рабина». Письма об обработке информации, 8 (1), стр. 20–23, 1979 г.

Дальнейшее чтение

Список книг по вычислительной геометрии

Журналы

Комбинаторная/алгоритмическая вычислительная геометрия

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

Внешние ссылки

Послушайте эту статью ( 9 минут )

Этот аудиофайл был создан на основе редакции этой статьи от 17 сентября 2013 г. и не отражает последующие изменения.

[PS-1] Франко П. Препарата и Майкл Ян Шамос (1985). Вычислительная геометрия. Введение . Спрингер-Верлаг . ISBN 0-387-96131-3 . 1-е издание; 2-е издание, исправленное и дополненное, 1988 г.

[2] А. Р. Форрест, «Вычислительная геометрия», Proc. Королевское общество Лондона , 321, серия 4, 187–195 (1971)

[YK-3] Евгений Борисович Карасик (2019). Оптическая вычислительная геометрия . ISBN 979-8511243344 .

[4] С. Хуллер и Ю. Матиас. Простой алгоритм рандомизированного сита для решения задачи поиска ближайшей пары . Инф. Comput., 118(1):34—37,1995 ( PDF )

[5] С. Форчун и Дж. Э. Хопкрофт. «Заметка об алгоритме ближайшего соседа Рабина». Письма об обработке информации, 8 (1), стр. 20–23, 1979 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

v т и Информатика
Примечание. Этот шаблон примерно соответствует Системе классификации вычислений ACM 2012 года .
Аппаратное обеспечение	Печатная плата Периферийное устройство Интегральная схема Очень крупномасштабная интеграция Системы на кристалле (SoC) Потребление энергии (зеленые вычисления) Автоматизация электронного проектирования Аппаратное ускорение Процессор Размер / Форма
Организация компьютерных систем	Компьютерная архитектура Вычислительная сложность Надежность Встроенная система Вычисления в реальном времени
Сети	Сетевая архитектура Сетевой протокол Сетевые компоненты Сетевой планировщик Оценка производительности сети Сетевой сервис
Организация программного обеспечения	Устный переводчик Промежуточное ПО Виртуальная машина Операционная система Качество программного обеспечения
Обозначения и инструменты программного обеспечения	Парадигма программирования Язык программирования Компилятор Язык, специфичный для предметной области Язык моделирования Программная среда Интегрированная среда разработки Управление конфигурацией программного обеспечения Библиотека программного обеспечения Репозиторий программного обеспечения
Разработка программного обеспечения	Управляющая переменная Процесс разработки программного обеспечения Анализ требований Разработка программного обеспечения Создание программного обеспечения Развертывание программного обеспечения Программная инженерия Обслуживание программного обеспечения Команда программистов Модель с открытым исходным кодом
Теория вычислений	Модель вычислений Официальный язык Теория автоматов Теория вычислимости Теория сложности вычислений Логика Семантика
Алгоритмы	Разработка алгоритма Анализ алгоритмов Алгоритмическая эффективность Рандомизированный алгоритм Вычислительная геометрия
Математика вычислений	Дискретная математика Вероятность Статистика Математическое программное обеспечение Теория информации Математический анализ Численный анализ Теоретическая информатика
Информационные системы	Система управления базой данных Системы хранения информации Информационная система предприятия Социальные информационные системы Геоинформационная система Система поддержки принятия решений Система управления технологическими процессами Мультимедийная информационная система Интеллектуальный анализ данных Электронная библиотека Вычислительная платформа Цифровой маркетинг Всемирная паутина Поиск информации
Безопасность	Криптография Формальные методы Хакер безопасности Услуги безопасности Система обнаружения вторжений Аппаратная безопасность Сетевая безопасность Информационная безопасность Безопасность приложений
Взаимодействие человека и компьютера	Дизайн взаимодействия Социальные вычисления Повсеместные вычисления Визуализация Доступность
Параллелизм	Параллельные вычисления Параллельные вычисления Распределенные вычисления Многопоточность Многопроцессорность
Искусственный интеллект	Обработка естественного языка Представление знаний и рассуждения Компьютерное зрение Автоматизированное планирование и составление графиков Методика поиска Метод управления Философия искусственного интеллекта Распределенный искусственный интеллект
Машинное обучение	Обучение под присмотром Обучение без присмотра Обучение с подкреплением Многозадачное обучение Перекрестная проверка
Графика	Анимация Рендеринг Манипулирование фотографиями Графический процессор Смешанная реальность Виртуальная реальность Сжатие изображения Твердотельное моделирование
Прикладные вычисления	Квантовые вычисления Электронная коммерция Корпоративное программное обеспечение Вычислительная математика Вычислительная физика Вычислительная химия Вычислительная биология Вычислительная социальная наука Вычислительная инженерия Дифференцируемые вычисления Вычислительное здравоохранение Цифровое искусство Электронное издание Кибервойна Электронное голосование Видеоигры Обработка текста Исследование операций Образовательные технологии Управление документами
Категория Контур Глоссарии