АЛГОРИТМЫ  И  ПРОГРАММНЫЙ  КОМПЛЕКС  ДЛЯ  ТОПОЛОГИЧЕСКОГО  АНАЛИЗА  КОМПЬЮТЕРНЫХ  МОДЕЛЕЙ

Галанин  Александр  Владимирович

аспирант,  Нижегородский  Государственный  Университет  им.  Н.И.  Лобачевского,  РФ,  г.  Нижний  Новгород

E-mail:  al@galanin.nnov.ru

ALGORITHMS  AND  SOFTWARE  SUITE  FOR  TOPOLOGICAL  ANALYSIS  OF  COMPUTER  MODELS

Galanin  Alexander

graduate  student,  Lobachevsky  State  University  of  Nizhni  Novgorod,  Russia,  Nizhy  Novgorod

АННОТАЦИЯ

Обсуждаются  алгоритмы  и  программный  комплекс,  предназначенные  для  решения  задач  вычислительной  топологии.  Основное  внимание  уделено  методам  минимизации  путей  в  заданных  классах  симплициальных  гомологий  по  модулю  2.

ABSTRACT

This  article  describes  algorithms  and  software  complex  for  solving  problems  of  computational  topology.  Basic  attention  is  given  to  path  minimization  problem  in  a  given  homology  class  of  homology  group  .

Ключевые  слова:  симплекс;  полиэдр;  группа  гомологий;  алгоритм;  минимизация;  топологический  шум.

Keywords:  simplex;  polyhedron;  homology  group;  algorithm;  minimization;  topological  noise.

Рассматриваемые  объекты

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

В  топологии  триангулированные  объекты  называются  полиэдрами.  В  настоящей  работе  рассматриваются  компактные  двумерные  полиэдры  трехмерного  евклидова  пространства  .  Каждый  такой  полиэдр  P  является  объединением  конечного  множества  симплексов  размерностей  n  =  0,1,2.  Поэтому  он  задается  списком  вершин  (нульмерных  симплексов)  V,  списком  ребер  (одномерных  симплексов)  E,  списком  треугольников  (двумерных  симплексов)  T,  а  также  списком  троек  действительных  чисел,  являющихся  координатами  соответствующих  вершин  в  пространстве  .  Первые  три  списка  (без  координат  вершин)  образуют  симплициальную  схему  полиэдра.

Программный  комплекс

Для  решения  задач  вычислительной  топологии  при  участии  автора  данной  работы  создан  программный  комплекс  TSL.  Комплексом  поддерживаются  следующие  основные  форматы  моделей:

·     AF:  формат  трёхмерных  моделей  программы  3DPlus;

·     VRML  1.0:  Virtual  Reality  Modeling  Language  —  cтандартизированный  формат  файлов  для  демонстрации  трёхмерной  интерактивной  векторной  графики;

·     STL:  разработан  для  нужд  стереолитографии  и  предназначен  для  представления  трёхмерных  моделей.  Он  включает  в  себя  описание  треугольников,  из  которых  состоит  поверхность  объекта.

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

Основные  задачи,  решаемые  с  помощью  программного  комплекса:

·     Коллапсирование  в  размерностях  1  и  2.

·     Поиск  особенностей  двумерных  полиэдров.

·     Исследование  2-многообразий  на  ориентируемость.

·     Нахождение  базисных  циклов  графов.

·     Вычисление  базисов  групп  симплициальных  гомологий  по  модулю  2  для  двумерных  многообразий  и  псевдомногообразий  без  применения  матриц  инциденций.

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

·     Индексация  ребер  2-многообразия  относительно  1-цикла  и  построение  индексной  вектор-функции  [2]  относительно  заданного  базиса  группы  одномерных  гомологий.

·     Вычисление  индексов  пересечения  1-циклов  двумерного  многообразия.

·     Поиск  минимального  пути  с  заданным  индексом,  соединяющего  фиксированные  вершины  полиэдра.

·     Минимизация  одномерных  путей  и  циклов  в  их  классах  гомологий.

·     Построение  минимальных  1-циклов  ориентируемого  замкнутого  2-многообразия,  порождающих  канонический  базис  соответствующей  группы  гомологий.

Алгоритмы  минимизации  в  заданных  классах  гомологий

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

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

Для  решения  этой  задачи  в  [3]  предложен  следующий  метод.  Сначала  вычисляется  базис  группы  гомологий  по  модулю  2    и  строится  индексная  вектор-функция    относительно  этого  базиса.  Затем  для    строится  накрывающий  полиэдр  .  Его  вершинами  являются  пары  ,  состоящие  из  вершин    исходного  полиэдра    и  векторов  ,  где    —  ранг  группы  .  Кроме  того,  для  любого  пути  ,  соединяющего  вершины  ,  накрывающие  пути  соединяют  вершины  ,  удовлетворяющие  равенству  .  Далее  применяется  алгоритм  Дейкстры  (см.  [1])  для  поиска  пути  с  минимальным  весом  на  накрывающем  полиэдре  .  При  этом  в  качестве  начальной  точки  на    выбирается  пара  ,  а  в  качестве  конечной  —  пара  .  Наконец,  полученный  путь  проектируется  на  исходный  полиэдр  .

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

