三维不规则三角网格的精确裁剪算法

给出了一种基于约束Delaunay三角剖分的三维不规则三角网格的精确裁剪算法。算法结合TIN数据的生成特点,首先将TIN投影到二维平面,然后利用约束Delaunay三角剖分把裁剪多边形的每条边嵌入三角网中,再利用边-三角形的拓扑关系删除裁剪多边形外部多余三角形,最后利用边-点的拓扑关系对裁剪多边形顶点高程进行插值,使生成裁剪后的TIN模型。对不同复杂程度的三维TIN模型进行裁剪实验,发现二维投影策略极大地提高了三维TIN裁剪效率。算法的程序实现简单,且符合工程需求。     

一种建筑物多边形合并、化简与优化的自动方案

介绍了一种城市地图中基于建筑物矩形几何特征的多边形全自动综合算法。采用Delaunay三角网探测多边形之间的拓扑邻近关系，根据视觉邻近关系聚合多边形。采用基于分割栅格多次扫描的方法对建筑物多边形进行化简以及形状优化。     

基于有向弧的改进多边形拓扑关系生成算法

文章提出了一种基于有向弧段的多边形拓扑关系生成算法,改进了传统算法.算法对每个结点的关联孤段按方位角排序并对这种有序性进行了补充定义,同时为弧段增加两个方向相关的字段,分别表示弧段的方向和是否被遍历过,搜索多边形的同时对遍历过的有向孤段加以标记.本算法避免了多边形的反复搜索和内角的计算,提高了建立多边形拓扑关系的效率.最后,时该算法进行了分析和实例计算.     

二维Delaunay三角网的动态更新

对于三角格网的动态更新，提出了一种对称边双循环链表结构，提供了如何实现这种结构，如何创建三角形，动态插入和删除点等操作的代码和伪码实现。该结构具有理解容易、操作简单、使用内存少的特点，能够快速地查找和维护三角网的拓扑结构，并且可根据实际需求进行扩充。     

基于Delaunay三角网的城市多边形合并算法

多边形合并是建筑物群综合的一个重要环节，而邻近关系是该合并过程的重要依据，利用Delaunay三角网生成拓扑信息，根据多边形之间的最小距离来判断是否聚合。因为多边形之间的最小距离总小于等于其间的三角网的最小边长，使建筑物多边形的合并更加精确和美观。     

一种改进的非流形点转化算法

实际建模过程中,经常会遇到非流形的多边形表面,但很多现有的图形学算法都是基于流形结构的。因此,可以将非流形结构转化为几何外观上与之逼近的流形结构。对于这种转化,包括非流形边和非流形点的修改。由于非流形边的转化问题已被较好的解决,因此,对非流形点的转化进行了研究,并提出了一种新算法修改非流形点。与现有算法相比：该算法不但可以得到拓扑上分离的流形结构而且可以得到拓扑上连通的流形结构,更符合一般建模用户的需要。     

新的关键字提取算法研究

传统的关键字提取算法往往是基于高频词提取的,但文档中的关键字往往并不都是高频词,因此还需要从非高频词集中找出关键字.把一篇文档抽象为一个图:结点表示词语,边表示词语的同现关系;并基于文档的这种拓扑结构,提出了一种新的关键字提取算法,并和传统的关键字提取算法作了比较,在精确率,覆盖率方面均有不错的效果.     

基于分割插值的连续多分辨率模型

给出了一种基于边删除的多边形网格分辨率模型生成算法,通过递归地删除网格模型中的边,从而得到连续的简化模型.算法建立了可调加权控制函数来控制边的简化顺序.在模型简化的不同阶段,通过调节控制函数的权值执行不同的简化原则,使得视觉重要度低的边优先删除.此外,通过建立独立集,避免了模型的局部过度简化.算法用临近点插值模板,求取边简化生成的新点.实验结果表明,该算法可实现较理想的场景简化效果.     

以优先点为中心的Delaunay三角网生长算法

目的 Delaunay三角网具备的优良性质使其得到广泛的应用,构建Delaunay三角网是计算几何的基础问题之一,为了高效、准确地构建大规模点集的Delaunay三角网,提出一种基于优先点的改进三角网生长算法.方法 算法以逆时针次序的一条凸包边为初始基边,使用基边对角最大化并按照逆时针次序选定第3点构建一个Delaunay三角形,通过待扩展边列表中的数据判断新生成的两条边是否需要扩展,采用先进先出的方式从待扩展边列表中取边作为基边,以优先点为中心构建局部Delaunay三角网使优先点尽快成为封闭点,再从点集中删除此封闭点.结果 对于同一测试点集,改进算法运行时间与经典算法运行时间的比率不超过1/3,且此比率随点集规模增长逐步下降.相比经典算法,改进算法在时间效率上有较大提升.结论 本文改进算法对点集规模具有较好的自适应性与较高的构网效率,可用于大规模场景下Delaunay三角网的构建.     

