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

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

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

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

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

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

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

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

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

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

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

Видимость

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

Другой

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