平面散乱点集凸包的快速生成算法

凸包问题是计算几何的基本问题,在实际工程中得到了广泛的应用。传统的凸包生成算法一般需要两个步骤,首先将离散点按照某种特性排序,然后进行凸包生成。依据快速排序算法的思想,提出一种“一步法”构建平面点集凸包的算法,将构建平面点集的凸包问题与排序问题结合起来,在排序过程中快速生成点集凸包。整个过程达到时间复杂度下限O（nlogn）。该算法在“河北省蓄滞洪区信息管理系统”中得到了实际应用,效果理想。     

一种简单多边形凸包的新线性算法

给出了一个计算简单多边形凸包的新算法，其搜索策略为：对简单多边 形上的点进行分类，排除不可能为凸包上的点，缩小搜索范围，从而降低算法的时间复杂度，该算法具有线性时间复杂度和空间复杂度，同时，具体量化了该算法的复杂度，给出了该算法的时间复杂度和空间复杂度的确定的上界，即，时间复杂度为不超过4(n-4）次乘法，6（n-4）次减法和17n-12次比较运算，空间复杂度为不超过2n个存储单元（n是该简单多边形顶点的个数）。     

求简单多边形可见点的一种新算法

提出一种求简单多边形可见点的新算法,通过对多边形作预处理,可预先剔除其中部分不可见点,并消除了判断可见点过程中的螺旋状态.将多边形剩余顶点序列分割为四段,每段分别按文中给出的方法找出可见点.算法中对点与线段的位置关系,用点与线段围成的三角形的方向表示.三角形的方向通过极点顺序法确定,避免了使用耗时的叉积法.试验表明,算法准确、高效和稳定.     

多边形OFFSET中无效环的去除算法

对于多边形OFFSET后产生的自交环现象,提出一种求解自交点的基于单调链的平面扫描算法,并对环的判别提出了一种简便而有效的方法。最后,对算法的时间复杂度进行了分析。实验表明,该算法高效而稳定地处理多边形OFFSET后产生的自交环。     

简单多边形顶点凸凹性的快速确定算法

本文深入剖析了平面简单多边形方向（逆时针或顺时针）与顶点凸凹性的内在本质联系，提出了确定顶点凸凹性的快速算法，并解决了根据凸点确定多边形方向的基本问题。本文方法已应用于工厂设计软件ＰＤＳＯＦＴ的工厂模型消隐和平剖图消隐中，实践证明效果很好。     

基于边向量斜率比较的简单多边形顶点凸凹性快速判别算法

对于给定的平面简单多边形顶点序列,判别多边形方向和顶点凸凹性的传统方法为:先计算多边形相邻边向量的叉积或相邻3个顶点所确定三角形的有向面积,再由叉积或有向面积的符号来确定顶点的凸凹性,使得处理一个顶点需要2次以上的乘法运算。笔者通过边向量斜率的计算和比较,将多边形顶点的凸凹性与边向量的斜率联系起来,并采用“假设-检验”方法,提出了一种快速判别简单多边形方向与顶点凸凹性的新算法,其时间复杂度为)(nO,判别多边形任一顶点凸凹性所需的乘法运算平均不超过1次。该算法原理直观简单,实现容易。实际运行结果表明,该算法速度快捷、运行稳定。     

连接不相交线段成简单多边形(链)的算法

提出一个实际问题，即如何连接平面上h条线段成一简单多边形或者简单多边形链，并证明了连接平面上线段集S成一简单多边形链的一个充分条件，S中有一条线段连接凸壳CH（S）中不相邻顶点，另外还提出了连接平面上线段集S成一简单多边形或者简单多边形链的算法，其基本思想是首先逐层计算线段集S的凸壳，并将这些凸壳改变多边形；然后计算各多边形之间的交点，进而删去这些交点。最后合并若干个简单多边形为一个简单多边形，当S中线段数目n较大时，用分治思想可以设计分治算法，较好地求解了这个问题，利用计算机求解这个问题上有实际应用价值。     

简单多边形方向及顶点凹凸性的快速判定

基于简单多边形方向与顶点凹凸性的内在联系，采用极值点性质判定多边形方向，通过多边形顶点坐标判定其拓扑映射点之间的位置关系，结合以上两方面对顶点的凹凸性作出判断。对基于拓扑映射的多边形顶点凹凸判别算法作出有效的改进，避免了原算法申大量的重复计算。实践证明，有效的减少计算次数，提高了效率。     

二维凸包Graham算法的设计与实现

本文设计了一种极角排序和方向判断方法，给出了Ｇｒａｈａｍ算法一种简单的实现。     

生成三维多边形平面域的双直线算法

提出了一种生成三维多边形平面域的新算法,该算法由主投影的扫描转换与主投影方向坐标的离散计算两部分构成。算法的两个部分相互独立,因而在第一部分可采用任意一种已有的多边形扫描转换算法来实现。主投影方向坐标的离散计算可通过两个整型数组（代表双直线）快速获得。算法可保证在理论上共面的两个多边形面域的公共部分在离散后完全重叠。     

寻求平面上线段集凸壳的扫描算法

首先证明寻求平面上线段集凸壳问题的下界是O(nlogn)，其方法是将平面上线段集凸壳问题与排序问题联系起来，由排序问题的下界推得平面上线段集凸壳问题的下界。然后提出一个算法，计算平面上线段集凸壳问题，其基本思想是将不交线段集中的线段按其端点的x，y坐标排序，并重排线段序。然后用平面扫描方法分段完成凸壳的构造。该算法的时间复杂性是O(nlogn)。     

寻求平面上线段集凸壳的算法

首先证明寻求平面上线段集凸壳问题的下界是O（nlogn)，其方法是将平面上线段集凸壳问题与排序问题联系起来，由排序问题的下界推得平面上线段集凸壳问题的下界。然后提出一个算法，计算平面上线段集凸壳问题，其基本思想是将线段集中的线段转换成平面上的简单多边形链，接着计算该简单多边形链的凸壳即得到所要求的凸壳。该算法的时间复杂性是O（nlogn)。     

