7

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

 2 years ago
source link: https://byronhe.com/post/2011/08/22/find-uniqPointOfTriangle/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

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

2011-08-22

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

网格如图：

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

1.这个图在平面上。

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

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

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的实现我想了一个邪恶的办法:

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构成的区域必然不是三角形！所以可以这样干。


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK