接楼上:其中,25代表地形块的离散点数目,接下来的25行每行代表一个三维点的xyz坐标,32代表这块地形共有32个三角形,接下来的32行代表每个三角形对应的点序列,例如1 2 6 代表由第一个 第二个 第六个点构成了一个三角形.现在要根据这些已有的数据来生成断面曲线和等高线,首先要建立好这些离散数据之间的关系,请问大家有没有高效率的算法来找出共享边线段的两个三角形,并将这两个三角形(索引或ID)存储到共享边之中?我现在写的代码如下: for(i=0; i<TriCount; i++) //TriCount为三角形数目 {//给AllBord和AllTri存入数据int point1,point2,point3;//记录当前三角形的三个顶点序号fscanf(fp, "%d %d %d", &point1, &point2, &point3);TBord b1(AllPoint[point1-1],AllPoint[point2-1]);//数组中对应的下标应减1 //copyTBord b2(AllPoint[point2-1],AllPoint[point3-1]);TBord b3(AllPoint[point3-1],AllPoint[point1-1]);//当前三角形的三条边int b1in = -1;//记录b1边是否在AllBord内int b2in = -1;//记录b2边是否在AllBord内int b3in = -1;//记录b3边是否在AllBord内int CurrentBordCount = AllBord.size();//获得当前存储的边数if (b1==AllBord[CurrentBordCount]){ b1in=CurrentBordCount;}else { for(int j=0; j<CurrentBordCount; j++)//对每条边进行判断 {
if (b1==AllBord[j])//搜索边数组，判断b1边是否在AllBord数组中
{
b1in = j; //覆盖-1；b1边已经在边数组中
} }}
if (b2==AllBord[CurrentBordCount]){ b2in=CurrentBordCount;}else { for(int j=0; j<CurrentBordCount; j++)//对每条边进行判断 {
if (b2==AllBord[j])//搜索边数组，判断b1边是否在AllBord数组中
{
b2in = j; //覆盖-1；b1边已经在边数组中
} }}if (b3==AllBord[CurrentBordCount]){ b3in=CurrentBordCount;}else { for(int j=0; j<CurrentBordCount; j++)//对每条边进行判断 {
if (b3==AllBord[j])//搜索边数组，判断b1边是否在AllBord数组中
{
b3in = j; //覆盖-1；b1边已经在边数组中
} }}
if (b1in != -1){//b1边已经记录；tri1已经记录 AllBord[b1in].tri2 = i; //对应边（公共边）的右三角形设为i. i为三角形在数组中的下标（从0开始） AllTri.bord1 = b1in; //AllTri.bord1:AllTri中对应三角形的第一条边设为bord1在AllBord中的索引}else{//b1边还未记录 CurrentBordCount = AllBord.size();//已经记录的边数 AllBord.push_back(b1);//将b1边加入边数列 AllBord[CurrentBordCount].tri1 = i; AllTri.bord1 = CurrentBordCount;//当前三角形的第一条边在AllBord中的位置}if (b2in != -1){//b2边已经记录；AllBord[b2in].tri1已经记录 AllBord[b2in].tri2 = i; AllTri.bord2 = b2in;}else{//b2边还未记录 CurrentBordCount = AllBord.size(); AllBord.push_back(b2); AllBord[CurrentBordCount].tri1 = i; AllTri.bord2 = CurrentBordCount;}if (b3in != -1){//b3边已经记录 AllBord[b3in].tri2 = i; AllTri.bord3 = b3in;}else{//b3边还未记录 CurrentBordCount = AllBord.size(); AllBord.push_back(b3); AllBord[CurrentBordCount].tri1 = i; AllTri.bord3 = CurrentBordCount;} }//endfor程序说明:AllPoint为存储离散点的数组,AllBord为存储三角形边的数组因为地形数据量很大,点数据少则成千上万,多则几十万上百万,所以,上面的代码执行效率很低,根本不能运算大面积的地形数据,外层循环固定,内层循环递增,大家有没有更好的办法可以使得给定某一个三角形的边后可以快速得到共享这个边的两个三角形的ID或是索引?注:以上数据只是一个测试数据,实际的地形数据是完全不规则的,离散点和每个三角形在数据文件中出现的顺序都随机.望各位有兴趣的能人和高手能给出个效率高的算法!! |
