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

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

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）。所有其他边缘都是边缘边缘。如何在算法上识别这些边界边界（或者相反地识别所有内部边界）？动力：如果有帮助，我试图建立一个导航网格，其中的一个步骤是建立一个可见性图形，我认为它的第一步是识别边界边缘。

来源

2012-04-22 Matthew Alpert

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

enter image description here

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

无论如何，对我来说这似乎很奇怪，你会知道该图有这样的属性，不知道相应的平面嵌入在同一时刻是什么。

来源

2012-04-22 09:37:53 voidengine

这个解决方案在我大约一个小时前找到了我。我在问题中提到了脸部是三角形的。我不会知道一切的原因是因为我基本上是在创建一个图形构建器。只要完成的图形是平面的，并且所有的面都是三角形，用户就可以将顶点放在任何他们喜欢的位置，并在任何他们喜欢的位置添加边。因此，所有程序随时都会知道顶点和边的列表。因此，首先我必须建立面（三角形）列表。 – 2012-04-22 21:44:33

我想我可以看一个边，得到所有相邻的边，然后找到共享一个顶点而不是原始边的一部分的边对。我认为复杂性将基于图的连通性，这不应该太糟糕。任何更好的想法？ – 2012-04-22 21:59:52

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

回答

相关问题