获取网格中连续的面

Question

我正在寻找一种算法，以找到连续网格的所有（或最大数量的）连续面。这些面应该按照顺序排列在一个数组中，以便每个面都在其前面连接到网格上的一个面。最终目标是拥有单个这样的数组。即使在理论上也可能吗？如果不可能，那么最大化数组中面的计数的最佳方法是什么？

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

编辑：

这是一个三角形网格，即每个面都恰好有三个顶点。要求是具有覆盖网格的所有连接面的最少数量的集合（理想情况下为1）。

- Blender Dadaist

---

你是如何表示网格的？同时，你如何定义不连续性？理想情况下，我认为网格应该是良好形成的，没有“洞”。每个面都可以从其他面到达，对吗？ - Srini

Answer 1

这是一个困难的问题（在平面图中，特别是输入图的对偶图中的哈密顿路径问题），但您可以使用局部搜索方法获得良好的结果。由Angluin和Valiant提出了一种简单的方法(https://doi.org/10.1016/0022-0000(79)90045-X)，Frieze也做出了更复杂的努力(https://doi.org/10.1002/rsa.20542)。这些算法在理论上被证明只适用于随机图，但没有敌对构造的图通常也是可行的。

- David Eisenstat

---

我也是这样考虑这个问题的，尽管我不知道是否有一些拓扑方法可以简化它。从Wikipedia上看，它说4连通平面图总是有哈密顿路径，并且可以在线性时间内计算，所以我想对于四边形的封闭网格来说，总是可以做到的。我不确定这是否太令人惊讶了。此外，这是在假设网格是“良好形式”（流形）的情况下，否则图形不必是平面的，我认为是这样的。 - jdehesa

@jdehesa 当然可以。这些算法适用于一般图。 - David Eisenstat

这（Angluin和Valiant）看起来非常有前途。不过我需要一些时间来理解和实现它。当我在实现方面取得一些进展时，我会在这个线程上分享结果。 - Blender Dadaist

我非常感激任何能够访问引用来源并为每个提供简单解释的人。 - Andrew Micallef

@AndrewMicallef 我为另一个答案实现了 A--V：https://dev59.com/questions/JmUo5IYBdhLWcg3wnwn2#15904295 - David Eisenstat

@AndrewMicallef 简而言之：随机延伸路径，如果路径形成环路，则删除与度为3的顶点相邻的一个环边，然后从另一端继续。 - David Eisenstat