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

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

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

在此输入图像描述

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

不管怎样，对我来说这似乎很奇怪，你会知道图具有这样的属性，但不知道同一时刻各自的平面嵌入是什么。