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

Вычислительная геометрия в раздел дискретной математики, в котором рассматриваются алгоритмы для решения геометрических задач.

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

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

[править] Виды многоугольников (полигонов)

Многоугольник - замкнутая кривая на плоскости, состоящая из отрезков прямых линий. Отрезки называются сторонами многоугольника, а их концы - вершинами многоугольника.

Многоугольник называется простым, если он не пересекается сам с собой.

Многоугольник называется выпуклым, если все его внутренние углы меньше или равны 180 градусам.

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

[править] Алгоритмы

Алгоритм сканирования Грэхема в трудоёмкость $O(n \log n)$ .
Алгоритм быстрой оболочки в трудоёмкость $O(n^2)$ , $O(n log n)$ в в среднем.
Алгоритм Киркпатрика в построение выпуклой оболочки набора точек на плоскости методом «разделяй и властвуй» через мосты. Трудоёмкость $O(n \log n)$ .
Алгоритм заворачивания подарков (Джарвиса) в трудоёмкость $O(n h)$ , $h$ в количество точек в выпуклой оболочке.
Алгоритм Чана в трудоёмкость $O(n\log h)$ , $h$ в количество точек в выпуклой оболочке.
Алгоритм точки в многоугольнике в проверка принадлежности данной точки простому многоугольнику $O(n)$ .
Метод луча в принадлежность точки простому многоугольнику $O(n)$ .
Пересечение отрезков в (алгоритм Бентли-Оттманна) поиск всех точек пересечения отрезков на плоскости $O((n + k) \log n)$ , $k$ в количество точек пересечения.

[править] См. также

[править] Литература

Препарата Ф., Шеймос М. Вычислительная геометрия: Введение = Computational Geometry An introduction. в М.: Мир, 1989. в С. 478.
Ласло М. Вычислительная геометрия и компьютерная графика на C++. в М.: БИНОМ, 1997. в С. 304.
Скворцов А.В. Триангуляция Делоне и ее применение. в Томск: Издательство Томского университета, 2002. в С. 128.
Кормен, Томас Х., Лейзерсон, Чарльз И., Ривест, Рональд Л., Штайн, Клифорд. Глава 33. Вычислительная геометрия // Алгоритмы: построение и анализ = Introduction to Algorithms. в 2-e издание. в М.: «Вильямс», 2005. в ISBN 5-8459-0857-4
Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications. в Springer, 2000. в С. 368.
David M. Mount. Computional Geometry. в University of Maryland, 2002. в С. 122.
Elmar Langetepe, Gabriel Zachmann. Geometric Data Structures for Computer Graphics. в A K Peters, 2006. в С. 362. в ISBN 1568812353
Hormoz Pirzadeh. Computational Geometry with the Rotating Calipers. в McGill University, 1999. в С. 118.
Jacob E. Goodman, Joseph O'Rourke. Handbook of Discrete and Computational Geometry. в CRC Press LLC, 1997. в С. 956.
Jianer Chen. Computational Geometry: Methods and Applications. в Texas A&M University, 1996. в С. 228.
Joseph O'Rourke. Computational Geometry in C. в Cambridge University Press, 1998. в С. 362.

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

Содержание

[править] Виды многоугольников (полигонов)

[править] Алгоритмы

[править] См. также

[править] Литература

Личные инструменты

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация

Участие

Печать/экспорт

Инструменты

На других языках