简单多边形间最大距离的求解算法

求解任意两个简单多边形间的最大距离,在几何图形计算中,一直是一个基本问题。在对多边形自身的特性以及两多边形间关系进行深入分析的基础上,提出了一个基于折线凸包的单调性的简单多边形间最大距离的求解算法。根据封闭折线内部所具有的特性,把封闭折线拆分成两个断开的折线,使一条折线在另一条折线左边。两个多边形分别被拆分成四条折线,两个分为一组。分别求出每组中两条折线的凸包,利用凸包的单调性可以快速地找出两个距离最远的顶点,其中较大的是两个简单多边形间的最大距离。算法的时间复杂度是线性的。     

一种简单平面多边形的快速分割方法

根据二分法的原理设计了一种简单平面多边形的快速分割算法,并利用ArcEngine提供的编程接口对该算法进行了实现,最后对算法进行了测试。实验结果验证了该算法的收敛特性,可以较好地控制分割精度,在满足精度要求的前提下实现多边形按面积或按比例任意份的分割,具有操作方便,参数控制灵活的优点。     

煤矿地质成图中多边形快速生成算法

针对煤矿地质成图中左转算法生成多边形在复杂的二维图形条件下应用效率低的问题,该文提出了一种新的基于左转算法的多边形快速选取及自动生成算法,实现了2D图形环境中多边形的快速选取及自动生成。通过在进行多边形选取时的起始点,起始方向的选择和对悬挂点、线进行处理,解决了复杂图形下多边形选取及自动生成过程中存在的重复生成、效率低下和搜索回退问题。基于GeoMS3D实现该算法,实验结果表明:该算法逻辑简单、结构清晰,在实际的应用中表现出了较高的运算效率。     

一种多边形交、并、差运算的有效算法

以周培德的Z₅₄算法为参考,提出了一种简单多边形交、并、差运算算法--IBO算法。该算法能够处理二维现实世界中的各种情况,对于地理信息系统的空间分析有较好的应用价值。     

简单多边形顶点凹凸性判断算法综述

简单多边形顶点凹凸性判断算法种类繁多,在模式识别及计算机图形学等领域具有重要应用.为了研究不同种类算法的内在联系与区别,以便在实际应用中根据情况选择合适的算法,分析了目前较为流行的角度法、左右点法、矢量面积法、向量积法、射线法、斜率法和极点顺序法等算法.经过详细的推导论证发现,这些算法都可以使用公式b=p*m来表示,且...     

一种有效的复杂多边形裁剪算法

提出了一种基于扫描线思想和梯形分割技术的多边形裁剪算法,其主要步骤包括:计算主多边形(集)与窗口多边形(集)的交点,提取所有交点和多边形边界结点的纵坐标(y)并进行排序;以排序后的y作水平扫描线,分别对主多边形和窗口多边形进行梯形分割,获得两组梯形集合;对这两组梯形集合逐行执行梯形单元“交”运算,最后对结果交集进行边界追踪建立裁剪多边形。实验结果表明,该算法具有较好的计算效率,是一种比较实用的多边形裁剪算法。     

拓扑多边形自动构建的一种快速算法

本文提出了一种基于方位角计算的多边形快速构建算法，很好地解决了拓扑多边形构建及“岛屿”与“飞地”处理问题。整个算法结构清晰，简单易懂，程序设计易于实现。     

基于单调链和STR树的简单要素模型多边形叠置分析算法

针对简单要素类叠置分析的特点,利用STR(sort-tile-recursive)树索引改进算法能够将尽量多的多边形节点存储在STR树的叶节点中,减少在空间数据库中检索多边形时的磁盘读取次数。算法对多边形边界进行关于坐标轴的单调链分割,并在多边形求交过程中引入平面图的概念,利用平面图元素与各个多边形的拓扑关系来组织叠加后的多边形。该算法能有效减少求交点的时间,在线段求交中加入对连续出入点特殊数据的处理。同时该算法使用单调链减少多边形求交过程的比较次数,与其他使用双链表或单链表的算法相比具有占用空间少及处理速度快的特点。     

任意多边形裁剪算法的研究及其实现

介绍了一种改进的Weiler-Atherton裁剪算法,简化了算法的实现过程,完善了细节处理,通过在地图符号库设计系统进行实验,获得了满意的结果.     

基于线段操作的多边形求交算法研究

根据多边形之间的相交状态求所有目标多边形线段与源多边形边界的交点;利用点与多边形关系判别法则判断出目标多边形与源多边形的公共线段;目标多边形与源多边形对调,再次判定出公共线段;最后将公共数据选择集中的公共线段首尾连接构成闭合多边形即为两个多边形求交结果。求交算法以线段操作为核心求解两多边形的交集,通过遍历公共线段来完成交集多边形边界的构建。该算法结构简单,易于编程实现,计算工作量小,求交效率高,已成功应用在土方计算软件开发中,在地图制图和地理信息空间分析等方面有广阔的应用前景。     

