找出平面上的特殊无向图中的所有三角形的算法

2011-08-22
science

问题提出背景：在非结构化三角形网格生成过程中，若采用前沿推进法，在推进过程中是不好构造三角形的（而且也没有要），最好在把所有的边都连好以后再找出所有三角形，于是提出了问题：在由三角形构成的平面无向图中如何找出所有三角形？

网格如图：

要注意的是，这个无向图很特殊，

1.这个图在平面上。

2.这个图是由三角形构成的（如果不是由三角行构成，那这个网格就没有用处了）。

我的算法如下，伪代码表示:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

foreach(点 p in所有的点){
    foreach(点 np in p的所有邻居点){
        foreach(点 nnpin np的所有邻居点){
            if(   p,np,nnp三点两两不重合
               && p,np,nnp三点两两相连
               && p==uniqPointOfTriangle(p,np,nnp)
               && uniqPointOf2Points(np,nnp)==np)  ){
                   输出p,np,nnp构成的三角形。
               }
       }
   }
}

算法的关键在于uniqPointOfTriangle( )和uniqPointOf2Points( )这两个函数。

阅读更多