一个改进的简单多边形凸包算法

本文改进了一个有名的简单多边形凸包算法－陈氏算法，使得改进后的算法不但具有线性效率、可避免自交等优点，而且实现简单。     

基于有序简单多边形的平面点集凸包快速求取算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。传统平面点集凸包算法和简单多边形凸包算法平行发展，互不相干。本文将改进的简单多边形凸包算法应用于平面点集凸包问题中，提出了新的点集凸包算法。该算法首先淘汰掉明显不位于凸包上的点，然后对剩余点集排序，再将点集按照一定顺序串联成有序简单多边形，最后利用前瞻回溯方法搜索多边形凸包，从而得到点集的凸包。本文算法不仅达到了Ｏ的理论时间复杂度下限，而且算法     

对平面简单多边形求凸包的线性时间算法

本文提出一种求平面简单多边形凸包的线性时间算法,这种算法是在一般局部凸算法上加了陷阱,这样就可克服局部凸算法产生的自交现象,文中还证明了这种算法的正确性。     

一种求简单多边形凸包的最优算法

计算一般多边形凸包的算法时间复杂度为Ｏ（ｎ＾２）。     

一个改进的简单多边形凸包算法

凸包问题是计算几何的基本问题之一，在许多领域均有应用。该文通过给出反例，证明文献[4]提出的简单多边形凸包的双动线检测算法不能正确求出任意多边形的凸包，并分析了其缺点，提出了一个改进的算法。改进的算法解决了线性算法所不能解决的自交问题，且实现简单。     

简单多边形方向识别的健壮算法

极值顶点前后相邻边矢量叉积法是识别任意简单多边形方向的最优算法 该算法存在的问题是 :当极值顶点前后相邻边夹角接近 0°或 180°时 ,叉积结果接近 0 ,因此存在二义性 ,会导致错误的方向识别 针对现有算法对奇异情形方向判别解决不彻底的问题 定义了多边形极值顶点奇异情形 ,对相邻边夹角接近 0°和 180°两种奇异情形给出了判定方法 ;提出了极点前后点坐标比较法和极点序号大小比较法 ,有效地解决了所有奇异情形下的方向识别问题 ,它们都可以发展成为独立的方向判断算法 实验结果表明 ,该算法简单高效 ,健壮性强 ,时间复杂度为O(n)     

简单多边形凸包的双动线检测算法

计算凸包问题不仅是计算几何的基本工具之一，而且在实际应用中也是很重要的，本文运用Ｇｒａｈａｍ扫描技术及双动线检测的方法，构造了测定简单多边形凸包的Ｏ（ｎ）快速算法。     

求解简单多边形和平面点集凸包的新算法

沿一定方向遍历凸多边形的边,其内部在边的同一侧。本文依据凸多边形的这一特性,提出求解简单多边形凸包的新算法,进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点,得到极值点间的候选点子集,再求得相邻极值点间的有序凸包点列,最后顺序连接极值点间的有序凸包点列,得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O（n log h）,其中,n为平面点集的点数,h为平面点集凸包的顶点数。相比相同复杂度的凸包算法,新算法简单、易于实现。又由于是顺序求得凸包上的点,新算法还具有更易于实现基于其上的有效空间算法的优点。     

基于象限划分的简单多边形方向与顶点凸凹性快速判别算法

文中提出一种快速判别简单多边形方向与顶点凸凹性的新算法。通过对简单多边形的每一个顶点引入伴随坐标系,将平面划分为与该顶点相关的四个部分;由此可以得到简单多边形中与该顶点相邻的两个顶点在该平面划分中的16种配置关系：不同的配置关系对判别该顶点的凸凹性所需要的计算量是不同的,从而使大量凸凹性判别工作由“比较”运算来完成,只有在必要时才运用“乘／除法”运算;算法利用“假设一检测”方法,通过获取诸顶点中横坐标值最大的顶点,最终确定简单多边形的方向和诸顶点的凸凹性。文中算法的时间复杂度为O（n）。一般情况下,计算一个顶点的凸凹性所使用的乘法次数平均不超过一次,最坏时也仅为一次。     

关于凸多边形的修剪算法研究

该文研究并提出了一种凸多边形的裁剪算法，它不同于传统的多边形剪算法，仅需对视口在点所关联的边检查与视口的相一。裁剪速度快，简单易行。     

凸多边形窗口线裁剪的新算法

凸多边形窗口的线裁剪是用多边形窗口裁剪多边形的基础 .为此 ,提出了凸 n边形窗口的线裁剪新算法 .新算法与 Cyrus- Beck算法相比 ,当 n较大时 ,新算法的乘法大约只有 Cyrus- Beck算法的 1/ 3且仅用 4次除法 .因此 ,新算法大大地加快运算速度 .     

基于ORB和最小凸包的感兴趣区域检测方法研究*

随着科技的发展,如何准确检测出复杂背景情况下的感兴趣区域(ROI)和提高检测方法的实时性已经成为图像处理领域亟待解决的问题。针对此问题,提出了基于ORB(ORiented Brief)算法检测特征点,并采用最小凸包检测感兴趣区域的方法。首先,采用ORB算法提取出图像中的特征点,然后从中挑选出效果良好的点对图像进行描述,最后采用最小凸包算法检测出感兴趣区域。在和其它算法的检测速度对比和复杂情环境况下的检测实验结果表明,ORB和最小凸包算法的结合在保证的检测精度基础上提高了检测速度。     

