algorithm - 获取网格中的连续面

Question

我正在寻找一种算法来查找连续网格的所有(或最多)连续面。面应该按这样的方式排列在一个数组中，即每个面前面都有一个在网格上链接到它的面。最终目标是拥有一个这样的数组。即使在理论上也可能吗？如果不是，最大化数组中面数的最佳方法是什么？

在this (rather naive) implementation选择点顺时针遍历最后覆盖面的可用边的结束顶点。但这很快就陷入了死胡同。我还尝试了边缘的两端，或面部的所有可用顶点，但迟早每个顶点都会到达一个与未选择的面部没有连接的面部。

编辑:

这是一个三角网格，即每个面都有三个顶点。并且要求有一组最少数量的阵列(最好是一个)覆盖网格的所有连接面。

Answer 1

这是一个难题(平面图中的 Hamiltonian path problem(特别是输入图的对偶))，但您可能会使用局部搜索方法获得良好的结果。 Angluin 和 Valiant (https://doi.org/10.1016/0022-0000(79)90045-X) 有一个简单的作品，Frieze (https://doi.org/10.1002/rsa.20542) 则有一个更复杂的作品。这些算法在理论上被证明仅适用于随机图，但没有对抗性构造的图通常也适用。