基于边方向角长度表示的多边形方向、凹凸性及点包含算法

提出矢量边方向角的长度表示概念,用于解决多边形方向识别、顶点凹凸性识别和点包含判断三个问题.给出了基于矢量边方向角长度概念描述多边形边方向角的单调连续函数,当方向角从0°增加到360°时,函数值从0增加到8,该函数可以准确地表达多边形中边矢量的方向角,也可以准确地表达待检测点与多边形顶点连线所形成矢量的方向角.建立了基于矢量边方向角长度概念的多边形相邻边左右侧走向关系判定规则.该规则可用于判定相邻边方向关系,实现多边形方向识别和顶点凹凸性识别;计算待检测点与多边形顶点连线之间所夹有向边方向角长度和,实现点包含判断.给出了三个问题的实现算法,该算法与目前最优算法复杂度相同,但计算量较最优算法少1次乘除类运算,同时保证了高可靠性、稳定性和执行效率.实现了三个问题解决方法在几何概念上的统一,而在其他同类算法中几何概念是相互独立的.     

基于三角形法向量的离散点三维构网方法

构建平面不规则三角网的算法已经很成熟,但普遍的算法都是基于某一投影平面,不能满足三维空间离散点的构网要求。本文在研究二维构网生长算法及现有 空间三维构网方法的基础上,提出利用空间三角形的法向量实现三维构网,详细讨论该算法的细节问题,并探讨提高构网速度的方法。通过实验证明该算法能快速、 有效、稳定地对复杂物体表面离散点构建空间三角网,达到建模效果,同时也体现出其应用范围的广阔性。     

基于LiDAR点云数据的三角网构建算法

在现有Delaunay三角网生长法的基础上进行改进,提出了一种三角网生长算法.该算法对大规模点云进行等格网分块,自适应确定搜索范围.通过在构建过程中对生成的基线进行分组和排序,动态删除封闭点,提高了构建三角网的速度;通过在整个点集范围内进行搜索,避免了通过插值所产生的误差和模块之间的拼接过程.利用此算法对大规模LiDAR点云数据进行构网,结果表明了该算法的有效性.     

一种基于四叉树的TIN的LOD算法

通过在不规则采样点集上构建一个四叉树结构，并联合基于四叉树的LOD算法和基于TIN的三角网简化算法，提出并实现了一种TIN的LOD算法。意在把适用于格网数据的高效方法应用于不规则采样点集，得到地形的一个高效的多分辨率表达。     

Expression and Visualization of Cloverleaf Junction in a 3-Dimensional City Model

Seldom research work has been conducted on cloverleaf junction expression in a 3-dimensional city model (3DCM). One apparent reason is that the cloverleaf junction is often in a complex and enormous construction. Its main body is bestraddle in air, and has aerial intersections between its parts. This complex feature makes cloverleaf junctions quite different from buildings and terrain, it is therefore difficult to express this kind of spatial objects in the same way as for buildings and terrain. In this paper, authors analyzed spatial characteristics of cloverleaf junction, proposed an all-constraint points triangulated irregular network (TIN) algorithm to partition cloverleaf junction road surface, and developed a method to visualize cloverleaf junction road surface using TIN. Accordingly, an appropriate data structure for cloverleaf junction is proposed.     

Building a water feature extraction model by integrating aerial image and lidar point clouds

An innovative model for extracting water regions from aerial images fused with light detection and ranging (lidar) data is proposed in this article. This model extracts water features from coarse to fine levels of accuracy by considering special spectral bands of existing airborne lidar systems and their spectral characteristics. The particular model consists of two parts, namely inexact water region recognition and precise water extraction. (1) A strategy of using a triangulated irregular network (TIN) is introduced to describe point clouds with a particular structure. A TIN coarsely divides the network into water and non-water regions through a threshold, which can be determined through an equation by inputting the minimum width and point density of water regions. The coarsely defined water region can be detected through overlay analysis between the aerial image and the raster surface generated from the TIN. (2) An improved mean-shift algorithm is used to remove most land pixels from the roughly recognized water to obtain precise water edges from coarse water. A new empirical formula to describe distance between multi-dimensional data is adopted. Using the mean-shift algorithm and empirical distance function, accurate water edge features are extracted from inexact water region(s). In addition, the classification field of lidar point clouds is used to remove land pixels from water features.

