Получить смежные лица в сетке

Question

Я ищу алгоритм, чтобы найти все (или максимальное количество) смежных граней непрерывной сетки. Грани должны быть упорядочены в виде массива таким образом, чтобы каждой грани предшествовала грань, связанная с ней в сетке. Конечная цель - иметь один такой массив. Возможно ли это даже в теории? Если нет, то как лучше всего увеличить количество граней в массиве?

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

Edit:

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

Answer 1

Это сложная проблема ( задача о гамильтоновом пути в плоском графе (в частности, двойственный входной граф)), но вы можете получить хорошие результаты с помощью локального метода поиска.Есть простой из-за Angluin и Valiant (https://doi.org/10.1016/0022-0000(79)90045-X) и более сложное усилие Frieze (https://doi.org/10.1002/rsa.20542).) Теоретически доказано, что эти алгоритмы работают только на случайных графах, но графы без состязательного построения частоподдается тоже.