2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Точка локального сочленения
Сообщение09.12.2016, 13:05 
Аватара пользователя


10/11/11
93
Kyiv
Доброго всем дня. Возникла задача, связанная, в принципе, с компьютерной графикой. Небольшая прелюдия. Не вдаваясь в детали, будем рассматривать сетку некоторого трехмерного объекта как граф в трехмерном пространстве. Возникла потребность сдвигать одни точки на другие, но при этом понадобилось проклассифицировать вершины, которые нельзя трогать.

Остановился на том, что вершины, у которых для каждого ребра есть только две прилежащие к нему грани (треугольники, причем обратные мы не считаем) - это такие вершины, которые можно двигать в сторону любой другой вершины (manifold vertex). Если больше двух соседних граней - то это не очень хорошая точка (non-manifold vertex), на нее можно сдвигать манифольдные, но не более того.
Формально говоря, в первом случае выходило, что прилежащие к данной вершине грани-треугольники можно обойти по признаку прилегающего ребра, сформировав простой цикл. В неманифольдном случае вообще достаточно наличия более двух граней для того, чтоб идентифицировать. Есть еще случай, когда обход граней представляет из себя простую цепь (не замкнутую в цикл) - это значит, что у нас граничная вершина (manifold with boundary).

В принципе, казалось бы, что быстрой проверки по числу смежных граней было бы достаточно (это было бы быстрее, чем искать циклы и цепи). Но дело в том, что это работает не всегда: можно выделить, так сказать, точки локального сочленения (junction vertex): когда существует несколько максимальных по размеру циклов и/или цепей, сформированных из соседей точки.
Просто для точек сочленения есть хороший алгоритм, который позволяет найти их прямо во время обхода графа, например, в глубину. Но такой алгоритм, на самом деле, показывает, есть ли путь по всему графу, что не подходит, когда, например, у нас точка в "ручке" поверхности, род которой больше 0 (в торе, к примеру, в котором в одном месте появилась такая "локальная" точка сочленения, последняя таковой считаться не будет, т.к. можно пройти к ней с обратной стороны).
А проверять локально для каждой точки довольно долго (даже если отбросить неманифольдные вершины и точки глобального сочленения, полученные при проходе в глубину, для подозреваемых на манифольдность или граничность надо проверять, которых большинство и на порядок больше, чем точек сочленения).

Следовательно, после этой преамбулы, вопрос. Может ли кто подсказать, есть возможность это как-то все упростить, или вдруг есть способ проверять такие точки на глобальном уровне (к примеру, храня какие-то данные, полученные от соседних точек, пройденных раньше).

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

-- 09.12.2016, 12:18 --

Собственно, примеры таких точек локально сочленения.
Где-то в пространстве, на определенной поверхности. Подозреваемая на граничность вершина. И, в принципе, и была бы такой, если бы еще одну грань добавить.
Изображение
Две пирамидки, соединенные вершиной. Вроде каждое ребро имеет две грани-соседа, но в целом, обходом можно получить два цикла максимальной длины.
Изображение

-- 09.12.2016, 12:24 --

Алгоритм поиска точек сочленения во время обхода в глубину можно увидеть тут, к примеру. (понимаю, внешние ссылки - это не очень, но как есть).
http://e-maxx.ru/algo/cutpoints
Ну, и пример с тором, где обе точки локального сочленения глобальными по вышеуказанному алгоритму не будут.
Изображение

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ 1 сообщение ] 

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group