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

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

Сложность вычислений занимает центральное место в вычислительной геометрии и имеет большое практическое значение, если алгоритмы используются с очень большими наборами данных, содержащими десятки или сотни миллионов точек. Для таких наборов разница между 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 т и Информатика
Note: This template roughly follows the 2012 ACM Computing Classification System.
Hardware	Printed circuit board Peripheral Integrated circuit Very Large Scale Integration Systems on Chip (SoCs) Energy consumption (Green computing) Electronic design automation Hardware acceleration Processor Size / Form
Computer systems organization	Computer architecture Computational complexity Dependability Embedded system Real-time computing
Networks	Network architecture Network protocol Network components Network scheduler Network performance evaluation Network service
Software organization	Interpreter Middleware Virtual machine Operating system Software quality
Software notations and tools	Programming paradigm Programming language Compiler Domain-specific language Modeling language Software framework Integrated development environment Software configuration management Software library Software repository
Software development	Control variable Software development process Requirements analysis Software design Software construction Software deployment Software engineering Software maintenance Programming team Open-source model
Theory of computation	Model of computation Formal language Automata theory Computability theory Computational complexity theory Logic Semantics
Algorithms	Algorithm design Analysis of algorithms Algorithmic efficiency Randomized algorithm Computational geometry
Mathematics of computing	Discrete mathematics Probability Statistics Mathematical software Information theory Mathematical analysis Numerical analysis Theoretical computer science
Information systems	Database management system Information storage systems Enterprise information system Social information systems Geographic information system Decision support system Process control system Multimedia information system Data mining Digital library Computing platform Digital marketing World Wide Web Information retrieval
Security	Cryptography Formal methods Security hacker Security services Intrusion detection system Hardware security Network security Information security Application security
Human–computer interaction	Interaction design Social computing Ubiquitous computing Visualization Accessibility
Concurrency	Concurrent computing Parallel computing Distributed computing Multithreading Multiprocessing
Artificial intelligence	Natural language processing Knowledge representation and reasoning Computer vision Automated planning and scheduling Search methodology Control method Philosophy of artificial intelligence Distributed artificial intelligence
Machine learning	Supervised learning Unsupervised learning Reinforcement learning Multi-task learning Cross-validation
Graphics	Animation Rendering Photograph manipulation Graphics processing unit Mixed reality Virtual reality Image compression Solid modeling
Applied computing	Quantum Computing E-commerce Enterprise software Computational mathematics Computational physics Computational chemistry Computational biology Computational social science Computational engineering Differentiable computing Computational healthcare Digital art Electronic publishing Cyberwarfare Electronic voting Video games Word processing Operations research Educational technology Document management
Category Outline Glossaries