Множество  вершин  полиэдра  триангулированного  многообразия    обозначим  буквой  ,  множество  рёбер  —  .  Пусть,  как  и  выше,    —  неотрицательная  весовая  функция,    —  индексная  вектор-функция  относительно  некотрого  базиса  группы  ,  а  граф    представляет  собой  одномерный  остов  полиэдра  .

Построим  мультиграф  в  качестве  вершин  которого  возьмём  множество  ,  состоящее  из  начальной  и  конечной  вершин  пути  ,  а  также  всех  вершин,  инцидентных  рёбрам  с  ненулевым  значением  индексной  вектор-функции  .  В    каждую  пару  вершин    будут  соединять  дуга    со  значением  ,  если  ,  и  дуга  с  ,  имеющая  вес,  равный  весу  минимального  пути  между    и  ,  проходящего  по  рёбрам  с  нулевым  значением  индексной  вектор-функции.  При  этом  запоминается  соответствие  между  рёбрами/путями  на  графе    и  дугами  .

К  графу    применим  указанный  метод  и  получим  новый  алгоритм  минимизации  пути  в  его  классе  гомологий.  Он  состоит  из  следующих  процедур:

1.  Нахождение  базиса    группы  гомологий  .

2.  Вычисление  индексной  вектор-функции    относительно  базиса  .

3.  Построение  мультиграфа  .

4.  Построение  накрытия    с  помощью  вектор-функции  .

5.  Поиск  пути    с  минимальным  весом  ,  ,  на  накрывающем  графе  ,  соединяющий  вершины    и  .

6.  Вычисление  проекции    найденного  пути  на  .

7.  Восстановление  соответствующего    пути    на  .

Оценка  алгоритмической  сложности

Введём  обозначения:  ,  где    —  количество  симплексов  размерности  i  в  исходном  полиэдре;  .  При  построении  графа    для  каждой  вершины    используется  алгоритм  Дейкстры  для  графа    c  N₀  вершинами  и  N₁  рёбрами,  сложность  которого    [1].  Следовательно,  шаг  3  алгоритма  имеет  сложность

,                                          (1)

так  как  .

Для  построения  накрывающего  графа    и  последующего  поиска  на  нём  минимального  пути  используется  граф  ,  содержащий    вершин.  К  графу    вновь  применяется  алгоритм  Дейкстры.  Этот  алгоритм  имеет  сложность

,              (2)

так  как  ,  по  построению    и  .

Вычисление  базиса  группы    и  индексация  относительно  него  могут  быть  выполнены  с  помощью  алгоритмов,  разработанных  в  [2]  и  [4].  Первый  из  них  имеет  сложность  ,  а  второй  —  .  Остальные  шаги  в  силу  их  простоты  на  окончательную  оценку  сложности  алгоритма  повлиять  не  могут.

Отсюда,  из  (1)  и  (2)  получаем  сложность

.

Заметим,  что  если  применять  алгоритм  Дейкстры  к  графу  ,  накрывающему  ,  как  это  делается  в  алгоритме  2  из  [3],  то  сложность  составит  .  Поэтому  существенный  выигрыш  от  применения  нового  варианта  алгоритма  может  быть  получен  в  ситуации,  когда  количество  специальных  вершин    намного  меньше  параметра  .

Некоторые  приложения

Как  уже  отмечалось  выше,  в  качестве  моделей  3D  объектов  часто  используются  триангулированные  поверхности,  являющиеся  замкнутыми  ориентируемыми  многообразиями.  В  этом  случае  группа    является  векторным  пространством  четной  размерности    над  полем  ,  а  индекс  пересечения    представляет  собой  симплектическую  форму  на  .  Поэтому  существует  базис  группы  ,  в  котором  форма    приводится  к  каноническому  виду.  Этот  базис  естественно  также  называть  каноническим. 

Разработанный  нами  алгоритм  может  быть  использован  при  реализации  предложенного  в  [4]  метода  нахождения  циклов  ,  каждый  из  которых  минимален  в  своем  гомологическом  классе,  а  гомологические  классы    образуют  канонический  базис  симплектического  векторного  пространства  .  Циклы  с  такими  свойствами  позволяет  выделять  ручки  поверхности  ,  что  важно  для  анализа  его  топологической  структуры. 

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

Список  литературы:

1.Кормен  Т.,  Лейзерсон  Ч.,  Ривест  Р.  Алгоритмы:  построение  и  анализ.  М.:  МЦНМО,  2001.  —  960    с.

2.Яковлев  Е.И.  Вычислительная  топология.  Нижний  Новгород:  Изд-во  ННГУ.  2005.

3.Lapteva  A.V.  and  E.I.  Yakovlev.  Index  Vector-Function  and  Minimal  Cycles  //  Lobachevskii  Journal  of  Mathematics.  —  2006.  —  Vol.  22.  —  P.  35—46.

4.Lapteva  A.V.,  Yakovlev  E.I.  Minimal  1-Cycles  Generating  a  Canonical  Basis  of  2-Manifold’s  Homology  Group  //  International  Journal  of  Pure  and  Applied  Mathematics.  —  2006.  —  Vol.  31.  —  №  4.  —  P.  555—570.