Итак, что же такое вычислительная геометрия? Это область компьютерных наук и геометрии, которая часто используется для описания алгоритмов манипулирования кривыми и поверхностями в твердотельном моделировании.
Проще говоря, это подраздел теории алгоритмов, который включает в себя разработку и анализ эффективных алгоритмов для задач, связанных с геометрическим вводом и выводом. Он отлично подходит для компьютерной графики, планирования движения роботов и многих других подобных областей.
Некоторые известные проблемы: -
- Проблема кратчайшего пути
Вам дан набор многоугольных препятствий на плоскости, и вы хотите найти кратчайший путь от начальной позиции до целевой позиции, избегая этих препятствий.
Эта проблема легко сводится к преобразованию пространства в граф видимости и запуску алгоритма Дейкстры для поиска кратчайшего пути. Запуск этого алгоритма на реальном роботе будет ужасающим. Удары, отскок, уклонение - вам будет весело с ботом. Конечно, но это указывает на необходимость в более совершенном неоптимальном алгоритме, который поможет удовлетворить некоторые ограничения, такие как поддержание определенного расстояния от препятствий, минимальное количество поворотов, из них. Добро пожаловать в мир алгоритмов видимости!
2. проблема галереи классического искусства
Какое количество охранников, которых я могу разместить, будет достаточно, чтобы увидеть интерьер комнаты художественной галереи?
На конференции в 1976 году В. Клее впервые поставил проблему художественной галереи.
Chav ́atal показал, что для простого многоугольника n / 3 стационарных охранников
всегда достаточно, а иногда необходимо, чтобы видеть или охранять весь многоугольник.
Теперь давайте сделаем несколько отверстий в многоугольнике (часть внутри многоугольника, которая не позволяет нашим охранникам видеть сквозь них).
Задача минимального ограждения - найти минимальное количество ограждений для защиты многоугольника с отверстиями или без них. Ли и Лин доказали, что эта проблема является NP-трудной. Как кажущиеся простыми повседневные жизненные проблемы могут оказаться такими трудными!
Что вам следует знать: (алгоритмы и ресурсы)
Я дам обзор некоторых основных алгоритмов и некоторых полезных ресурсов для начала:
Обновите свою геометрию
Если вы новичок в геометрии или пересматриваете ее спустя долгое время, я предлагаю вам прочитать первую главу из Вычислительной геометрии текста О’Рурка на языке Си.
Триангуляция и разбиение
Разделение большой геометрической структуры на смежные более мелкие структуры, с которыми мы можем легко справиться, очень распространено в этих геометрических алгоритмах. Самый простой объект, который мы можем иметь на плоской двумерной фигуре, - это треугольник.
Оказывается, триангуляция многоугольника помогает решить массу задач в области вычислительной геометрии. Эта проблема была в центре внимания этой темы в течение многих лет. Существуют очень простые алгоритмы O (nlogn) для решения этой проблемы, которые были известны много лет. Давняя открытая проблема заключалась в том, существует ли алгоритм времени O (n). Проблема была решена Chazelle в 1991 году, но алгоритм настолько удивительно сложен, что он никогда не мог конкурировать с практичными, но асимптотически более медленными алгоритмами O (nlogn).
Техника Plane Sweep - еще один из наиболее распространенных методов, используемых в алгоритмах. Слайды в ссылке должны дать вам хорошее представление о том, что это такое.
O (nlogn) Triangulation Algorithm - отличный ресурс для глубокого изучения того, как работает алгоритм триангуляции. Возможно, вам понадобится время, чтобы проработать детали, так как есть много новых терминов и сложных деталей, но не волнуйтесь, вы все освоите.
Вычисление выпуклой оболочки
Выпуклая оболочка многоугольника - это минимальное выпуклое множество, охватывающее наш многоугольник.
Некоторые из интересных и хороших алгоритмов вычисления выпуклой оболочки обсуждаются ниже:
Алгоритм Грэма [O (nlogn)]
Немного об ориентациях:
Идея о том, как ориентированы точки, играет ключевую роль в понимании алгоритма Грэма, поэтому обязательно прочтите это, прежде чем возиться с алгоритмом.
Таким образом, определение того, поворачиваются ли точки p, q, r налево или направо, является простым вычислением определителя.
Алгоритм
- Найдите крайнюю левую и крайнюю правую точку в данном нам наборе точек. Мы разделим задачу поиска выпуклой оболочки на поиск верхней выпуклой оболочки и нижней выпуклой оболочки по отдельности.
2. Отсортируйте точки по возрастанию координаты x.
3. Вставьте p1 и p2 в пустую стопку W.
4. для i = 3: n:
while (W.size≥2 && Orient (pi, H [top], H [top-1] ≤0)) pop W
нажмите пи
[Обратите внимание, что перемещение верхней части корпуса от p1 к pn представляет собой последовательность поворотов вправо в каждой вершине, лежащей между ними. Это свойство используется в алгоритме.]
Алгоритм Чана улучшил временную сложность до O (nlogh), где h - количество точек в выпуклой оболочке множества Point. Очень хорошее объяснение алгоритма Чана можно найти в теме Подробнее о выпуклой оболочке здесь.
Больше алгоритмов впереди:
- Выпуклая оболочка - объяснение
- График видимости
- Планирование пути робота
- Вычисление областей Вороного
- Слабая видимость
