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

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

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

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

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

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