Tech Ideas

C++,Linux,Algorithm,Crypto,Lisp,etc

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

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

网格如图:

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

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( )这两个函数。

这两个函数的原理相同, uniqPointOfTriangle( )uniqPointOf2Points()唯一的作用是

它的一个性质:    输出和输入参数的顺序无关。

如果没有这两个函数的判断,每个三角形会被输出6次,而有了这两个函数的限制后,强制在3个元素的6中排列中指定1种,

就消除了重复。

uniqPointOfTriangle的实现我想了一个邪恶的办法:

1
2
3
4
5
6
7
8
struct point * uniqPointOfTriangle(struct point * a,struct point * b ,struct point * c){
        /*返回一个3个点的特征点,即不管a,b,c的次序,这个函数返回结果唯一*/
        struct point * p=NULL;

        //我直接比较指针大小,O(∩_∩)O哈哈~
        p=(a > b?a:b);
        return p > c?p:c;
}

还有一种正常一点的办法:

思路是:对三个点,先在x方向找出最小的点,若有一个,直接返回;若有两个,找出y方向小的那个返回。

另外,这样输出的三角形中其内部可能有其他的点,若要消除,再加上一层过滤,去除掉那些”p有邻点在p,np,nnp三角形中的”情况即可,

这是因为这个图由三角形构成的特殊性质,如果有在p–np–nnp中有点,假设这些点都不和p相连,那么,

这些点和p-np, p-nnp构成的区域必然不是三角形!所以可以这样干。