2014 dxdy logo

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

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




 
 Точка локального сочленения
Сообщение09.12.2016, 13:05 
Аватара пользователя
Доброго всем дня. Возникла задача, связанная, в принципе, с компьютерной графикой. Небольшая прелюдия. Не вдаваясь в детали, будем рассматривать сетку некоторого трехмерного объекта как граф в трехмерном пространстве. Возникла потребность сдвигать одни точки на другие, но при этом понадобилось проклассифицировать вершины, которые нельзя трогать.

Остановился на том, что вершины, у которых для каждого ребра есть только две прилежащие к нему грани (треугольники, причем обратные мы не считаем) - это такие вершины, которые можно двигать в сторону любой другой вершины (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 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group