Список тем комбинаторной вычислительной геометрии - List of combinatorial computational geometry topics

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

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

Строительство / представительство

• Логические операции над полигонами
• Выпуклый корпус
• Расположение гиперплоскости
• Разложение многоугольника
  • Триангуляция многоугольника
    • Минимальное выпуклое разложение
    • Задача о минимальном выпуклом покрытии ( NP-сложная )
    • Минимальное прямоугольное разложение
  • Проблемы тесселяции
• Проблемы с рассечением формы
• Прямой скелет
• Проблема с линией колющих ран
• Триангуляция
  • Триангуляция Делоне
  • Триангуляция по заданным точкам
  • Триангуляция многоугольника
• Диаграмма Вороного

Экстремальные формы

• Минимальный ограничивающий прямоугольник ( Наименьший вшита окно , Наименьший ограничивающий прямоугольник )
  • Двухмерный случай: наименьший ограничивающий прямоугольник ( наименьший охватывающий прямоугольник )
  • Есть два распространенных варианта этой проблемы.
    • Во многих областях компьютерной графики ограничивающий прямоугольник (часто сокращенно bbox) понимается как самый маленький прямоугольник, ограниченный сторонами, параллельными осям координат, которые охватывают рассматриваемые объекты.
    • В других приложениях, таких как упаковка , проблема состоит в том, чтобы найти наименьшую коробку, в которую объект (или объекты) может поместиться («упакованный»). Здесь коробка может принимать произвольную ориентацию по отношению к «упакованным» объектам.
• Наименьшая ограничивающая сфера ( Наименьшая ограничивающая сфера)
  • Двухмерный случай: наименьшая ограничивающая окружность
• Самый большой пустой прямоугольник ( Максимальный пустой прямоугольник )
• Самая большая пустая сфера
  • Двухмерный случай: Максимальный пустой круг ( самый большой пустой круг )

Взаимодействие / поиск

• Обнаружение столкновений
• Пересечение отрезка прямой
• Расположение точки
  • Точка в многоугольнике
• Пересечение многоугольника
• Поиск диапазона
  • Поиск ортогонального диапазона
  • Односторонний поиск диапазона
• Ray casting (не путать с трассировкой лучей компьютерной графики)

Проблемы с близостью

• Ближайшая пара точек
• Проблема ближайшей точки
• Диаметр точечного набора
• Триангуляция Делоне
• Диаграмма Вороного

Видимость

• Видимость (геометрия)
• Проблема картинной галереи ( Проблема музея )
• График видимости
• Проблема маршрута сторожа
• Приложения для компьютерной графики:
  • Определение скрытой поверхности
  • Удаление скрытой линии
• Ray casting (не путать с трассировкой лучей компьютерной графики)

Другой

• Проблема с счастливым концом
• Проблема бутерброда с ветчиной
• проблемы сборки формы
• проблемы соответствия формы
• Клее проблема меры
• Задачи об изотетических многоугольниках и изотетических многогранниках
  • Ортогональная выпуклая оболочка
• Планирование пути
  • Пути среди препятствий
  • Кратчайший путь в многоугольнике
• Сдерживание многоугольника
• Надежные геометрические вычисления решают две основные проблемы: представление действительных чисел с фиксированной точностью на компьютерах и возможное геометрическое вырождение (математика) входных данных.