基于边优先的任意多边形最优三角剖分

针对现有多边形三角剖分算法不能同时兼顾算法的简单有效性、适用性以及剖分三角网质量的问题,提出一种基于边优先的任意多边形最优化三角剖分算法:首先直接对多边形的边进行构网,最后再对生成的非约束边进行构网,最终完成整个多边形的三角剖分。剖分得到的三角网为约束Delaunay三角网,网形稳定、最优,算法简单,执行效率较高,且适用于任意复杂多边形。实验证明了该算法的合理性和有效性,较好地解决了现有多边形三角剖分算法存在的问题。     

GIS岛多边形三角剖分算法

结合Delaunay三角剖分原理,在多边形顶点关系的基础上,通过对多边形从外向内间隔相邻级环间的三角剖分,来实现岛多边形的剖分算法。算法涉及图形相交、相邻、相离、包含等几何关系分析,以及Delaunay三角形构建等过程。对图形几何关系判断和三角形构建等过程进行了优化处理,提高了岛内三角剖分的精度和速度,解决了GIS制图中存在的"岛中岛"等复杂几何图形的剖分问题,可以对任意凹凸多边形实现快速三角剖分。首先获取并存储shape文件中多边形的空间坐标数据,然后基于该算法在VC++开发环境中完成岛多边形的三角剖分和显示。通过对不同形状的岛多边形反复测试表明,该算法的三角剖分结果均可达到最优,且效率较高。     

利用自适应分块的任意多边形三角剖分算法

三角剖分算法是计算几何领域中的重要课题之一,针对现有多边形三角剖分算法大多不能同时兼顾算法的简单有效性、适用性以及三角网的质量问题,提出一种基于自适应分块的任意多边形三角剖分算法。多边形的自适应分块区别于传统的格子分块,它充分顾及了多边形边作为剖分三角网约束边这一特点,通过选择原始多边形一定数量的边,并对这些边构建最优三角形,将原始多边形分割成若干个小的简单多边形,这些简单多边形之间通过三角形进行连接。至此,原始多边形的三角剖分直接转化为这些简单多边形的三角剖分,这样由一条边寻找一顶点构建最优三角形,直接在该边所在的简单多边形内进行搜索,大大减少了点的搜索范围,提高了算法效率。利用基于边优先的多边形三角剖分算法对分块后的小多边形进行三角剖分,从而完成整个多边形的三角剖分。算法具有适用性广,剖分三角形网形稳定、最优,思路简单,易于实现,执行效率高的特点,最后通过实验证明了本算法的科学性和先进性。     

利用自适应分块的任意多边形三角剖分算法

三角剖分算法是计算几何领域中的重要课题之一,针对现有多边形三角剖分算法大多不能同时兼顾算法的简单有效性、适用性以及三角网的质量问题,提出一种基于自适应分块的任意多边形三角剖分算法.多边形的自适应分块区别于传统的格子分块,它充分顾及了多边形边作为剖分三角网约束边这一特点,通过选择原始多边形一定数量的边,并对这些边构建最优三角形,将原始多边形分割成若干个小的简单多边形,这些简单多边形之间通过三角形进行连接.至此,原始多边形的三角剖分直接转化为这些简单多边形的三角剖分,这样由一条边寻找一顶点构建最优三角形,直接在该边所在的简单多边形内进行搜索,大大减少了点的搜索范围,提高了算法效率.利用基于边优先的多边形三角剖分算法对分块后的小多边形进行三角剖分,从而完成整个多边形的三角剖分.算法具有适用性广,剖分三角形网形稳定、最优,思路简单,易于实现,执行效率高的特点,最后通过实验证明了本算法的科学性和先进性.     

带岛区约束数据域的Delaunay三角剖分通用算法研究

文章提出了一种可解决带岛区约束数据域的三角剖分通用算法,通过对岛区制图边界拓扑结构建立与分析,引入双联点和辅助约束边界概念对岛区外部划分子区(抽象出凸或凹多边形),再采用任意多边形内部三角剖分算法,实现了带岛区约束数据域的Delaunay三角剖分并应用于油气勘探设计等领域。     

三维建筑的三角重剖分算法

三维建筑是三维地物的主体,是三维城市和三维G IS的重要组成部分。三角面是三维图形可视化的基础,三角面的数量决定了三维建筑的渲染速度。针对三维建筑物建模及综合过程中存在冗余三角面的问题,本文提出了一种主要应用于三维综合的三角剖分算法。该算法包括两部分:基于邻面搜索的轮廓构造算法和任意多边形的剖分算法。实验证明此算法可实现大部分三维建筑的重剖分,其应用也可延伸到其他领域。     

三维空间中任意多边形的绘制

空间分析是地理信息系统中必不可少的一部分，随着计算机硬件、三维仿真技术的成熟，用户希望将空间分析及其结果在更加直观的三维空间中进行表达。而分析区域或分析结果大部分是以多边形的形式进行表达，因此，需要研究三维空间中任意多边形的绘制方法。本文分析了三维空间中传统多边形绘制方法的局限性，提出了基于三角剖分的任意多边形绘制方法，并进行了算法实现。     

城市景观三维重建中的三角剖分算法

在构建城市景观时,为了快速精确地重建建筑物、绿地、河流等三维模型,提高自动化程度,缩短建设周期,需对用户采集的矢量地物数据进行三角剖分,再以OpenGL重绘三维模型。本文提出了一种对多边形进行三角剖分的递归分割算法,并以VisualC++实现,以实际的4万多个建筑物进行三角剖分实验,充分证明其是有效的。     

