平面点集凸壳的一个性质

该文揭示了平面点集凸壳的一个性质,即如果一个子凸壳包含东、西、南、北4个方向上的极值点,则其任一条子凸壳边的外点必在该边所确定的外直角三角形中,并对该性质进行了数学证明。在此基础上,利用该性质对快速凸壳算法进行了改进,达到了良好的加速效果。     

基于凸壳原理的杭州城市扩展形态演化分析

在城市化快速推进的背景下,探索凸壳原理在城市扩展形态识别中的应用价值,并借此分析杭州市主城区1985~2010年间城市扩展形态演化规律及其机理,以期为控制城市扩展形态,指导未来城市土地开发活动提供借鉴。研究发现,凸壳原理在城市扩展形态识别上简单而明确,通过确定已有城市建设用地的凸壳,将城市所有可开发用地明确区分为凸壳内用地和凸壳外用地2类,为采取差别化的空间管理政策提供依据。构建了基于凸壳原理的城市扩展形态计算机识别方法,有利于在城市扩展模拟中实现城市扩展形态影响因素的定量化表达。1996年之前,杭州市建设用地和凸壳面积增长缓慢,城市形态相对紧凑;1996年之后,建设用地快速增长,城市不均衡扩展加剧,凸壳面积陡增,城市形态紧凑程度下降。总体来看杭州市城市扩展类型属于外延型,随着凸壳面积的增加,城市填充潜力随之增强,为促进杭州市城市紧凑化发展,应该严格控制凸壳外的城市土地开发。沿主干道的城市开发是城市形态外延式发展的主要因素,已有建设用地周边以及城市内部次要道路沿线的城市开发,以及城市中心的集聚作用和规划对城市开发的控制是城市形态填充式发展的主要因素,而郊区化发展和“东扩西进”等城市空间发展政策促使特定时期城市外延式发展。     

凸壳原理用于城市用地空间扩展类型识别

针对目前尚缺乏定量方法确定城市用地扩展类型的问题,首次提出了利用计算几何中凸壳原理识别城市用地扩展类型的新方法,阐述了该方法实现步骤和判别标准,凸壳方法可以区分城市用地扩展的两种类型,即填充类型和延伸类型。基于国家资源环境数据库,应用研究的结果表明,从1990年到2000年,安徽省城市用地扩展类型以填充类型为主,而用地扩展的结果导致城市形态的变化,这一时期安徽省城市轮廓平面形态逐渐趋于紧凑。     

二维Delaunay三角网的任意点插入算法研究

针对目前各种点插入算法的不足,提出一种二维Delaunay三角网任意点插入算法。首先基于凸壳区分点的位置,并利用三角形面积坐标、重心和点与有向线段关系三者构建的融和算法搜索插入点所在三角形,然后通过构建和优化新三角形完成点的插入,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。     

一种基于DEM的河网快速提取算法

目前从DEM中提取河网应用最普遍的是径向水流算法,但DEM中存在平地会形成平行水流,存在洼地会造成平行水流形成断流。该文提出一种快速提取算法:首先在DEM中标注山顶、平地、洼地和盆地,以山顶区域周围的低洼点为起点,按照最陡坡降追踪谷地,当追踪到盆地区域或其他谷地区域则结束;连接谷地和盆地,建立初步的河流网络。然后计算出网络中连接点的汇水量,舍弃汇水量小的节点的上游谷地,得到需要提取的网络。该算法避免了平行水流和断流的产生,其仅追踪从山顶区域(而非所有格网点)发育的水流,汇水量计算中仅计算连接点(而非所有格网点)的汇水量,实现了河网的快速提取。     

一种快速等面积分割平面简单多边形的算法