阶差等比数列选取模型算法研究

论述了原选取模型控制表生成的数学基础,确立了该数学模型的“阶差等比”实质,生成了更为简洁的算法,并揭示了其内在的构造规律。     

两个简单多边形求交的算法

采用了双向链表这种数据结构,对两简单多边形的顶点及交点进行存储,在对交点进行插入时,可直接插入链表中,避免了利用单向链表或数组进行存储时对点的重复查找。通过遍历两个顶点、交点混合表,可得到两多边形的交及多边形的顶点,从而得到两多边形的交集。相对其他类似的算法,该算法具有较快的计算速度和较高的效率。     

基于二叉树思想的任意多边形三角剖分递归算法

提出了一种基于二叉树思想的任意多边形三角剖分递归算法。该算法采用二叉树思想,确定剖分三角形的二叉树状结构,并采用递归算法实现。该算法可适用于任意形状的凹或凸多边形,也适用于包含岛屿的多边形。此外,在考虑边界点高程的基础上,可充分顾及地形特征。该算法完全适用于长距离河流流域的三维面状表达。     

一种道路网信息几何差异检测算法

道路网信息几何差异的检测在导航电子地图数据更新,数据压缩和质量检查中具有重要的现实意义。针对道路网信息和道路信息几何差异检测的实际应用特点,对传统的平面扫描线算法进行改进,提出一种新的计算道路网信息几何差异的高效算法。该方法的计算复杂度为O((n s)logn),n表示输入数据大小,s表示线段交点的个数;并且在实际地图生产中得到应用,结果表明该算法效率高,符合应用需求,可靠性好。     

长距离网络RTK参考站间双差模糊度快速解算算法

提出了一种长距离网络RTK参考站间双差整周模糊度快速解算方法,该方法利用双频载波相位模糊度间的线性关系确定宽巷模糊度,然后选取双频载波相位的备选模糊度组合,通过计算参考站间对流层误差和轨道误差等非色散误差,对双频载波相位整周模糊度进行搜索。实验结果表明,此方法能够快速、可靠地解算长距离参考站间的双差整周模糊度。     

第三次国土调查的图斑自动综合方法

从第三次国土调查数据库快速缩编派生出多尺度数据库,是地图制图的重要任务。本文针对大量图斑,首先通过研究图斑栅格综合,减少碎图斑数量;然后构建图斑语义邻近度模型、空间几何拓扑模型,分析了顾及拓扑和地区地理特征约束下的地类图斑制图综合方法;最后形成了自动化图斑缩编生产工艺流程。基于上述方法,采用计算机编程技术研发国土三调缩编系统,并应用于四川省某县23万图斑量的三调数据并试验验证。试验结果表明,通过本文方法的成果符合专题制图要求,极大地提高了三调图斑的自动综合效率。     

一种高效的建筑物直线特征提取算法

随着遥感卫星的发射,国内影像处理事业逐渐被人们重视。高效、快速地对遥感及航测影像进行特征提取成为当前研究的热点。本次实验采用辽宁科技大学1∶2 000航拍影像图,针对教学用地建筑物直线提取中绿色植被和道路的影响,提出了一种新的直线提取算法。实验将直线拟合和Hough变换结合并进行改进,对实验结果进行对比,分析改进前后效果。实验结果表明:该方法能很好地适应复杂地形下建筑物的直线特征提取,提取速度快,有效地解决了教学用地中道路和绿色植被对建筑物直线提取的影响问题。     

基于Bootstrap的模糊度法方程更新算法的改进

阐述了GPS数据处理中基于Bootstrap的模糊度固定策略,在此基础上对二维法方程以及参数更新的算法进行改进,推导了更高效的三维法方程以及参数更新算法,能够提高解算速度,对GPS数据处理具有一定的参考价值。     

遗传算法在甲流SIR模型参数求解中的应用

论文以全国甲型H1N1流行性感冒（下简称甲流）疫情数据为实例,讨论了采用SIR模型对甲流的传播过程进行模拟时相关参数的求解问题。分别通过优化的遗传算法（Genetic Algorithm,GA）和模拟退火算法（Simula-ted Annealing Algorithm,SA）求得该非线性模型中的重要参数阈值（日治愈率与日传染率的比值）,并由该参数阈值计算出各月患病人数。论文比较分析了两种算法在精度和效率上的优劣,发现遗传算法优于模拟退火。同时模拟结果验证了SIR模型适合甲流疫情的分析模拟。