三维模型重建中的凹多边形三角剖分

OpenGL作为通用的开放式三维图形标准,在三维模型重建方面有着广泛的应用。但由于它只提供绘制填充凸多边形图元的函数,因而难以处理很多具有凹多边形外形的三维实体。文中提出了一种对凹多边形进行递归三角剖分的分割算法,较好地解决了这个问题,并成功地用于基于OpenGL的建筑物三维重建。     

基于CUDA的二叉树图像拼接算法研究

提出一种基于CUDA的二叉树图像拼接算法,对现有的SURF特征点算法进行GPU加速,并对原有的图像拼接流程进行改进,采用二叉树进行递归拼接。实验证实,基于CUDA二叉树图像拼接的速度有较大提升。     

Tile‐based polygon overlay of vector data in a virtual globe

The demand for analysis of large‐scale data has increased with increased access to spatial vector data. Polygon overlay of vector data in a virtual globe requires proprietary data structures and proprietary analysis algorithms. A vector data structure is designed for rapid polygon overlay in a virtual globe by recording the metadata of the triangles (TriMeta) that constitute polygons. A polygon overlay algorithm is proposed based on this data structure. The overlay of two complex GIS polygons is transformed into the intersection computation of their 3D triangular presentations. The intersection computation of two sets of triangles is reduced considerably by utilizing TriMeta to filter out the disjoint triangle pairs and rapidly identify the contained triangle. The new method improves the overlay efficiency in a virtual globe because the amount of computation required to calculate the intersections of two large polygons and drape the intersections onto a terrain surface is reduced.     

Delaunay三角网内插多边形算法研究

针对Delaunay三角网内插多边形的实用性,提出了一种Delaunay三角网快速内插多边形算法,该算法先将多边形的边作为约束数据入网,然后对多边形内部三角形进行清空处理.在影响区域及多边形内部三角形确定上,提出了一种快速解决方法,大大提高了算法的执行效率.     

Delaunay三角网内插多边形算法研究

针对Delaunay三角网内插多边形的实用性,提出了一种Delaunay三角网快速内插多边形算法,该算法先将多边形的边作为约束数据入网,然后对多边形内部三角形进行清空处理。在影响区域及多边形内部三角形确定上,提出了一种快速解决方法,大大提高了算法的执行效率。     

支持地图综合的面状目标约束Delaunay三角网剖分

针对多边形面状目标的综合问题,建立了二维空间中约束Ｄｅｌａｕｎａｙ三角网剖分结构,融入多边形的环、岛屿、边界、顶点的描述,通过形式化条件检索,在该结构上提取二维空间中各种感兴趣的由剖分三角形组成的区域,用于支持地图综合中邻近多边形的搜索、多边形弯曲部位的识别、冲突关系探测、多边形合并等操作。并对基于骨架线的图结构建立、分枝宽度计算等几何问题进行了详细讨论,指出了其在诸如双线河中轴化、街道中轴线网络模型建立、多边形合并中的邻近关系分析、面状目标注记自动定位领域的支持作用。     

多边形骨架线与形心自动搜寻算法研究

针对GIS中的应用，分析了传统的多边形骨架线与形心提取算法的不足之处，提出了一种基于约束Delaunay三角网结构的多边形主骨架线与形心的自动搜索算法，详细描述了该方法的基本思想，并在实验结果基础上分析了该算法的特点。     

利用约束D-TIN进行建筑物多边形凹部结构识别与渐进式化简

分析了位于建筑物多边形外侧的凹部结构特征及其类型,探讨了一种基于凹部层次结构的建筑物多边形渐进式化简方法,即以三角形为形状基元,用约束Delaunay三角化方法对建筑物多边形进行空间剖分,从凹部三角形树中提取三角形序列,通过匹配特征序列识别凹部的基本模式,以确定和实施相应的凹部化简方法,在此基础上迭代执行识别-化简过程,以实现对建筑物复杂凹部的渐进式化简。实验分析表明,该方法具有结构化和渐进综合的特点。     

基于Delaunay三角网的等高线骨架提取算法

根据等高线数据直接建立不规则三角形网络模型往往会在山顶、山底、山脊和山谷等特殊地区出现＂平三角形＂,导致模型失真。文中基于Delaunay三角网,通过对＂平三角形＂的处理,提取骨架线,并结合地形特征估计其高程值。实验证明该算法能够有效地提取各种地形骨架线,对于建立逼真的数字地面模型和进行数字地形分析具有重要应用价值。     

An efficient solution for building polygonal objects

Polygonal object is a fundamental type of geometric data in vector GIS. The key step cleaning topological relationship after data collection of polygonal layer is to build polygonal objects from digital arcs. The raw digital arcs may intersect with each other. The algorithm for building polygonal objects after the raw arcs have been split at all intersections is presented. The build-up of polygonal objects in this paper is designed to be implemented by two steps. The first step is to extract all the polygons needed for build-up of polygonal objects from arcs. The second step is to organize polygonal objects from these polygons. For the first step, a tracing algorithm is proposed. The algorithm merely extracts the polygons needed for the build-up of polygonal objects, which is a subset of all the possible polygons that can be induced from the arcs. For the second step, an algorithm based on a specially designed order of polygons is advanced. All the topological relationships among the polygons are shown in a single scan. Experiments show that the two algorithms together offer a robust and efficient solution for building polygonal objects from intersected arcs.