0

线条图类似于图形，但其顶点具有 x,y 位置。没有交叉边缘。例如，像这样的线条图是具有 13 个顶点的线条图，其编号为 0-12。一张脸是一个没有“内部”路径的循环。示例中的面孔将是

(0,1,3,2,0), (2,3,5,4,2), (4,5,8,7,4), (7,8,12,11,7) and (0,2,4,7,11,10,9,6,0)

循环(0,1,3,5,4,2,0)不是一张脸，因为里面有一条路径，名为(2,3). 循环(0,1,3,5,8,12,11,10,9,6,0)也不是一张脸，因为里面有一条路径 (0,2,4,7,11)。我可以使用什么算法来识别示例中的人脸？

4

1 回答 1

0

假设你所有的边都是线段；每个平面图都可以仅使用线段来绘制。还假设图是连接的。现在算法非常简单：

构造一个有向图，使得顶点与原始图中的顶点相同，并且每个原始边都有两条有向边，每个方向都有一条

从尚未使用的随机（有向）边开始。最后，顺时针选择下一个出边（或逆时针也可以，只是始终相同）。要确定是哪条边，您必须根据平面嵌入中的顶点坐标进行计算。您最好事先为每个顶点预先计算此边缘顺序。

继续对选定边的末端执行此操作，直到到达起始顶点。此时，您已经完成了一张脸。

当没有未使用的边时，您已在图中找到所有面

或者，使用像 Boost 这样的库，它可以有效地执行此类任务

于 2013-10-16T10:42:36.673 回答