计算两凸多边形的并集多边形及其面积的计算机算法与实现

提出计算两平面凸多边形的并集(多边形)及其面积的计算机算法，并对算法实现给出详细的计算过程。程序实现中，文中将算法分为判定点是否在多边形内部、求两多边形交点、求并集多边形及其面积三部分。引入利用向量叉积符号判定三角形的方向，进而判别平面上一点是否在凸多边形内的方法，简化了计算。还进一步提出了运用“区间分割”求两相交线段交点的新颖方法。     

类双曲壳的概念及算法

论文提出类双曲壳的概念,类双曲壳是一类通过射影平面无穷远直线的凸壳。运用拓扑同胚来帮助提出射影凸集和类双曲壳的概念。并借助于有向射影几何的正平面上可定向的优势,分析了从经典凸壳到类双曲壳的射影变换。构造出一个在欧氏平面上的实时凸壳算法,用于两个区域中间寻找直线簇。     

一种求凸多边形宽度的优化算法

提出了一种优化的线性时间算法计算凸多边形的宽度。首先证明了凸多边形的宽度只可能介于＂点边式＂跨度之间,缩小了宽度的计算范围。其次提出了一种距离比较算法,降低了凸多边形跨度的计算量。最后,在＂点边式＂基本算法和距离比较算法的基础上,提出了计算宽度的优化算法。仿真分析表明,提出的优化算法提高了计算凸多边形宽度的效率,算法的时间复杂性降为O（n）。     

基于梯形分解的不规则多边形干涉算法

研究了二维两不规则多边形之间的干涉量计算问题,将不规则多边形离散为有限个梯形的组合,从而转化为两两梯形对之间干涉量计算问题。分析了两梯形间干涉拓扑图形类型,并按内点个数区间及干涉量多边形顶点性质将其归类,给出两梯形对干涉量计算方法。在此基础上提出用水平梯形剖分不规则多边形的思想,进而得到基于梯形分解的平面多边形干涉算法,并进行该算法复杂度分析。最后,算例表明了本算法的可行性。     

求平面点集独立线段的一个联机算法

令Ｓ为一个有限平面点集合，线段Ｌ（ｐ，ｑ），ｐ，ｑ∈Ｓ称为Ｓ的一个独立线段当且仅当不存在两个端点在Ｓ中的线段与Ｌ（ｐ，ｑ）相交。本文给出了时间复杂度为Ｏ（ｎ＾２ｌｏｇｎ）和修正时间复杂度为Ｏ（ｎｌｏｇｎ）的联机算法。这一算法与已知的脱算法具有相同的时间复杂度。