Список тем комбинаторной вычислительной геометрии
Список тем комбинаторной вычислительной геометрии перечисляет темы вычислительной геометрии , в которых задачи формулируются в терминах геометрических объектов как дискретных методы их решения представляют собой в основном теории и алгоритмы комбинаторного сущностей, и, следовательно , характера.
См. «Список тем по числовой вычислительной геометрии», чтобы узнать о другой разновидности вычислительной геометрии, которая рассматривает геометрические объекты как непрерывные объекты и применяет методы и алгоритмы, характерные для природы, для численного анализа .
Строительство/представительство [ править ]
- Булевы операции над многоугольниками
- Выпуклая оболочка
- Расположение гиперплоскости
- Разложение полигонов
- с рассечением формы Проблемы
- Прямой скелет
- Проблема с колющей линией
- Триангуляция
- Диаграмма Вороного
Экстремальные формы [ править ]
- Минимальная ограничивающая рамка ( Наименьшая ограничивающая рамка , Наименьшая ограничивающая рамка )
- 2-D случай: наименьший ограничивающий прямоугольник ( наименьший охватывающий прямоугольник )
- Есть два распространенных варианта этой проблемы.
- Во многих областях компьютерной графики под ограничивающей рамкой (часто сокращенно bbox) понимают наименьшую рамку, ограниченную сторонами, параллельными осям координат, которая ограничивает рассматриваемые объекты.
- В других приложениях, таких как упаковка , проблема состоит в том, чтобы найти наименьшую коробку, в которую может поместиться объект (или объекты) («упакованный»). Здесь коробка может принимать произвольную ориентацию относительно «упакованных» объектов.
- Наименьшая ограничивающая сфера (Наименьшая охватывающая сфера)
- 2-D случай: наименьший ограничивающий круг
- Самый большой пустой прямоугольник ( Максимальный пустой прямоугольник )
- Самая большая пустая сфера
- 2-D случай: Максимальный пустой круг ( самый большой пустой круг )
Взаимодействие/поиск [ править ]
- Обнаружение столкновений
- Пересечение сегментов линии
- Местоположение точки
- Пересечение многоугольников
- Поиск диапазона
- Приведение лучей (не путать с трассировкой лучей компьютерной графики)
- Плитный метод
Проблемы с близостью [ править ]
- Ближайшая пара точек
- Проблема с ближайшей точкой
- Диаметр набора точек
- Триангуляция Делоне
- Диаграмма Вороного
Видимость [ править ]
- Видимость (геометрия)
- Проблема художественной галереи ( Проблема музея )
- График видимости
- Проблема с маршрутом сторожа
- Приложения компьютерной графики:
- Приведение лучей (не путать с трассировкой лучей компьютерной графики)
Другое [ править ]
- Проблема со счастливым концом
- Проблема с сэндвичем с ветчиной
- со сборкой формы проблемы
- с совпадением форм проблемы
- Проблема меры Клее
- Задачи об изотетических многоугольниках и изотетических многогранниках
- Планирование пути
- Полигональное сдерживание
- Надежные геометрические вычисления с фиксированной точностью решают две основные проблемы: представление действительных чисел в компьютерах и возможное геометрическое вырождение (математика) входных данных.