Rambler's Top100 Наука Технологии  

Методы решения задач в геометрических ограничениях в трехмерном геометрическом решателе.

 
Введение

Формальная постановка задачи

Методы решения

Ссылки


Выделяют несколько методов решения задач в геометрических ограничениях:
  • Численный
  • Основанный на правилах
  • Декомпозиционный

    В решателях, применяющих сугубо численный подход, геометрические ограничения переводятся в алгебраические (обычно это полиномиальные уравнения), и полученная система решается некоторым набором численных методов, как правило, итеративных. Одним из часто используемых методов является метод Ньютона, который привлекает своей относительной простотой и высокой скоростью сходимости, однако требует хороших начальных приближений, не гарантирует сходимость к решению и не так быстр в многомерном случае. Все большую и большую популярность завоевывает метод гомотопии, который, по сравнению с методом Ньютона, ведет себя более регулярно, с высокой вероятностью сходясь к ближайшему относительно начального приближения решению, однако является более сложным в реализации. Так же используются методы релаксации, метод проекций, и многие другие общие и специализированные методы. Особое место занимают методы программирования в ограничениях, позволяющие работать с недифференцируемыми и разрывными пользовательскими ограничениями, однако их вычислительная эффективность низка. В целом, численные методы хороши тем, что позволяют решать переопределенные, но совместные, а также недоопределенные задачи, но плохи тем, что имеют высокую вычислительную сложность, и тем, что изменение параметров модели ведет к полному пересчету модели.

    При реализации подхода, основанного на правилах, ограничения рассматриваются как известные факты, из которых можно выводить факты-следствия по заранее заданным, “вшитым в решатель” правилам. База фактов, таким образом, постепенно пополняется, в результате мы получаем факты, которые задают координаты объектам, определяя тем самым решение задачи. Есть и другие известные методы, и их варианты, например, метод резолюций, основанные на этом подходе, однако современные решатели, как правило, не используют подход на основе правил.

    Третий, и наиболее интересный подход заключается в декомпозиции задачи на дерево подзадач, решать которые можно последовательно. Решатели, основанные на таком подходе, позволяют локализовать вносимые в модель изменения, и не выполнять при них полный пересчет. Более того, перенося часть вычислительной сложности из численных методов в символьные, имеющие, как правило, полиномиальную сложность, мы существенно сокращаем сложность вычислений. С помощью таких решателей проще выполнять и поиск всех решений задачи. Наиболее известны три группы исследователей, работающих в этом направлении – это группа Хоффмана, группа Клеманна и группа Оуэна. К сожалению, как группа Клеманна (применяющая для разрешения геометрических моделей групповой анализ на группах возможных перемещений геометрических объектов), так и группа Оуэна (применяющая процесс декомпозиции модели сверху-вниз с помощью выделения в графе объектов и ограничений трехсвязных компонент) работают в рамках коммерческих проектов и имеют сравнительно мало публикаций. Потому наиболее известен подход профессора Хоффмана, так называемый формальный анализ степеней свобод, позволяющий выделать в модели внутренне определенные части при обработке ее снизу-вверх (у него есть и публикации по декомпозиции сверху-вниз).



  • Hosted by uCoz
    Rambler's Top100 TopCTO Наука Технологии Данный сайт создан казахстанцем, ныне студентом ФИТ НГУ, Кучерявым К.С.