共查询到20条相似文献，搜索用时 488 毫秒
1.
不规则三角网(TIN)可以逼真的模拟地形表面,因此被广泛应用于地学领域。Delaunay三角剖分算法是构建TIN网的最优算法,该文对传统Delaunay三角网构建算法进行分析,提出了一种针对大规模离散数据点生成TIN的高效合成算法。该算法首先根据离散点的分布位置和密度对其进行四叉树区域划分;然后以每个叶子节点的边界四边形为凸包,采用逐点插入法构建三角网;最后采用顶点合并法自底向上合并具有相同父节点的4个子节点,生成Delaunay三角网。实验结果表明,该算法时间复杂度较低,有效提高了TIN网的构建效率。 相似文献
2.
Kai Wang Chor-Pang Lo George A. Brook Hamid R. Arabnia 《International journal of geographical information science》2013,27(8):743-762
Over the last two decades, the Delaunay triangulation has been the only choice for most geographical information system (GIS) users and researchers to build triangulated irregular networks (TINs). The classical Delaunay triangulation for creating TINs only considers the 2D distribution of data points. Recent research efforts have been devoted to generating data-dependent triangulation which incorporate information on both distribution and values of input data in the triangulation process. This paper compares the traditional Delaunay triangulations with several variant data-dependent triangulations based on Lawson's local optimization procedure (LOP). Two USGS digital elevation models (DEMs) are used in the comparison. It is clear from the experiments that the quality of TINs not only depends on the vertex placement but also on the vertex connection. Traditonal two step processes for TIN construction, which separate point selection from the triangulation, generate far worse results than the methods which iteratively select points during the triangulation process. A pure data-dependent triangulation contains a large amount of slivers and steep triangles, which greatly affect the quality of TINs constructed. Among the triangulation methods tested, the classical Delaunay triangulation is still the most successful technique for constructing TINs for approximating natural terrain surfaces. 相似文献
3.
Sunghwan Cho M. Xavier Punithan Jonggun Gim 《International journal of geographical information science》2014,28(12):2533-2550
In spatial data sets, gaps or overlaps among features are frequently found in spatial tessellations due to the non-abutting edges with adjacent features. These non-abutting edges in loose tessellations are also called inconsistent boundaries or slivers; polygons containing at least one inconsistent boundary are called inconsistent polygons or sliver polygons. The existing algorithms to solve topological inconsistencies in sliver polygons suffer from one or more of three major issues, namely determination of tolerances, excessive CPU processing time for large data sets and loss of vertex history. In this article, we introduce a new algorithm that mitigates these three issues. Our algorithm efficiently searches the features with inconsistent polygons in a given spatial data set and logically partitions them among adjacent features. The proposed algorithm employs the constrained Delaunay triangulation technique to generate labelled triangles from which inconsistent polygons with gaps and overlaps are identified using label counts. These inconsistent polygons are then partitioned using the straight skeleton method. Moreover, each of these partitioned gaps or overlaps is distributed among the adjacent features to improve the topological consistency of the spatial data sets. We experimentally verified our algorithm using the real land cadastre data set. The comparison results show that the proposed algorithm is four times faster than the existing algorithm for data sets with 200,000 edges. 相似文献
4.
二维Delaunay三角网的任意点删除算法研究 总被引：1，自引：0，他引：1
针对目前基于影响域多边形剖分的点删除算法缺陷,提出一种二维Delaunay三角网点删除算法。首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成点的删除,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。 相似文献
5.
三维含拓扑地质剖面三角剖分可视化研究 总被引：1，自引：0，他引：1
三维剖面是地质对象表达和地质问题分析中最基本和最常用的数据。该文分析三维复杂地质折剖面可视化存在的问题,并提出展开剖分算法。该方法保证了各点之间的水平距离与剖面拓扑关系不变,能够对由"多边形-弧段-结点"矢量结构构成的三维折剖面进行有效剖分。在此基础上实现了三维剖面的可视化,尤其合理解决了纹理映射中的纹理变形与重复接缝等问题。 相似文献
6.
E.G. Paredes M. Amor M. Bóo J.D. Bruguera J. Döllner 《International journal of geographical information science》2016,30(6):1095-1116
Hybrid terrain models combine large regular data sets and high-resolution irregular meshes [triangulated irregular network (TIN)] for topographically and morphologically complex terrain features such as man-made microstructures or cliffs. In this paper, a new method to generate and visualize this kind of 3D hybrid terrain models is presented. This method can integrate geographic data sets from multiple sources without a remeshing process to combine the heterogeneous data of the different models. At the same time, the original data sets are preserved without modification, and, thus, TIN meshes can be easily edited and replaced, among other features. Specifically, our approach is based on the utilization of the external edges of convexified TINs as the fundamental primitive to tessellate the space between both types of meshes. Our proposal is eminently parallel, requires only a minimal preprocessing phase, and minimizes the storage requirements when compared with the previous proposals. 相似文献
7.
为实现大规模地形的多分辨率显示与实时绘制,基于LOD技术给出了多尺度TIN的管理和表达算法。探讨该算法相关的数据组织、LOD层次表达、实时刷新等关键问题。该算法使用分级策略,在不影响视觉效果前提下对TIN进行分级表达;使用分区策略,在可视化过程中对TIN进行局部更新。采取不同分辨率TIN模型间逐步过渡策略,基本上消除了视图变换时的跳跃感。实验结果表明,这种紧凑有效的TIN表示方法实现简单,内存开销较少,CPU耗费小,大大缩短了视图刷新切换时间,能够在普通机器上实现大规模地形的实时漫游。 相似文献
8.
基于SPIHT小波的DEM自适应压缩方法研究 总被引：1，自引：0，他引：1
海量地形数据给其存储、分发和实时渲染带来了极大的挑战,因此迫切需要适合网络环境下地形可视化的数据压缩方法。该文探讨地形复杂度与DEM压缩方法的关系,研究可视化中地形复杂度的计算方法,并提出一种改进的SPIHT小波压缩方法:采用小波分解后的系数对DEM的地形复杂度进行评估,并针对地形复杂度对编码算法进行自适应调节。实验证明,这种改进的SPIHT小波压缩方法采用合适的压缩比进行DEM数据压缩,能够在满足地形可视化需要的同时提高压缩效率。 相似文献
9.
MAHDI ABDELGUERFI CHRIS WYNNE EDGAR COOPER LADNER ROY 《International journal of geographical information science》2013,27(8):853-873
3-D terrain representation plays an important role in a number of terrain database applications. Hierarchical Triangulated Irregular Networks (TINs) provide a variable-resolution terrain representation that is based on a nested triangulation of the terrain. This paper compares and analyzes existing hierarchical triangulation techniques. The comparative analysis takes into account how aesthetically appealing and accurate the resulting terrain representation is. Parameters, such as adjacency, slivers, and streaks, are used to provide a measure on how aesthetically appealing the terrain representation is. Slivers occur when the triangulation produces thin and slivery triangles. Streaks appear when there are too many triangulations done at a given vertex. Simple mathematical expressions are derived for these parameters, thereby providing a fairer and a more easily duplicated comparison. In addition to meeting the adjacency requirement, an aesthetically pleasant hierarchical TINs generation algorithm is expected to reduce both slivers and streaks while maintaining accuracy. A comparative analysis of a number of existing approaches shows that a variant of a method originally proposed by Scarlatos exhibits better overall performance. 相似文献
10.
11.
12.
Montserrat Bóo Margarita Amor 《International journal of geographical information science》2013,27(4):417-439
Hybrid digital terrain models combine terrain data with different topologies and resolutions. Cartographic digital terrain models are typically composed of regular grid data that can be locally refined by adding a Triangulated Irregular Network (TIN) that represents morphologically complex terrain parts. Direct rendering of both datasets to visualize the digital terrain model generates discontinuities, as the meshes are disconnected. The utilization of complete/partial precomputed tessellation solutions solves the problem of quality, but limits the applicability of the representation to models with a fixed relative position between datasets. In this paper, we present a new scheme for hybrid terrain representation that permits the dynamic generation of the adaptive tessellation required to join the grid and TIN models. Our proposal permits the dynamic modification of the relative position between datasets. This increases the representation capabilities for those applications where this property is interesting as, for example, urban and landscape planning applications. The algorithm we propose is based on the identification of convex areas on the TIN and the efficient generation of triangles to join the models based on this convex structure. As a result, high quality models without discontinuities are obtained, increasing the flexibility of previous solutions based on fixed precomputations. 相似文献
13.
大规模地形实时绘制算法 总被引：8，自引：3，他引：5
该文提出一种适合大规模地形实时绘制的简单高效的LOD简化算法。该算法使用一种紧凑有效的规则网格表示方法,优化网格节点的数目,减少可视化过程中的计算量,降低额外内存开销。探讨该算法相关的数据组织、视域裁剪、LOD层次选择、裂缝消除、三角形化等关键问题。实验结果表明,该算法实现简单,内存开销较少,CPU耗费小,对图形卡要求低,能够在普通机器上实现大规模地形的实时漫游。 相似文献
14.
B. Yang W. Shi Q. Li 《International journal of geographical information science》2013,27(10):1019-1038
Multi‐resolution terrain models are an efficient approach to improve the speed of three‐dimensional (3D) visualizations, especially for terrain visualization in Geographical Information Systems (GIS). As a further development to existing algorithms and models, a new model is proposed for the construction of multi‐resolution terrain models in a 3D GIS. The new model represents multi‐resolution terrains using two major methods for terrain representation: Triangulated Irregular Network (TIN) and regular grid (Grid). In this paper, first, the concepts and formal definitions of the new model are presented. Second, the methodology for constructing multi‐resolution terrain models based on the new model is proposed. Third, the error of multi‐resolution terrain models is analysed, and a set of rules is proposed to retain the important features (e.g. boundaries of man‐made objects) within the multi‐resolution terrain models. Finally, several experiments are undertaken to test the performance of the new model. The experimental results demonstrate that the new model can be applied to construct multi‐resolution terrain models with good performance in terms of time cost and maintenance of the important features. Furthermore, a comparison with previous algorithms/models shows that the speed of rendering for 3D walking/flying through has been greatly improved by applying the new model. 相似文献
15.
二维Delaunay三角网局部更新:点插入与点删除 总被引：16，自引：3，他引：13
二维Delaunay三角网的局部更新在地学分析、道路CAD、城市规划等领域有着广泛的用途,点插入和点删除则是其中最重要、最基本的操作。该文针对原有逐点插入法和凸耳权值点删除算法存在的不足,利用动态包围三角形和特征三角形分别对其进行改进,在设计的具有拓扑关系Delaunay的三角网数据结构基础上,实现Delaunay三角网的快速局部更新,且使之满足Delaunay特性。最后通过模拟实验验证了算法的正确性和高效性。 相似文献
16.
Narcís Coll Marité Guerrieri 《International journal of geographical information science》2017,31(7):1467-1484
In this paper, we propose a new graphics processing unit (GPU) method able to compute the 2D constrained Delaunay triangulation (CDT) of a planar straight-line graph consisting of points and segments. All existing methods compute the Delaunay triangulation of the given point set, insert all the segments, and then finally transform the resulting triangulation into the CDT. To the contrary, our novel approach simultaneously inserts points and segments into the triangulation, taking special care to avoid conflicts during retriangulations due to concurrent insertion of points or concurrent edge flips. Our implementation using the Compute Unified Device Architecture programming model on NVIDIA GPUs improves, in terms of running time, the best known GPU-based approach to the CDT problem. 相似文献
17.
Mengyun Zhou Jianya Gong 《International journal of geographical information science》2016,30(11):2208-2229
Polygonal vector data are important for representing countries, lakes, residential settlements, and other polygonal features. The proper representation of polygonal vector data is the basis of efficient rendering and picking and quick access and display of the analysis results based on polygons (e.g., 3D overlaying and surface area measurement in mountainous areas) in a virtual globe. However, polygonal vector data are displayed using texture-based or boundary-based approaches in most existing virtual globes. The texture-based approach cannot easily support interactive operations (e.g., picking) and spatial analysis (e.g., adjacency analysis and spatial measurement). The boundary-based approach treats the holes as independent features; however, it is difficult to recognize which boundaries constitute a polygon. Further research is needed on how to better organize the polygons to support efficient rendering, picking, and analysis in a virtual globe. In this article, we propose two methods to drape interior filled 2D polygons onto a multi-resolution 3D terrain. Both proposed methods combine polygon clipping and polygon triangulation. The difference between the two methods is in the way holes are eliminated. Method 1 recursively subdivides a terrain triangle until the child-triangles contain no holes; every resulting clipped polygon, which is then triangulated, contains no holes. Method 2 directly clips a polygon against a terrain triangle and creates bridge edges to transform the resulting polygons with holes to degenerate polygons that are further triangulated. The experimental results demonstrate that both proposed methods can efficiently process polygons with holes resulting in appropriate numbers of triangles. The processed interior-filled polygons remain close to the terrain surface in a virtual globe. Both proposed methods support real-time rendering of polygonal vector data in a virtual globe. 相似文献
18.
Jingsong Wu Kevin Amaratunga 《International journal of geographical information science》2013,27(3):273-289
GIS applications have recently begun to emerge on the Internet. The management of three-dimensional geographic datasets in this distributed environment poses a particularly challenging problem, which highlights the need for a good data representation. This paper presents a new multiresolution data representation: the Wavelet Triangulated Irregular Network (WTIN). Compared to the traditional cell-based Digital Elevation Model (DEM) format and the Triangulated Irregular Network (TIN) format, it is more compact and suitable for scalable distributed GIS services. This format is based on the second-generation wavelet theory and is specially designed for geographical height field data. The modified Butterfly scheme is used for constructing the wavelet transform. For every point in the geographic surface, only a single wavelet coefficient is used, which makes the final data representation very efficient and easy to compress. Because the transform used in the data representation is a linear filter operation, the computational efficiency is better than other multiresolution data formats for terrain surfaces. Results from numerical experiments on real data are given to demonstrate that the proposed data representation can be efficiently implemented. The results show that the proposed WTIN data format can provide multiresolution data sets, which achieve significant compression while preserving geographical features. The quality is found to be quite acceptable for geographical terrain representation. 相似文献
19.
Recently, the Chinese government raised an urban planning policy which suggests communities open their private roads for public transport and establish street networks with high spatial density in cities. In this context, the purpose of this study is to analyze the potential changes to street network accessibility using GIS techniques and to provide spatial information that may influence the decision making of urban managers. In addition to the existing street network data in the case study city, Shenzhen, intra-community roads are extracted from building footprints in GIS topographic database and used to construct a potential street network with respect to the community opening policy. An automatic GIS-based method is proposed here to analyze the location advantage information in the simulated urban environment, by combining Delaunay triangulation model and graph theory concepts. Specifically, we establish a two-step framework based on the spatial relationships between roads and buildings. Firstly, intra-community roads between neighboring building footprints are generated using a Delaunay triangulation skeleton model, and with the existing inter-community roads they form the simulated network. Secondly, street centrality indices of the current and simulated networks are compared in terms of closeness, betweenness and straightness. Results indicate that after applying the policy the global accessibility in the city would be increased at some places and decreased at others, and places' directness among others would be generally improved. In addition, the skeleton of central routes for through traffic would not change much. The presented method can also be applied to other cities. 相似文献
20.
遥感影像可以极大地增强DEM的表达效果,然而由于各种因素的影响,通常需对其进行预处理,传统方法是通过同名控制点进行校正。该文提出一种新的自动匹配算法,即提取DEM和遥感影像对应的特征线,利用Douglas-Peucker算法提取对应的特征点,以DEM特征点为离散点进行Delaunay三角剖分,并基于TIN完成纹理映射。实验结果表明,该算法显示效果较好,可有效改善畸变图像引起的错误显示。 相似文献