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

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)，其余的边都是边界边。如何通过算法识别这些边界边（或相反，识别所有内部边）？

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

- Matthew Alpert

Answer 1

对于平面图来说，“外部面”属性并不唯一；你可以绘制图形，使任何一个面成为外部面，甚至可以绘制不同的面——考虑你的示例图：

（两张图片）

话虽如此，如果你知道可以将图形绘制成所有内部面都是三角形，那么你可以扫描边缘列表，并检查它们属于多少个三角形（通过检查相邻的边缘）。如果边缘仅属于一个三角形，则它是外部边缘。

总之，我觉得很奇怪，你会知道图形具有这样的属性，但同时不知道相应的平面嵌入是什么。

- voidengine

---

那个解决方案大约在一个小时前浮现在我脑海中。而且我在问题中提到了面是三角形。之所以我不会知道所有的事情，是因为我基本上正在创建一个图形构建器。用户可以随意放置顶点并添加边缘，只要完成的图形是平面的且所有面都是三角形即可。因此，在任何时刻，程序只会知道顶点和边缘的列表。因此，首先我需要构建面（三角形）的列表。 - Matthew Alpert

我想我可以查看一个边缘，获取所有相邻的边缘，然后找到共享不属于原始边缘的顶点的边缘对。我认为复杂性将基于图的连通性，这应该不会太糟糕。有更好的想法吗？ - Matthew Alpert

Answer 2

我知道有点晚了。在有限元社区中，我们为每个三角形计算边缘，然后边界是仅出现一次的边缘。如果使用稀疏矩阵进行计算，速度非常快（对我来说）。

- hugo d