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