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

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

对《一个快速的多边形凸包求取算法》的修改

<正> 在贵刊1988年第5期(总227期)所载《一个快速的多边形凸包求取算法》一文的第三节,给出有一个对点可见多边形的凸包求取算法。所给出的算法(以下简称原算法)有一些不够清楚的地方,看来做些修改是必要的。显然求凸包的点可见多边形的顶点数应大于3,开始考察时应设头二个顶点已取为是凸包上的顶点,故应初始化为i=3,j=2。值得注意的是原算法步z所做的斜率比较     

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

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

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

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

一个多边形填充的快速算法

本文提出一种实用的简单多边形快速填充算法，它人有裁剪与填充双重功能，也可完成单纯的裁剪操作。     

改进的三维点集凸包求取算法

为提高三维点集凸包的求取效率,提出充分利用凸包极值点和性质改进的三维点集凸包求取算法.首先,求出三维点集中的极值点,并由它们形成初步凸包;其次,根据初步凸包与点的位置关系,排除其内部点;最后,依次考察其外部点,求出符合要求的点集、棱边集和面集,并对凸包进行扩展,得到凸包的点集、棱边集和面集.与普通算法进行时间的复杂度分析比较及实验表明,该算法效率较高.     

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

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

一个快速有效的凹多边形分解算法

文中在简述了传统的矢量法分解凹多边形算法之后,提出了一个快速有效的凹多边形分解算法,该算法避免了矢量法所需的大量,复杂的求交计算,因此该算法在时间及计算复杂性方面远远优于矢量法,而且该算法在三维环境中同样适用,该算法除了在多边形裁剪中有广泛的应用外,在多面体的消隐中也经常用到,并用Visual C 语言实现。     

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

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

基于凸包求解的简单多边形方向判断新算法

Graham ScanA求解简单多边形凸包算法简洁高效,但是对于未确定方向的简单多边形,该算法需设定一个方向求解其凸包。提出一种新的算法,该算法通过利用凸包求解的Graham ScanA算法来判断简单多边形的方向。算法取得了较好的实用效果。     

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

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

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

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

一个有效的多边形裁剪算法

通过对相交多边形交点的完备分类,给出了一个可靠的任意多边形裁剪算法.结果表明,该算法非常稳定可靠,且能处理各种奇异情况.     

一个有效的多边形裁剪算法

多边形裁剪与线剪裁相比具有更广泛的实用意义,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,既可以是凹多边形,也可以是有内孔的多边形.该算法不仅可以求多边形的"交"(多边形裁剪),而且可以求多边形的"并"和"差".它是以所提出的一系列新方法和新技术为基础而形成的.首先,该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,具有占用空间少及处理速度快的特点;其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.与其他同类算法进行了比较,结果表明,新算法具有最简单的结构和最快的执行速度.     

判断简单多边形的核是否为空的一个快速算法

简单多边形的核是位一这形内部的一个点集,从其中任意一点可见多边形的全部边界,文中考查了简单多边形的核在构成同性质,结构已有结果,提出了一个算法,该算法能快速地判断简单多边形是否有核,有核时间以方便地求出核中一个顶点,对算法进行简单扩展,可以求得核中一边及完整的核,给出的算法容易理解,便于实现,可以广泛地应用于一些涉及可见性的问题及许多其它问题中。     

图象处理中多边形拟合的快速算法

提出了一种简单高效的多边形拟合算法 ,不必采用递归调用的方法 ,仅在对目标图象的边界数据的一次遍历中 ,即可计算出所有的多边形拟合点 ,避免了递归调用中的重复运算 ,有利于计算机图象的实时处理和在线检测。实践证明 ,采用这种算法可得到满意的结果。     

平面点集凸包快速构建算法的研究

文章提出了一种提高构建凸包速度的新方法。该算法生成一个网格来管理离散点,在淘汰明显不位于凸包上的点时,将对离散点的取舍转换为对格的取舍,计算工作量只与离散点的范围及网格的密度有关,与离散点的数目无关;同时对点集也进行了初略的排序。在求取剩余点集的凸包时,采用了一种先分段求取凸包边界,最后将这些边界合并成凸包的方法,该方法充分利用了剩余点集所具有的有序性。     

一种任意多边形裁剪快速算法

提出一种用VC++语言实现的多边形裁剪快速算法。与以往的算法相比,算法中不仅多边形可以是任意的,而且在求交、并和差的过程中用符号判断代替耗时的乘法运算,采用预处理方法等技术来减少程序的遍历次数,从而加快了计算速度。算法中用MFC的CObList类和CArray类的对象来动态存储数据,大大节约了内存开销,是一种高效的算法。另外,算法编制的软件,已得到了有效的应用。