基于节点序列搜索的多边形分割算法

针对多边形切割中由于切割点坐标值的取舍导致的点位偏移,从而可能出现拓扑错误的情况,提出一种基于节点序列搜索的多边形分割算法。该算法在生成多边形相交的切割线的基础上,对产生的切割点进行坐标值取舍,将进行坐标值取舍后的坐标点与被切割多边形的坐标点按照节点序列生成被切割多边形,同时切割点内插到相关多边形,从而保证多边形的拓扑关系不变。该算法能解决带岛多边形切割。该算法已经在大规模数据生产中得到应用。

基于遗传算法的多边形分割AUV全局路径规划

针对遗传算法在实际AUV全局路径规划应用中出现运算数据大、路径规划有尖峰等问题,提出了新型路径规划方法。利用平面直角坐标系实现环境的建模,将障碍物简化成多边形并分割为三角形。路径用首尾相接的线段表示,通过固定横坐标,随机生成纵坐标的方式实现遗传算法二进制编码,对障碍物三角形交叉判断,路径距离运算实现适用度函数编写。对遗传之后的路径通过避障、删除节点、平滑的操作确定最终优化路径。结果表明,对障碍物的三角形简化实现了在遗传操作中的程序优化,利用避障、删除多余节点、平滑操作实可很好的消除尖峰,可寻找一条相对较优的路径。

基于简单要素模型的多边形分割算法

多边形是GIS研究和应用中使用最频繁的几何对象,该文描述了基于简单要素模型的任意多边形分割算法。从计算几何出发,结合GIS空间数据的特点,将基于简单要素模型的多边形分割算法设计为:1)对多边形及分割线的边界排序,基于扫描线及外包矩形检测查找可能相交的线段,提高相交线段的搜索效率;2)计算交点生成结点信息(包括交点坐标、线号及交点的出入),并存储在独立的单向链表中;3)根据结点链表和原多边形坐标搜索结果多边形。该算法能够分割任意简单多边形(凹凸、曲线边界和带洞的多边形)以及有共享边的多边形。最后在MapGIS7.0平台上,实现了基于简单要素类的多边形分割功能。

基于点序的多边形分割方法探讨

多边形分割是多边形剪切的特殊情况之一,目前多边形分割的算法较为复杂且适用范围有很大的局限性。本文根据多边形的图形定义给出两个约束条件,然后根据约束条件结合多边形点序特征,提出一种基于点序的多边形分割算法。此外本文还依据多边形剪切和多边形分割的关系,扩展基于点序的多边形分割算法在多边形剪切中的实现,经试验分析达到了理想效果。

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

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

由课题“分割三角形”想到的“分割多边形”

《全日制义务教育数学课程标准(实验稿)》中指出:"综合与实践"是一类以问题为载体,学生主动参与的学习活动,是帮助学生积累数学活动经验、培养学生应用意识与创新意识的重要途径。其总体目标是"学生将在教师的指导下,将所学过的知识有机地结合,增强对知识的理解;注意与实际问题有机地结合,进一步获得数学活动的经验,增强应用意识。"

多无人机协同搜索区域分割与覆盖

多无人机覆盖搜索是无人机的一项主要任务,将搜索区域进行分割后,每个子区域内成为单机覆盖搜索问题,大大降低了任务难度.对无人机的平行搜索策略进行了详细的分析,针对平行搜索策略给出了搜索起始点、转弯关键点、搜索终点的判断依据,使得区域覆盖率达到100%.分析了最小转弯半径对搜索路径的影响.根据无人机初始位置和搜索面积对任意凸多边形搜索区域进行分割.针对无人机搜索的特点,以转弯次数作为主要依据对分割结果进行评估.对不同情况下无人机从初始位置到搜索起始点的路径进行了研究.最后通过仿真验证了方法的实用性.

考虑最短转弯半径的无人机区域覆盖航迹规划

为实现无人机测量自动化,必须解决覆盖航迹规划,即无人机路径规划,以便监测感兴趣区域内的所有点。为此,提出改进的旋转卡尺航迹规划算法,综合考虑被测区域的凹凸性、无人机类型、无人机起飞点、着陆点,计算最优边-点来回航迹,构成完整的覆盖航迹。被测区域是凹多边形,则将其分割为具有最小个数的凸边形;如果采用固定翼无人机,则需要考虑其最小转弯半径,进行航迹规划。仿真结果表明,改进的航迹规划算法更具实用性和有效性。