A case study based on a point cloud data set and an aerial image is conducted to evaluate the feasibility and accuracy of the proposed model. Spatial distances between checkpoints and extracted water edges, as well as the confusion matrix of mean-shift classification, are adopted as measurements of accuracy for the extracted water edges in two case regions. Evaluation results show that the proposed model achieved continuous water-edge features, and that spatial accuracy of water edges is 0.3 to 0.4 m, at approximately the 1–2-pixel level, which is more than four times better than the maximum-likelihood classification method. General accuracy of the confusion matrix shows that mean-shift classification in the proposed model is better than 95%, which indicates excellent results.     

Multiresolution indexing of triangulated irregular networks

We show how to build a continuous, one-dimensional index of the points on a triangulated irregular network (TIN). The index is constructed by first finding an ordering of the triangles in which consecutive triangles share a vertex or an edge. Then, the space within each triangle is continuously indexed with a space-filling curve that begins at one vertex of the triangle and ends at another. The space-filling curve is oriented such that the first point in each triangle is a vertex shared with the previous triangle and the last point is a vertex shared with the next triangle. Furthermore, our index can be refined locally and, therefore, efficiently when the TIN is augmented by filling any face with another TIN (to make a hierarchical TIN). Such processes arise, for example, in the elaboration of detail on a graphical surface.     

TIN generation and point-cloud compression for vehicle-based mobile mapping systems

The vehicle-based mobile mapping system (MMS) is effective for capturing dense 3D data of roads, roadside objects and buildings. Since discrete points are not convenient for many application systems, a triangulated irregular network (TIN) is often generated from point-clouds. However, TIN data require two or three times larger storage than point-clouds. If TIN models can be promptly generated while loading point-clouds, it would not be necessary to store huge TIN models on a hard disk. In this paper, we propose two efficient TIN generation methods according to types of laser scanners. One is the line-by-line TIN generation method, and the other is the GPS-time based method. These methods can quickly generate TIN models based on scan lines of laser scanners. In addition, we introduce a new compression method to reduce the loading time of point-clouds. Our compression method is also based on the scan lines of laser scanners. Since points captured by a MMS tend to be positioned on nearly straight lines, their data size can be significantly reduced by coding the second order differences.     

基于不规则三角网构建的网格生长算法

提出一种基于离散点Delaunay三角网快速构建的网格生长算法,采用分治算法将离散点表达为唯一网格,利用稀疏矩阵完成网格数据的压缩存储,通过标识码实现有值单元格与离散点之间的高效检索,从而提高网格构建的效率。依据有值单元格的密度获取预设正方形搜索空间,并在三角网扩展时根据需要动态建立正方形搜索空间,从而保证网格生长的准确性。实验结果表明,该算法的时间复杂度为O(nlogn),对于少量或海量离散点均具有较好的适应性。     

基于可见性约束的自动表面重构算法研究

提出了一种基于可见性约束的自动表面重构算法.此算法首先介绍了一种通过插入法实现的3维Delaunay三角网自动重构算法,然后利用给定的离散点,构建包围所有点的凸包.在完成初始的Delaunay三角剖分基础上,提出了利用特征点在影像中的可见性信息,对初始的3维模型进行修正,从而得到物体的实际表面模型.实验结果表明,该方法是有效的.     

基于几何元素的城市三维地理信息系统空间数据模型

空间数据模型是城市三维地理信息系统建立的核心问题。基于不同的城市空间对象划分方法,提出了城市三维地理信息系统的十八个空间数据模型:把空间现象抽象为六类对象:点对象、线对象、规则面对象、规则体对象、不规则对象和DTM,基于六种几何元素(点、直线段、多边形、函数构造面、TIN面片、规则体素)的不同组合,提出了城市三维地理信息系统的九个空间数据模型;把空间现象抽象为五类对象:0维空间对象(点对象)、一维空间对象(线对象)、二维空间对象(面对象)、三维空间对象(体对象)和DTM,基于六种几何元素的不同组合提出了八个空间数据模型;把空间现象抽象为0维对象(点对象)、一维对象(线对象)、二维对象(面对象)、三维对象(体对象)、DTM,基于点、直线段、TIN面片、多边形、规则面、不规则面六类几何元素提出了一个空间数据模型。通过对一个数据模型的实验验证和各模型的理论分析,表明了模型的特点及可行性。