求解简单多边形间最小距离的一个线性时间算法

计算简单多边形间的最小距离,在所有与几何图形计算有关的领域中,一直以来都是一个基本问题。为了更快地求解简单多边形的最小距离,提出了一个基于关联多边形三角化分割的简单多边形间最小距离的求解算法。该算法的主要思想是:首先构造一个关联多边形把两个多边形联系起来,其目的是把最小距离限制在这个关联多边形内;然后根据两个多边形的最小边界矩形包围框间的不同位置关系,详细阐述了关联多边形的构造过程,同时论述了关联多边形是一个简单多边形。为了计算最小距离,首先要对关联多边形进行三角化分割,并使最小距离位于三角化分割结果中某一个三角形区域内,或者至多位于两个相邻三角形区域内;之后通过对所有三角形进行遍历来找出最小距离及其所在的位置。该算法的时间复杂度是线性的。     

基于计算几何的一种航带设计算法

航带设计是执行航空摄影测量的第一步,而以前的航带设计都是由手工完成,效率低、精度差、成本高,已无法满足快速发展的航空摄影测量的精度要求。本文基于计算几何的思想,给出了一种航带设计算法。通过分析直线与多边形相交的各种情况,判断交点是否是临界点,找出符合条件的交点,即有效交点,把这些有效交点根据一定的规则连起来构成线段组,最后形成航带。作者编程实现了该算法,获得了满意的实用效果。     

简单多边形集凸包的快速算法

提出了一个简单多边形集凸包的快速算法.先求出每个简单多边形的(子)凸包,根据凸包的切线性质,从有关的子凸包中抽取一段严格单调的折线.应用归并排序方法把位于一条直线右侧的一组严格单调的折线合并成一条折线,把合并后的折线和子凸包集的外接矩形上的边连结成一条封闭折线,即一个简单多边形,使其能够把所有子凸包包围起来,最后求出这个简单多边形的凸包.算法的时间复杂度为线性O(n),并且给出一个例子进行了验证.