基于凸多边形的凸壳算法

确定平面点集的凸壳问题在计算机图形学、图像处理、CAD／CAM、模式识别等众多领域中有广泛的应用。本文根据凸多边形的性质构建了一种新的基于凸多边形的凸壳算法，该算法利用X、y坐标的极值将凸多边形分为几个段，应用凸壳顶点有序性，分段计算凸壳的顶点而得到凸壳。理论分析和实验结果表明，该算法运行速度快效率高，具有较强的实用性。     

基于循环链表的凸包增量算法研究与实现

采用循环链表构建凸包,使凸包的各顶点在增量过程中,始终处于动态变化的稳定循环链中,无差错地生成结果凸包。相比顺序表而言,每次只需修改指针,无须在内存中频繁移动顶点数据,节省大量的系统时间及内存资源,从根本上解决首尾相接的凸包动态生成问题,极好地满足程序的鲁棒性原则,代码执行效率高。     

圆形窗口的凸多边形填充算法

给出了一种基于圆形窗口的凸多边形填充算法，它集裁剪与填充功能于一体，也可完成单纯地裁剪功能。     

A Linear-Time Approximation Scheme for Maximum Weight Triangulation of Convex Polygons

In this paper we present a linear-time approximation scheme for determining the maximum weight triangulation of a convex polygon. Our algorithm is simple and can be implemented easily.     

基于双域双向水平倾角最小化圈绕的凸壳新算法

本文依据同构化凸壳构造基本定理,提出效率更高的双域双向水平倾角最小化圈绕凸壳新算法.本新算法的同构化特点是:1)"初始顶点与双域生成"处理:找出给定二维点集S的最低点和最高点,即Y轴坐标值最小点(若有多个最小点,则只取最左的最小点)和Y轴坐标值最大点(若有多个最大点,则只取最左的最大点),作为凸壳(逆时针围绕的)A向初始顶点、(顺时针圈绕的)B向初始顶点;并以这两个初始顶点为端点的线段,把原二维点集划分为两个独立的子点集S右、S左.2)在S右内,进行双向"圈绕寻找下一新顶点"即凸壳A向、B向最新顶点寻找处理:分别过自己的最近新顶点,作X轴正向射线,并A向或B向找出当前点集内对该顶点正向射线(为始边的)倾角最小的点;删除对已得各顶点所构成的子凸壳内点,当所剩当前点集非空时继续作"2)"逐边圈绕,直到为空.3)同理,在子点集S左内,进行双向"圈绕寻找下一新顶点"即凸壳A向、B向最新顶点寻找处理.     

双域单向水平倾角最小化圈绕凸壳新算法

本文依据同构化凸壳构造基本定理,提出了效率更高的双域单向水平倾角最小化圈绕二维点集凸壳新算法,实现了对卷包裹凸壳算法、单域单向水平倾角最小化圈绕凸壳算法的改进与创新。本新算法的同构化特点是：1）“初始顶点与双域生成”处理：找出给定二维点集S的最低点和最高点,即Y轴坐标值最小点（若有多个最小点,则只取最左的最小点）和Y轴坐标值最大点（若有多个最大点,则只取最右的最大点）,作为凸壳逆时针圈绕的初始顶点;并以这两个初始顶点为端点的线段,把原二维点集划分为两个独立的子点集S右、S左。2）进行单向“圈绕寻找下一新顶点”：A）在S右内,过逆向次新顶点作X轴正向射线,并找出当前子点集内对该逆向次新顶点正向射线（为始边的）倾角最小的点,此最小点即为S右逆向最新顶点;B）在S左内,过次新顶点作X轴负向射线,并找出当前子点集内对该逆向次新顶点负向射线（为终边的）倾角最小的点,此最小点即为S左逆向最新顶点。3）删除对已得各项点所构成的子凸壳各内点。4）仅当所剩当前点集非空时才从“2）”继续作逐边双域单向圈绕。     

单域双向水平倾角最小化圈绕凸壳新算法

依据同构化凸壳构造基本定理,提出了效率更高的单域双向水平倾角最小化圈绕二维点集凸壳新算法,它实现了对卷包裹凸壳算法、单域单向水平倾角最小化圈绕凸壳算法的改进与创新.本新算法的同构化特点是：1）找出给定二维点集的最低点,即Y轴坐标值最小点（若有多个最小点,则只取最左的最小点）,并作为凸壳逆向（即逆时针）圈绕、顺向（即顺时针）圈绕的共同初始顶点（即最低顶点）.2）双向圈绕寻找最新顶点（即凸壳的下一组逆向、顺向最新顶点,而该组最新顶点＂初始组必为一个,最末组方可一个,其余组总为一对＂ ）：A.过逆向次新顶点作X轴正向射线,并找出当前点集内对该逆向次新顶点正向射线（为始边的）倾角最小的点,此最小点即为当前逆向最新顶点;B.过顺向次新顶点作X轴负向射线,并找出当前点集内对该顺向次新顶点负向射线（为终边的）倾角最小的点,此最小点即为当前顺向最新顶点.3）删除对已得各顶点所构成的子凸壳各内点.4）仅当所剩当前点集非空时才从＂2）＂继续作逐边双向圈绕.