面向地形等高线匹配的三重约束LCSS算法

针对地形匹配中数据简化表示以及匹配的问题,提出一种基于等高线特征序列的三重约束LCSS地形匹配方法。首先将基准地形数据用等高线表示,对等高线进行多边形分割逼近,选取分割点作为等高线特征点,然后构造具有平移旋转不变性的弦长夹角特征描述子,对等高线特征点序列进行描述;其次,对实时地形数据以相同的方式构造等高线特征描述子与基准信息匹配;在特征匹配的过程中,针对LCSS算法生成匹配点的外点较多的问题,提出候选集约束、回溯路径同列最小约束、相对位置偏移方差约束的三重约束LCSS方法;最后,采用RANSAC算法对旋转平移参数进行解算,实现地形匹配导航定位。采用秦岭地区ASTER-GTM地形数据验证该地形匹配方法的性能,结果表明文中方法在噪声与几何变换下鲁棒性好,可以显著减少误匹配点数量,提高地形匹配的可靠性,能够有效应用于山区地形匹配导航。

优化TSP算法的完善及推广

本文完善和推广了文献［１］中的简单多边形优化三角剖分算法，提出了一种一般化的算法，它能对卷曲、缠绕复杂的简单多边形进行优化三角剖分，我们还把这种算法推广到简单多边形的优化外三角剖分和任意嵌套封闭多边形的情形。

基于拉伸特征的B-Rep→CSG转换算法及其应用

边界表示(boundary representation,B-Rep)法和构造实体几何(construction solid geometry,CSG)法是目前应用最广泛的两种实体表示法,B-Rep→CSG转换也备受关注。B-Rep→CSG转换算法为一种半空间分割法,完全依赖三维造型引擎中的布尔运算,计算量大且不稳定。实际应用中已有大量具有拉伸特征的B-Rep模型:可将整个模型或模型的一部分看作由二维图形沿一定方向拉伸而成。通过将三维模型的B-Rep→CSG转换问题变为二维图形的B-Rep→CSG转换问题,从而避免对布尔运算的依赖,为此,提出基于拉伸特征的BRep→CSG转换算法。首先,得到拉伸边具有相互平行性、首尾相连性、方向相反性、唯一连接性4个拉伸特征,然后,基于这些特征提出基于平行边连接图的拉伸特征识别算法,最后,结合拉伸特征识别算法、基于环收缩的模型分割算法和基于顶点可见的多边形分割算法,提出具有拉伸特征的三维模型的B-Rep→CSG转换整体解决方案。将本文算法集成至自主研发的粒子输运可视建模(COSINE visual modelling of particle transport,cosVMPT)软件,并基于cosVMPT对3个专门构造的例题和1个实际应用实例进行了测试,测试结果证明了本文算法的有效性和优越性。

面向对象分割与混合像元分解相结合提取沙化土地信息

以甘肃省民勤县作为研究区域,使用了3景Landsat 8 OLI数据进行民勤县沙地信息的提取,提出了一种混合像元分解(FCLSU)和面向对象图像分割技术相结合的新方法。该方法不仅实现了沙地、盐碱地和裸土的分类识别,还实现了流动沙地、半固定沙地和固定沙地的定量区分,新方法总体沙地分类精度为87.23%,高于面向对象图像分类的84.82%,在沙地定量划分中新方法有着更为明显的优势。

限定面积的图斑随机分割算法设计和实现

根据限定面积对多边形进行随机分割是空间数据库处理中的常见问题,可以模拟随机发生的自然现象和过程,广泛应用于数据缩编、数据更新、城市扩展模型和景观生态模型中。提出了根据已知面积对多边形进行随机分割的算法,首先,利用随机数发生器生成分割线段的起始点;然后,利用数据结构中的队列根据分割面积来计算分割线段的终止点;最后,利用C#.NET编程实现该算法并举例演示。多边形随机分割算法为直接在地理信息系统中模拟随机现象提供了参考。