graph - 查找平面图（几何形状）的边界（边界）边

Question

我有描述平面几何形状（面是三角形）的顶点和边列表。例如：

   a_______b
   /|\    /
  / | \  /
e/__|__\/c
    d

Verts: a, b, c, d, e
Edges: (a,b), (a,c), (a,d), (a,e), (b,c), (c,d), (d,e)

这就是我所拥有的关于特定平面几何形状的所有信息。在此示例中，唯一的内部边缘是 (a,c) 和 (a,d)。所有其他边缘都是边界边缘。如何通过算法识别这些边界边缘（或反过来识别所有内部边缘）？

动机：如果有帮助，我正在尝试构建导航网格，其中一个步骤是构建可见性图，我认为第一步是识别边界边缘。

Answer 1

对于平面图，“外表面”属性不是唯一的；您可以绘制图形以使任何面成为外部面，或者您甚至可以绘制图形以使其具有不同的面 - 考虑您的示例图：

也就是说，如果您知道可以绘制图形以使所有内部面都是三角形的，则可以扫描边列表并检查它们属于多少三角形（通过检查相邻边）。如果边只属于一个三角形，则为外边。

无论如何，对我来说似乎很奇怪，您会知道图形具有这样的属性，但同时不知道各自的平面嵌入是什么。

Answer 2

我知道有点晚了。在 FEM 社区中，我们计算每个三角形的边，然后边界是出现一次的边。如果它是用稀疏矩阵完成的，它会非常快（对我来说）。