1

这是过去几天一直困扰我的一个问题——我的同事认为这是一个经过充分研究的问题，但我在网上找不到任何论文（也许我使用的关键词不正确）。给定一个图形，其中每个顶点对应于一个曲面，并且如果相应的曲面在一条线上相交，则两个顶点之间存在一条边，我将如何识别组合形成闭合体积的曲面？

例如，立方体（表面编号为 1 到 6）的邻接列表可能如下所示：

1 -> [4,2,5,6]
2 -> [1,3,5,6]
3 -> [2,4,5,6]
4 -> [3,1,5,6]
5 -> [1,2,3,4]
6 -> [1,2,3,4]

除了这些信息之外，我还知道某些曲面是否有自由边（即这些边不与任何其他曲面共享），这意味着我可以立即排除这些曲面，因为具有自由边的曲面不能成为腔体的一部分边界。此外，如果两个表面相遇，它们将在边界处干净地相遇 - 没有扫视等。

我希望能够做的不仅仅是识别一个空腔的存在，还要输出表面和它们所包含的空腔之间的映射。例如，在两个立方体在边缘相遇的情况下（没有足够的声誉来发布图像，所以这是一个侧视图）：

-----------
|         |
|         |
|         |
---------------------
          |          |
          |          |
          |          |
          -----------

...这将是所需的输出，假设表面 1-6 组成立方体 ONE 并且 7-12 组成立方体 2：

Volume 1 -> [1,2,3,4,5,6]
Volume 2 -> [7,8,9,10,11,12]

请注意，在这种情况下，一些表面在图中有六个邻居，而其他表面只有四个邻居。

任何帮助将非常感激！

4

1 回答 1

0

是的，这个领域被称为计算拓扑。它的中心对象是循环的代数群，称为同调群（当循环由 1-dim 边缘形成时为 H1，当我们谈论 2-dim faces时为 H2 ）。

可以通过形成同调群矩阵来分析这样的群。对于某些查询，需要 H1 和 H2 矩阵。

当矩阵可以重新排列成独立的块时，这意味着形状没有相互作用。当一个单块同源矩阵有 N 个等级时，这意味着形状有 N 个空腔（孔）。像立方体这样的简单形状有 0 个孔，圆环有 1 个等。

可以找到用于这些计算的 C++ 和 MATLAB 开源包。

希望它提供一些有用的关键字。

于 2013-11-02T19:27:41.133 回答