查找平面图（几何形状）的边界（边界） [英] Find border (boundary) edges of planar graph (geometric shape)

问题描述

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

  a_______b 
 / | \ / 
 / | \ / 
e / __ | __\ / c 
d 
 
 Verts：a，b，c，d，e 
边缘：（a，b）， （a，c），（a，d），（a，e），（b，c），（c，d），（d，e）
  

这就是所有关于特定平面几何形状的信息。在这个例子中，唯一的内部边是（a，c）和（a，d）。所有其他边缘都是边框边缘。如何在算法上识别这些边界边界（或者相反地识别所有内部边界）？

动机：如果有帮助，我试图建立一个导航网格，其中的步骤是建立一个可见性图，我认为的第一步是确定边界的边缘。

解决方案

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

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

I have vertices and an edge list that describe a planar geometric shape (faces are triangles). For example:

   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)

So that is all the information I would have about that particular planar geometric shape. In this example, the only internal edges are (a,c) and (a,d). All other edges are border edges. How can I identify those border edges algorithmically (or conversely identify all internal edges)?

Motivation: If it helps, I'm trying to build a navigation mesh, one of the steps of which is to build a visibility graph, the first step of which I think is to identify the border edges.

解决方案

For planar graphs, the "outer face" property is not unique; you can draw the graph so that any of the faces becomes the outer one, or you can even draw the graph such that it has different faces - consider your example graph:

That said, if you know that the graph can be drawn such that all internal faces are triangular, you could scan the list of edges and check how many triangles they belong to (by checking the neighboring edges). If the edge only belongs to one triangle, it's an outer edge.

Anyway, it seems weird to me, that you would know the graph has such property and not know what the respective planar embedding was at the same moment.

这篇关于查找平面图（几何形状）的边界（边界）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！