针对平面简单多边形按相等面积划分问题,设计了一种顾及形态特征和面积精度的快速分割算法。首先计算出多边形的最小面积外包矩形(MABR),确定其短轴方向为分割方向;然后根据MABR的长边距离与分块数计算出长边上的距离等分点,根据这些点构建初始分割线,并利用第一条分割线对多边形进行粗略分割;根据分割出的左多边形面积与目标分块面积差值转换成分割线的平移距离,沿长轴方向平移分割线,分割多边形,不断迭代,进行精细分割,直到满足面积精度要求;最后对分割出的右多边形按上述方法继续分割,直至完成分块。实验结果表明,相对于现有的两种算法,该算法的分割精度提升了1～2个数量级,处理性能分别提升了4.27倍和7.35倍。     

基于改进SURF算法的无人机遥感影像快速拼接

为了及时、准确地反映测区情况,需要在拍摄现场将获得的无人机遥感影像进行实时拼接.基于SURF的无人机遥感影像拼接算法具有尺度和旋转不变性,拼接效果较好,但该算法稳定性较差,拼接过程中大量误特征点被提取出来,导致计算量大、匹配效率低,无法满足实时拼接的要求.该文首先利用SURF算法粗提取特征点,然后利用RANSAC算法剔除被误提取的特征点,实现特征点的快速匹配和图像实时拼接.实验结果表明该文的算法不但可以得到很好的图像拼接效果,而且极大地提高了拼接效率.     

一种基于梯度最大值相位相关的航空影像自动配准算法

图像配准是将不同时期、不同视点或从不同传感器获得的同一地域目标的图像对准的过程[1-5],其主要目的是消除或减少参考图像和待配准图像之间由于成像条件不同所引起的几何形变,从而获得具有几何一致性的两幅图像。本文针对基于灰度图像配准算法中传统的梯度配准法执行效率低的     

无人机航摄生成DEM的高程点快速提取算法

无人机航空摄影技术在近年来得到了迅速的发展,无人机具有起降方便,分辨率高,响应速度快的特点,在抢险救灾,地质灾害监测等方面发挥了重要作用。无人机航空摄影生成的地形图中的高程点提取是地形图制作的重要步骤,本文提出了一种自适应的地形图高程点提取算法,相对于传统的算法,具有精确度高,计算简单,实用性强等特点。该算法的基础是数学形态学中的图像膨胀算法。本文将此算法用于陕西省丹凤县和紫阳县的无人机航摄生成的地形图中,提取了符合要求的高程点。结果表明,提取的高程点完全满足了地形图的要求,说明了该算法的准确性和实用性。     

基于钻孔点集Voronoi 图的矿产储量新算法

该文在分析平面点集Voronoi图特性及其生成算法的基础上,针对传统矿产储量计算方法的不足,提出了一种新的方法。该法以钻孔平面点集的Voronoi图为基础,利用Voronoi多边形的势力范围特性,实现了任意区域内矿床体积与矿产储量的计算。并给出了以Delphi编程实现的系统界面与计算实例,讨论了基于钻孔三维点集的Voronoi体进行矿产品位与经济可采性分析的前景。     

一种新的最小凸包算法及其应用

当前流行的最小凸包算法的时间复杂度相对较大,不适宜处理海量数据.该文提出一种新的平面离散点的最小凸包生成算法,其时间复杂度为O(nlogn).该算法通过排序、分区、指针定位、一遍扫描离散点集,在运算过程中对凸包顶点进行动态增加或删除,可快速生成点集的最小凸包.最终,求离散分布的居民点点集的最小凸包实例表明,该算法应用效果较好.     

Efficient measurement of continuous space shortest distance around barriers

There are many different metrics used to estimate proximity between locations. These metrics are good in some situations and not so good in others, depending on permissible movement behavior. A complicating issue for general metrics to accurately reflect proximity is the presence of obstacles and barriers prohibiting certain directions of movement. This paper develops a continuous space-based technique for deriving a guaranteed shortest path between two locations that avoids barriers. The problem is formalized mathematically. A solution approach is presented that relies on geographic information system (GIS) functionality to exploit spatial knowledge, making it accessible for use in various kinds of spatial analyses. Results are presented to illustrate the effectiveness of the solution approach and demonstrate potential for general integration across a range of spatial analysis contexts. The contribution of the paper lies in the formal specification of the problem and an efficient GIS-based solution technique.     

