精华内容
下载资源
问答
  • 比较了各种三角网构建方法,并详细介绍了Delaunay三角网构建方法
  • 度难以保证等问题,分析了同类算法的特点和缺陷,研究了影响约束数据域Delaunay三角剖分算 法效率提高的因素,提出了基于约束数据域三角剖分的整体模型优化算法,讨论了基于该模型的 DEM建立的方法、步骤和过程,...
  • 方法首先递归分割点集,然后按照构网条件以分割线为轴线对其两侧的点进行构造三角网的操作,直至每个点都被包含进所构建的三角网,最后使其成为Delaunay三角网。结果通过1000-5000个点的测试,表明基于分治策略的...
  • ​ 一般的Delaunay三角网构建算法效率很低,只适合于少量点(大约几千个点),这是因为三维Delaunay三角网如果使用数组来进行存储,存取和计算效率都会比较低,理想办法是使用合适三维模型,如kdtree、八叉树等...

    image-20210318113146748

    激光点云快速构建Delaunay三角网python

    ​ 一般的Delaunay三角网构建算法效率很低,只适合于少量点(大约几千个点),这是因为三维Delaunay三角网如果使用数组来进行存储,存取和计算效率都会比较低,理想的办法是使用合适的三维模型,如kdtree、八叉树等三维模型或者是通过并行处理提高运算速度,scipy库中提供了Delaunay方法调用,可以快速的进行大量三维点Delaunay三角网的构建,然后使用mayavi.mlab进行渲染,效果较好。

    使用库文件

    pclpy:用于读取.pcd格式的激光点云数据,调用tolist函数返回list格式的点云坐标数据;
    mayavi:mayavi的mlab模块提供了方便快捷的绘制三维图函数。只要把数据准备好,通常只需要调用一次mlab的函数就可以看到数据的三维显示效果。非常适合在IPython中交互式地使用。
    scipy.spatial:对空间数据存储和组织构建高效的模型,如kdtree,通过并行处理提高三维空间数据的运算速度,
    Delaunay:构建Delaunay三角网
    

    完整代码

    from scipy.spatial import delaunay_plot_2d  
    from scipy.spatial import Delaunay  
    import numpy as np  
    import pclpy  
    from pclpy import pcl  
    from mayavi import mlab  
    import matplotlib.pyplot as plt  
    from mpl_toolkits.mplot3d import Axes3D  
      
    # 读  
    pc = pclpy.pcl.PointCloud.PointXYZ()  
    pcl.io.loadPCDFile('./data/DataSample.pcd', pc)  
      
    xyz_points = pc.xyz.tolist()  
    xy_points = pc.xyz[:,0:2].tolist()  
      
    tri = Delaunay(xy_points)  
    mlab.triangular_mesh(pc.x, pc.y, pc.z, tri.simplices)  
    mlab.show()  
    

    构建结果

    ​ 这里我们使用600+w个点进行Delaunay三角网构建,耗时大约为30s,电脑内存为16G,效果如下。

    image-20210318113019695

    思考总结

    ​ 三维空间数据的存储、组织与管理直接关系到空间运算的效率和精度,现有的三维可视化不能够很好地展现三维实体在多个层次上的细节特征,这也是三维可视化研究的热点方向。造成这种状况的一个重要原因是二维数据结构向三维数据结构扩展的复杂性,不少学者认为开发三维GIS平台的技术关键和瓶颈可能就在于找到合适的三维数据结构,以实现三维空间数据的便捷存储、展示和分析,因此研究者们对可能的三维数据结构进行了大量的探索,这些三维数据结构大致可以分为基于面的三维数据结构和基于体的三维数据结构。基于面的三维数据结构包括栅格结构、不规则三角网结构、边界表示结构和参数方程式结构,基于面的三维数据结构具有精度高、显示美观和更新便捷的优点,但是由于存储关系数据的困难,导致难以进行三维空间分析;基于体的结构包括3D栅格、八叉树结构、实体结构几何和四面体等结构,其优点是便于表示空间体的整体分布状况,这一存储方式解决了基于面结构中空间操作和空间分析困难的问题,但是在存储空间和计算速度等方面存在着有不足之处。

    展开全文
  • 对并行环境下 Delaunay三角网的构建及实时更新进行了研究。针对海量数据处理高效性要求,提出了一种 归并构网方法。该方法根据构网数据实际分布特点,对数据点按 x坐标进行排序,并将排序后数据按给定阈值 点数...
  • 分析了3种不同方法的优缺点和各自代表性算法时间复杂度, 并详细讨论了Delaunay三角网构建方法在大规模 场景渲染和地形可视化领域中未来3个研究方向: 混合算法研究、算法支撑技术研究和分布式并行算法研究。
  • 提出了一种改进前沿边推进算法来构建Delaunay三角网,提高了Delaunay三角网的构网速度.通过等值点插值、追踪、平滑处理和等值区构造,实现了二维电磁态势可视化.仿真结果表明,采用该方法绘制二维电磁态势图...
  • 方法首先按Graham扫描法对平面散乱点集进行排序,然后将排好序点通过可见点判断连接成Graham三角网,最后利用拓扑结构快速进行优化,使其成为Delaunay三角网。结果通过500至10000个点测试,表明这种基于C-...
  • Delaunay三角剖分—三角网生长算法

    千次阅读 2017-03-08 20:35:53
    关于Delaunay三角网构建的研究有许多,但由于本课题具有数据量大的特征,不宜直接沿用已有构建方法,笔者针对本课题数据特征,研究获得了适应本课题,速度较快的构建方法。Delaunay三角网有一个特性,每个三角网形成...

    Delaunay三角网是俄国数学家B.Delaunay于1934年发现的。关于Delaunay三角网构建的研究有许多,但由于本课题具有数据量大的特征,不宜直接沿用已有构建方法,笔者针对本课题数据特征,研究获得了适应本课题,速度较快的构建方法。Delaunay三角网有一个特性,每个三角网形成的外接圆都不包含其他参考点。利用这一个性质,我们可以直接构成Delaunay三角网:
    一、建立第一个三角形
    1、判断用来建立TIN的总脚点数,小于3则报错退出。
    2、第一点的选择:
    链表的第一节点,命名为Pt1;
    3、第二点的选择:
    A.非Pt1点; B.距Pt1最近
    命名为Pt2
    4、第三点的选择
    A.非Pt1,Pt2点;
    B.与Pt1,Pt2点组成的三角形的外接圆内无其他节点;
    C.与Pt1,Pt2组成的三角形中的角Pt1Pt3Pt2最大。
    命名为Pt3
    5、生成三边,加入边表
    6、生成第一个三角形,组建三角形表
    二、扩展TIN
    1、从边表头取一边,要求:该边flag标志为假(只在一个三角形中)
    2、从点链表中搜索一点,要求:
    A、与边中的Pixel3在边的异侧;
    B、该点与边组成的三角形的外接圆内无其他点
    C、满足上面两条件的点中角Pt1Pt3Pt2最大的点为Pt3。
    3、判断新生成的边,如果边表中没有,则加入边表尾,设定标志flag为假,如果有,则设定该边flag为真。
    4、将生成的三角形假如三角形表
    5、设定选中的边的标志flag为真
    6、转至1,直至边表边的标志flag全部为真。

    注:如果需要进行限制三角剖分,则可利用重心法取出不要的三角形,必要时,可对边界进行限制,不让生成的边与边界相交

    数据结构:

    struct Pixel    //脚点数据
    {
    double x,y,z,g;
    bool flag;
    };
    struct List //数据链表
    {
    Pixel *pixel;
    List *next;
    };
    struct Line //三角形边
    {
    Pixel *pixel1;  //三角形边一端点
    Pixel *pixel2;  //三角形边另一端点
    Pixel *pixel3;  //三角形边所对顶点
    bool flag;
    };
    struct Linelist //三角形边表
    {
    Line *line;
    Linelist *next;
    };
    struct Triangle //三角形表
    {
    Line *line1;
    Line *line2;
    Line *line3;
    Triangle *next;
    };
    
    
    
    以下是程序中关于建网的部分:
    // DelaunayTIN.cpp: implementation of the CDelaunayTIN class.
    //
    //
    //功能:   用给定的数据链表数据,组建Delaunay不规则三角网
    //输入参数:数据链表list;区域范围(XMin,YMin),(XMax,YMax)
    //输出参数:不规则三角网首三角形地址
    
     Triangle * CSimRegular::CreateDelaunayTIN(List *list)
    {
        //组建第一个三角形
         List *node;
         Pixel *pt1,*pt2,*pt3;
        bool flag;
        Triangle *TIN;
        pt1=list->pixel;
        pt2=list->next->pixel;
        node=list->next->next;
        while(node!=NULL)
        {
            if(
             (pt1->x-node->pixel->x)*(pt1->x-node->pixel->x)+(pt1->y-node->pixel->y)*(pt1->y-node->pixel->y)
           <(pt1->x-pt2->x)*(pt1->x-pt2->x)+(pt1->y-pt2->y)*(pt1->y-pt2->y)         
                )
            {
                pt2=node->pixel;
            }
            node=node->next;
        }
        node=list->next;
        pt3=NULL;
        while(node!=NULL)
        {
            if(node->pixel==pt1 || node->pixel==pt2)
            {
                node=node->next;
                continue;
            }
    
            if(pt3==NULL)
            {
                pt3=node->pixel;
            }
            else
            {
                float dist11=sqrt((pt1->x-node->pixel->x)*(pt1->x-node->pixel->x)+(pt1->y-node->pixel->y)*(pt1->y-node->pixel->y));
                float dist12=sqrt((pt2->x-node->pixel->x)*(pt2->x-node->pixel->x)+(pt2->y-node->pixel->y)*(pt2->y-node->pixel->y));
                float dist12_3=sqrt((pt1->x-pt2->x)*(pt1->x-pt2->x)+(pt1->y-pt2->y)*(pt1->y-pt2->y));
                float dist21=sqrt((pt1->x-pt3->x)*(pt1->x-pt3->x)+(pt1->y-pt3->y)*(pt1->y-pt3->y));
                float dist22=sqrt((pt3->x-pt2->x)*(pt3->x-pt2->x)+(pt3->y-pt2->y)*(pt3->y-pt2->y));
                if((pow(dist11,2)+pow(dist12,2)-pow(dist12_3,2))/(2*dist11*dist12)
                    <(pow(dist21,2)+pow(dist22,2)-pow(dist12_3,2))/(2*dist21*dist22)) //余弦判断角度
    
                {
                    pt3=node->pixel;
                }
            }
            node=node->next;
        }
        //LineList
        Linelist *linehead,*linenode,*linelast;
        Line *ln1,*ln2,*ln3;
        linenode=new Linelist;
        linenode->line=new Line;
        linenode->line->pixel1=pt1;
        linenode->line->pixel2=pt2;
        linenode->line->pixel3=pt3;
        linenode->line->flag=false;
        linenode->next=NULL;
        linehead=linelast=linenode;
        ln1=linenode->line;
        linenode=new Linelist;
        linenode->line=new Line;
        linenode->line->pixel1=pt2;
        linenode->line->pixel2=pt3;
        linenode->line->pixel3=pt1;
        linenode->line->flag=false;
        linenode->next=NULL;
        linelast->next=linenode;
        linelast=linenode;
        ln2=linenode->line;
        linenode=new Linelist;
        linenode->line=new Line;
        linenode->line->pixel1=pt3;
        linenode->line->pixel2=pt1;
        linenode->line->pixel3=pt2;
        linenode->line->flag=false;
        linenode->next=NULL;
        linelast->next=linenode;
        linelast=linenode;
        ln3=linenode->line;
        //first Triangle
        Triangle *tglhead,*tglnode,*tgllast;
        tglnode=new Triangle;
        tglnode->line1=ln1;
        tglnode->line2=ln2;
        tglnode->line3=ln3;
        tglnode->next=NULL;
        tglhead=tgllast=tglnode;
    
    
        //expend tin;
        Linelist *linetmp,*linetemp;
        List *pixeltmp;
        float x1,y1,x2,y2,x3,y3;
        linetmp=linehead;
        while(linetmp!=NULL)
        {
            if(linetmp->line->flag==true)
            {
                linetmp=linetmp->next;
                continue;
            }
            ln1=linetmp->line;
            pt1=linetmp->line->pixel1;
            pt2=linetmp->line->pixel2;
            x1=linetmp->line->pixel1->x;
            y1=linetmp->line->pixel1->y;
            x2=linetmp->line->pixel2->x;
            y2=linetmp->line->pixel2->y;
            x3=linetmp->line->pixel3->x;
            y3=linetmp->line->pixel3->y;
    
    
            pixeltmp=list;
            pt3=NULL;
            while(pixeltmp!=NULL)
            {
                if(pixeltmp->pixel==pt1 || pixeltmp->pixel==pt2)
                {
                    pixeltmp=pixeltmp->next;
                    continue;
                }
                if(((y2-y1)*pixeltmp->pixel->x+(x1-x2)*pixeltmp->pixel->y+(x2*y1-x1*y2))
                *((y2-y1)*x3+(x1-x2)*y3+(x2*y1-x1*y2))>=0)
                {
                    pixeltmp=pixeltmp->next;
                    continue;
                }
    
    
                if(pt3==NULL)pt3=pixeltmp->pixel;
                else
                {
                    float dist11=sqrt((pt1->x-pixeltmp->pixel->x)*(pt1->x-pixeltmp->pixel->x)+(pt1->y-pixeltmp->pixel->y)*(pt1->y-pixeltmp->pixel->y));
                    float dist12=sqrt((pt2->x-pixeltmp->pixel->x)*(pt2->x-pixeltmp->pixel->x)+(pt2->y-pixeltmp->pixel->y)*(pt2->y-pixeltmp->pixel->y));
                    float dist12_3=sqrt((pt1->x-pt2->x)*(pt1->x-pt2->x)+(pt1->y-pt2->y)*(pt1->y-pt2->y));
                    float dist21=sqrt((pt1->x-pt3->x)*(pt1->x-pt3->x)+(pt1->y-pt3->y)*(pt1->y-pt3->y));
                    float dist22=sqrt((pt3->x-pt2->x)*(pt3->x-pt2->x)+(pt3->y-pt2->y)*(pt3->y-pt2->y));
                    if((pow(dist11,2)+pow(dist12,2)-pow(dist12_3,2))/(2*dist11*dist12)
                        <(pow(dist21,2)+pow(dist22,2)-pow(dist12_3,2))/(2*dist21*dist22)) //余弦判断角度
                    {
                        pt3=pixeltmp->pixel;
                    }
                }
                pixeltmp=pixeltmp->next;
            }
            if(pt3!=NULL)
            {
                linetemp=linehead;
                flag=false;
                while(linetemp!=NULL)
                {
                    if((pt1==linetemp->line->pixel1 && pt3==linetemp->line->pixel2)
                        || (pt3==linetemp->line->pixel1 && pt1==linetemp->line->pixel2))
                    {
                        linetemp->line->flag=true;
                        flag=true;
                        ln2=linetemp->line;
                        break;
                    }
                    linetemp=linetemp->next;
                }
                if(!flag)
                {
                    linenode=new Linelist;
                    linenode->line=new Line;
                    linenode->line->pixel1=pt3;
                    linenode->line->pixel2=pt1;
                    linenode->line->pixel3=pt2;
                    linenode->line->flag=false;
                    linenode->next=NULL;
                    linelast->next=linenode;
                    linelast=linenode;
                    ln2=linenode->line;
                }
                linetemp=linehead;
                flag=false;
                while(linetemp!=NULL)
                {
                    if((pt2==linetemp->line->pixel1 && pt3==linetemp->line->pixel2)
                        || (pt3==linetemp->line->pixel1 && pt2==linetemp->line->pixel2))
                    {
                        linetemp->line->flag=true;
                        flag=true;
                        ln3=linetemp->line;
                        break;
                    }
                    linetemp=linetemp->next;
                }
                if(!flag)
                {
                    linenode=new Linelist;
                    linenode->line=new Line;
                    linenode->line->pixel1=pt2;
                    linenode->line->pixel2=pt3;
                    linenode->line->pixel3=pt1;
                    linenode->line->flag=false;
                    linenode->next=NULL;
                    linelast->next=linenode;
                    linelast=linenode;
                    ln3=linenode->line;
                }
                tglnode=new Triangle;
                tglnode->line1=ln1;
                tglnode->line2=ln2;
                tglnode->line3=ln3;
                tglnode->next=NULL;
                tgllast->next=tglnode;
                tgllast=tglnode;
            }
    
    
            linetmp->line->flag=true;
            linetmp=linetmp->next;
        }
        TIN=tglhead;
           return TIN;
    展开全文
  • 用DELPHI做的构建Delaunay三角网的程序,可以帮助GIS开发人员掌握构建Delaunay三角网的算法,内附有构建的详细方法说明和程序说明。(Delaunay是一种在离散点序列中快速构造三角形网格的方法,本代码依据的Delaunay...
  • Delaunay三角网的基础上提出了一种高阶Delaunay三角网,并给出了高阶Delaunay三角网生成算法。实验结果表明,高阶Delaunay三角网能够有效地减少地形中局部极小数量,因此,采用高阶Delaunay三角网建立地形模型...
  • Delaunay三角剖分

    千次阅读 2020-09-22 20:43:18
    本课题研究方法主要是以Delaunay三角网的两个重要性质(空外接圆性质和最大最小角度性质)以及Delaunay三角网的基本原理为基础,参照传统算法思路,在构建三角网过程中,改进算法实现方法,数据结构,以达到...

    三角网格化主要有两种准则:一种称为 Delaunay三角剖分,即在生成的三角形网格中,各三角形的最小内角和为最大;另一种是在生成的三角网格中,所有三角形的边长和最小.其中, Delaunay三角剖分是目前研究应用最广的一种剖分方法.本课题的研究方法主要是以Delaunay三角网的两个重要性质(空外接圆性质和最大最小角度性质)以及Delaunay三角网的基本原理为基础,参照传统算法思路,在构建三角网的过程中,改进算法的实现方法,数据结构,以达到提高效率的目的。
    Delaunay的重要性质
     空外接圆性质:在由点集V生成的Delaunay三角网中,每个三角形的外接圆均不包含该点集的其他任意点。l
     最大最小角度性质:在由点集V生成的Delaunay三角网中,所有三角形中的最小角度是最大的,即在生成的三角形网格中,各三角形的最小内角和为最大。l
     唯一性:不论从区域何处开始构网,最终都将得到一致的结果。l
    由于以上特性,决定了Delaunay三角网具有极大的应用价值。Miles证明了Delaunay三角网是“好的”三角网;Lingas进一步论证了“在一般情况下,Delauany三角网是最优的。”同时以上特性也成为建立Delaunay三角网的重要算法依据。
    3.3 详细算法描述
    算法基于上述的传统构建算法,但仅有两步:
    第一步:
    (1) 在离散点集中寻找一纵坐标最小的点A。
    (2) 以点A为起点,寻找两个点B、D,使得向量AB与横坐标轴夹角最小,向量AD与横坐标轴夹角最大。若点A、B、D共线,将原B点标记为A,寻找点D,使得向量AD与直线AB夹角最大;寻找点C使得向量BC与线段AB夹角最小。否则,若A、B、D不共线,则寻找点C使得向量BC与线段AB夹角最小。这样,所有点都在逆时针旋转的折线DABC的左侧。
    (3) 上面一步生成的点C、D如果为同一点,则△ABC(或△ABD)即为包含所有不规则点的Delaunay三角形,生成凸包的过程结束跳过一下各步;否则,继续第四步。
    (4) 寻找一个距离直线AB最远的点E,过E作直线AB的平行线,与射线AD、BC分别交于点D’、C’,将点D’、C’重新标记为点D、C,则凸四边形DABC包括所有不规则点
    (5) 判断△ABC的外接圆是否包含点D,若是则求△ABC的外接圆半径R,在射线BC上距点C2.1R远处取一点D’,并将点D’重新标记为点D,则凸四边形DCBA即为所求得的初始凸包。若△ABC的外接圆不包含点D,则凸四边形DCBA即为所求得的初始凸包。
    第二步:不规则点内插
    在原有Delaunay三角形网的基础上,将其余离散点依次内插,形成Delaunay三角网。该算法原理遵循传统(TSAI)离散点内插算法。
    内插的计算机实现:
    将第一步中形成的初始Delaunay三角形放入Delaunay三角形链表。并建立临时三角形链表,放置新生成的三角形,初始值为空。
    (1) 若没到点集链表的尾端,按顺序取不规则点中的一个点O;将临时三角形链表清空。
    (2) 若Delaunay三角形链表不为空,从该链表中按顺序取一个,称为当前三角形。若为空,转(5)。
    (3) 若当前三角形的外接圆不包含点O,转(2);否则,将当前三角形与临时链表中的所有三角形依次比较,将临时三角形链表中的与当前三角形有公共边的全部删除;并且将当前三角形中的公共边标记出,若当前三角形的公共边数达到3,转(4)
    (4) 将点O与当前三角形的非公共边连接成新的三角形,放入临时三角形链表的尾部,同时从Delaunay三角形链表中删除当前三角形转(2)。
    (5) 判断临时三角形链表是否为空,若否,将临时三角形中的所有三角形全部放入Delaunay三角形链表。

    展开全文
  • 方法提出了一种确定高阶Delaunay三角网中可用 k-OD边的方法,该方法首先在任意边 uv的两侧分别确定两点,使每个点与 uv边形成的三角形的外接圆不包含同侧的点,若这两三角形都为 k-OD三角形,则 uv边是可用 k-OD 边。...
  • 在常规逐点插入算法的基础上,提出了一种改进的逐点插入构建Delaunay三角网的算法。引入散乱点集有序化、三角形单元分类的方法快速生成Delaunay三角网
  • 针对直接在三维空间构建海量点云的Delaunay三角网格效率低下,提出一种新基于映射法的Delaunay三角网格构建算法。首先提出一种基于区域增长法点云分片方法,能够保证对分片后点云数据进行映射而不产生重叠;...
  • 实验结果表明,提出的方法对特征相同多物体同名点实现了快速高精度的匹配,多物体同名点提取以及实时匹配时间约为30 ms,满足相机25 frame/s的实时处理要求,较好地解决了超大三维空间中弧形坡面上随机出现的特征...
  • Delaunay Triangulation方法用于近红外光谱的定量分析,李艳坤,徐恒,Delaunay三角网格(Delaunay triangulation,DT)是一种构建空间网格的方法。本文采用 DT方法在偏最小二乘得分空间中构建网格用于样本相似性�
  • 当输入是所谓“中心良好” Delaunay 三角剖分时,这种广义双网格等效于传统 Voronoi 图。 双网格可用于多种数值方法,通常用作非结构化有限体积或不连续 Galerkin 有限元公式基础。 有关其他信息,请参阅 ...
  • 介绍了散乱数据基于Delaunay三角剖分优化准则和Liang提出相邻扫描线之间三角网格构建方法,并在此基础上提出了一种改进方法,基于优化准则线结构光扫描点云数据三角剖分算法,该算法符合Delaunay三角最优...
  • 分析了现有道路三维模型构建方法,针对其存在不足,提出了一种将道路设计面模型与地形表面模型融为一体模型构建方法,该方法基于在约束Delaunay三角网内插入点和约束边理论,巧妙地解决了剔除落在道路设计面...
  • 不规则三角网 (TIN) 以数字方式来表示表面形态,GIS 社区多年来一直采用此方法。TIN 是基于矢量数字地理数据一种形式,通过将一系列**折点(点)**组成三角形来构建。各折点通过由一系列边进行连接,最终形成一...

    一、什么是 TIN

    不规则三角网 (TIN) 以数字方式来表示表面形态,GIS 社区多年来一直采用此方法。TIN 是基于矢量的数字地理数据的一种形式,通过将一系列折点(点)组成三角形来构建。各折点通过由一系列边进行连接,最终形成一个三角网。形成这些三角形的插值方法有很多种,例如 Delaunay 三角测量法或距离排序法。

    生成的三角测量满足 Delaunay1 三角形准则,从而确保不会有任何折点位于网络中各三角形的外接圆内部即所有的点都是三角形外接圆上的点。如果 TIN 上的任何位置都符合 Delaunay 准则,则所有三角形的最小内角都将被最大化。这样会尽可能避免形成狭长三角形。

    TIN 的各边形成不叠置的连续三角面,可用于捕获在表面中发挥重要作用的线状要素(如山脊线或河道)的位置。在以下两幅图中,图1显示了 TIN 的结点和边,图2显示了 TIN 的结点、边和面。
    在这里插入图片描述在这里插入图片描述
    由于结点可以不规则地放置在表面上,所以在表面起伏变化较大或需要更多细节的区域,TIN 可具有较高的分辨率,而在表面起伏变化较小的区域,可具有较低的分辨率。

    用于创建 TIN 的输入要素与结点或边在 TIN 中位于同一位置。这样,TIN 便能够在对已知点之间的值进行建模的同时保持输入数据的所有精度。可以在表面上包括精确定位的要素(如山峰、道路及河流),方法是将其用作 TIN 结点的输入要素。

    TIN 的单位应该为英尺或米,而非十进制度。当使用地理坐标系的角度坐标进行构建时,Delaunay 三角测量无效。

    TIN 模型的适用范围不及栅格表面模型那么广泛,且构建和处理所需的开销更大。获得优良源数据的成本可能会很高,并且,由于数据结构非常复杂,处理 TIN 的效率要比处理栅格数据低。

    TIN 通常用于较小区域的高精度建模(如在工程应用中),此时 TIN 非常有用,因为它们允许计算平面面积、表面积和体积。

    TIN 的最大允许大小视连续的可用内存资源而定。对于 Win32 系统而言,正常操作条件下,可达到的最大大小为 1000 到 1500 万个结点。出于可用性和性能的考虑,强烈建议始终将此大小限制为几百万。如果超出这一大小,则最好使用 terrain 数据集来表示。

    由于结点可以不规则地放置在表面上,所以在表面起伏变化较大或需要更多细节的区域,TIN 可具有较高的分辨率,而在表面起伏变化较小的区域,则可具有较低的分辨率。

    二、TIN 表面的基础知识

    不规则三角网 (TIN) 表面可由表面源测量值生成,也可由另一功能性表面转换而来。

    可以由包含高程信息的要素(如点、线和面)来创建 TIN 表面。使用点作为高程数据的点位置。使用具有高度信息的线来强化自然要素,例如,湖泊、河流、山脊和山谷。最后,使用面将 TIN 裁剪为适合您研究区域的大小。

    也可以由其他功能性表面(如栅格数据集或 terrain 数据集)创建 TIN 表面。可能希望将栅格表面转换为 TIN,以便向表面模型添加更多要素(如河流和道路)。要将栅格数据集转换为 TIN,可以使用栅格转 TIN 地理处理工具。

    处理多分辨率 terrain 数据集时,可能需要将 terrain 数据集的一部分转换为 TIN 表面,以特定的金字塔等级来处理这一小部分感兴趣区域。要将 TIN 转换为 terrain 数据集,可以使用 Terrain 转 TIN 地理处理工具。另外,基于文件的 TIN 具有实际的大小限制。TIN 的最大允许大小视连续的可用内存资源而定。对于 Win32 系统而言,正常操作条件下,可达到的最大大小为 1000 到 1500 万个结点。出于可用性和性能的考虑,强烈建议始终将此大小限制为几百万。如果超出这一大小,则最好使用 terrain 数据集来表示。

    多个不同的矢量数据源可构成一个 TIN 表面。在 TIN 表面设计过程中,为 TIN 中的每个数据源建立角色并确定每个数据源的使用方式。

    下面是对可用于构建 TIN 表面的表面要素类型的简要:

    2.1 离散多点

    离散多点是点高度测量;它们将作为 TIN 网中的结点。离散多点是 TIN 中的主要输入要素,由它们来决定表面的总体形状。

    通过在表面变化程度较大的区域包括较多的离散多点,而在表面变化程度较小的区域包括较少的离散多点,可以利用 TIN 对非均匀表面进行有效建模。以下示例显示了按高度属性分类的离散多点。
    在这里插入图片描述

    2.2 隔断线和多边形 (hull)

    隔断线(如下所示)是具有或不具有高度测量值的线。这些隔断线会成为一条或多条三角形边的序列。隔断线通常用于呈现自然要素(如山脊线或河流)或建筑要素(如道路)。隔断线有以下两种:硬隔断线与软隔断线。
    在这里插入图片描述

    2.2.1 硬隔断线

    硬隔断线用于表示表面坡度的不连续性。河流和道路断面可作为硬隔断线包括在 TIN 中。硬隔断线能够捕获表面的突变并能改进 TIN 的显示和分析质量。

    2.2.2 软隔断线

    软隔断线用于向 TIN 添加边,以捕获不会改变表面局部坡度的线状要素。研究区域边界可作为软隔断线包括在 TIN 中,以在不影响表面形状的情况下捕获它们的位置。

    2.2.3 多边形 (Hull)

    面用于表示具有面积的表面要素(如湖泊)或具有单独插值区域边界(外壳)的表面要素。多边形 (Hull) 可定义群岛中各个岛屿的海岸或研究区域的边界。

    2.3 多边形表面要素类型

    有以下四种多边形表面要素类型:

    • 裁剪多边形插值,用于定义 TIN 表面的边界。位于裁剪多边形之外的输入数据将从插值和分析操作(例如,等值线或体积计算)中排除。
      在这里插入图片描述
    • 擦除多边形,用于定义插值的边界。位于擦除多边形之内的输入数据将从插值和分析操作(例如,等值线或体积计算)中排除。
    • 替换多边形,用于将边界及所有内部高度设置为相同的值。替换多边形可用于对湖泊或者坡度挖掘到水平面以下的区域进行建模。
    • 填充多边形,用于将一个整数属性值分配给位于此填充多边形内部的所有三角形。表面高度不受影响,并且不发生裁剪或擦除操作。

    多边形要素作为三个或多个三角边的封闭序列集成到三角测量中。通过在 TIN 中使用隔断线和面,可以更好地控制 TIN 表面的形状。下面是使用离散多点创建的表面与同时使用离散多点和隔断线创建的表面进行了比较。图1显示了使用离散多点创建的 TIN;图2显示了使用离散多点和隔断线创建的同一区域的 TIN。
    在这里插入图片描述
    在这里插入图片描述

    2.4 高度源

    如果地理要素关联有 z 值,可以将 z 值包括到 TIN 表面中。例如,用于表示隔断线的线要素,它们有助于进一步定义 TIN 表面。隔断线通常有一个高程值与线图层中的每个折点相关联。如果要素启用了 3D,则高度源/字段将包含以单独属性表示的形状或要素 z 值。

    2.5 表面要素类型 (SF_type)

    表面要素类型能够帮助定义 TIN 表面以及根据与输入要素的矢量类型关联的行为对输入要素进行分类。例如,只能以离散多点的形式添加点。不过,线要素可描述为硬断线或软断线,面要素可以是硬裁剪、软裁剪、硬替换、软替换、硬擦除、软擦除、硬值填充或软值填充。

    线和面要素类型的硬和软限定词用于指示其位置处的表面坡度是否发生明显中断。硬断线表示坡度发生明显中断,而软断线将表示表面上坡度的变化较平缓。

    离散多点以单个结点的形式添加到 TIN 中
    在这里插入图片描述
    在三角测量中,以一系列三角边的形式强化隔断线。将根据需要添加 Steiner、增密点,以符合 Delaunay 三角测量的规则。
    在这里插入图片描述
    裁剪多边形用于描绘 TIN 的数据区或插值区。其边界在三角测量中将强化为隔断线。落在多边形之外的三角形将被掩膜。在进行插值时,这些三角形会变为 NoData。擦除多边形也会影响 TIN 的数据区。其边界在三角测量中将强化为隔断线。这样,落在多边形内部的三角形将被掩膜。替换多边形用于定义平坦区域。其边界在三角测量中强化为恒定高度的隔断线。多边形内部所有结点的 z 值均设置为同一个常数。
    在这里插入图片描述

    2.6 标签值

    标签值填充多边形将简单形式的整数属性值分配给三角形。其边界在三角测量中将强化为隔断线。这些面内部的三角形会将标签值作为属性。标签以有符号长整型数据形式存储。三角形标签代表用户定义的有关区域的条件。例如,土地覆盖代码。随后,可通过基于这些标签对三角形进行符号化的方式来渲染 TIN。“识别”工具也会报告它们的值。


    1. https://baike.baidu.com/item/Delaunay%E4%B8%89%E8%A7%92%E5%89%96%E5%88%86%E7%AE%97%E6%B3%95/3779918?fr=aladdin ↩︎

    展开全文
  • 现在的问题是,虽然现有的方法能够满足曲线曲面连续性和插值的要求,但是这些方法往往不能产生令人满意的形状,或者使现有的图形得到改善。在本研究中,我们使用了一种新的三角Gregory面片。它是在四边形Gregory面片...
  • 基于约束Delaunay三角网构建理论,建立了外形与内部拓扑关系均为整体道路三维模型。提出了顾及道路约束边界半边折叠误差度量方法,采用半边折叠操作,在服务器端对道路模型进行整体简化,并建立操作层次树存储...
  • 不规则三角网是DEM建模中最常用一种...本文以城市水系为例,在研究TIN构建过程中约束条件和Delaunay三角网的基础上,通过加入阻断点作为约束边界方式,来控制三角网的构建过程,从而建立符合现实情况城市水系DEM。
  • 然后利用Delaunay三角网构建建筑群邻近关系,生成邻近图;考虑直线模式直线性、紧凑性等,通过模拟直线模式识别人工过程进行邻近图同质性修剪,识别出多连通直线模式。实验表明,该方法能够识别出明显直线...
  • 针对现有岩层面三维建模方法未系统考虑含断层、陷落柱等地质条件的复杂岩层面三维模型构建的问题,通过定义投影度和投影单元,给出了不同地质条件下岩层面水平投影单元特征,同时提出一种基于单元划分的复杂岩层面三维...
  • Voronori图建立

    2017-07-26 20:18:05
    建立Voronoi图方法和步骤 实验采用是Delaunay三角剖分算法。主要是指生成Voronoi图时,先生成其对偶元Delaunay...建立Voronoi图算法关键是对离散数据点合理地连成三角网,即构建Delaunay三角网。  建立Vorono

空空如也

空空如也

1 2 3
收藏数 43
精华内容 17
关键字:

delaunay三角网构建的方法