问三维中双连通边表的构造算法

EN

链接文章中的问题陈述说，只有顶点和边被输入到算法中，但是我认为，如果不对网格的面进行额外的输入，就不可能在3D中明确地做到这一点。在2D情况下，由于输入被指定为平面图，这些面是明确的:平面中包含在边缘环中的任何区域，以及内部没有边缘的区域，都是人脸。然而，在3D中，你不知道哪些边缘环应该是脸，哪些不应该。

考虑一个立方体，表示为仅仅是顶点和边:您可能希望将立方体的“通常”6面视为面，但不希望算法在内部创建跨越立方体对角线的附加面。但是算法不可能知道这一点。此外，顶点/边缘网格甚至不可能以合理的方式分配人脸；它可能有非平面面，可能是不可定向的(例如，莫比乌斯条)或非流形。

通常，在3D应用中，我们已经定义了网格面，我们可以假设它是一个流形的、可定向的网格。以人脸数据作为算法的输入，例如沿每一个面按逆时针顺序排列的边或顶点列表，那么就可以简单地(如果繁琐的话)计算出半边关系。