An Indoor Routing Algorithm for the Blind: Development and Comparison to a Routing Algorithm for the Sighted

This paper presents a prototypical implementation of a non‐network‐based indoor routing algorithm for the sighted and the blind. The spatial abilities of the visually impaired are discussed. Former approaches of outdoor navigation systems for the blind are analyzed and deemed inappropriate for the purpose of modeling indoor navigation. The proposed routing algorithm for the blind calculates routes based on physical characteristics of traveling with a long cane. The algorithm distinguishes between clues, landmarks, obstacles, and hazards along the feasible paths and selects the optimal route by trading off distance and the number of landmarks and clues along a route. Subsequently, the routes for the blind are compared to routes calculated by the routing algorithm for the sighted. The paper asserts that the proposed indoor routing algorithm leads to more suitable routes for the blind.     

一种改进的基于法矢方向调整的平面点云分割方法

智慧城市的蓬勃发展和快速推广,使得三维建模成为当前热点研究方向。平面点云分割是三维点云建模中数据处理的关键环节。该文提出一种三角面片法向量方向调整方法,通过后续对邻近法向量进行加权平均估算实现平面点云的分割。首先采用八叉树的空间划分方法将无序的点云建立索引,利用K紧邻搜索获取参考点的K个邻近点,然后将该局部点构建不规则三角网并且得到包含参考点的所有三角面片以及三角面片的法向量,并通过将三维点投影到二维平面,利用平面三角形两边向量叉乘的方法,判断并调整各三角面片的顶点排列顺序,使三角面片的法向量一致化,最后对包含参考点的所有三角面片的法向量加权平均,估算参考点的法向量,根据点云法矢一致、共面的原则将平面点云分割出来。以徕卡Scanstation 2型扫描仪获取点云数据,对该方法进行检验,结果显示其能较好地实现对点云法矢量方向的调整与估算,并对平面点云数据进行分割提取。     

二维Delaunay三角网的任意点删除算法研究

针对目前基于影响域多边形剖分的点删除算法缺陷,提出一种二维Delaunay三角网点删除算法。首先利用具有拓扑关系的三角网搜索影响多边形,并以三角形矢量面积为工具三角剖分影响域多边形,最后通过镶嵌优化后的剖分三角网完成点的删除,且满足Delaunay法则。通过测试证明了算法的可靠性和高效性。     

基于四叉树索引构建TIN的高效合成算法

不规则三角网(TIN)可以逼真的模拟地形表面,因此被广泛应用于地学领域。Delaunay三角剖分算法是构建TIN网的最优算法,该文对传统Delaunay三角网构建算法进行分析,提出了一种针对大规模离散数据点生成TIN的高效合成算法。该算法首先根据离散点的分布位置和密度对其进行四叉树区域划分;然后以每个叶子节点的边界四边形为凸包,采用逐点插入法构建三角网;最后采用顶点合并法自底向上合并具有相同父节点的4个子节点,生成Delaunay三角网。实验结果表明,该算法时间复杂度较低,有效提高了TIN网的构建效率。     

大规模地形实时绘制算法

该文提出一种适合大规模地形实时绘制的简单高效的LOD简化算法。该算法使用一种紧凑有效的规则网格表示方法,优化网格节点的数目,减少可视化过程中的计算量,降低额外内存开销。探讨该算法相关的数据组织、视域裁剪、LOD层次选择、裂缝消除、三角形化等关键问题。实验结果表明,该算法实现简单,内存开销较少,CPU耗费小,对图形卡要求低,能够在普通机器上实现大规模地形的实时漫游。