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

计算机科学 ›› 2007, Vol. 34 ›› Issue (11): 208-211.

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

黄涛周启海

西南财经大学经济信息工程学院,成都610074

出版日期:2018-11-16 发布日期:2018-11-16
基金资助:
西南财经大学科研基金项目（No.06K75）.

HUANG Tao ,ZHOU Qi-Hai （School of Economic Information Engineering, Southwestern University of Finance and Economics, Chengdu 610074）

Online:2018-11-16 Published:2018-11-16

摘要/Abstract

摘要： 本文依据同构化凸壳构造基本定理，提出了效率更高的双域单向水平倾角最小化圈绕二维点集凸壳新算法，实现了对卷包裹凸壳算法、单域单向水平倾角最小化圈绕凸壳算法的改进与创新。本新算法的同构化特点是：1）“初始顶点与双域生成”处理：找出给定二维点集S的最低点和最高点，即Y轴坐标值最小点（若有多个最小点，则只取最左的最小点）和Y轴坐标值最大点（若有多个最大点，则只取最右的最大点），作为凸壳逆时针圈绕的初始顶点；并以这两个初始顶点为端点的线段，把原二维点集划分为两个独立的子点集S右、S左。2）进行单向“圈绕寻找下一新顶

关键词: 同构化凸壳算法顶点射线水平倾角双域单向圈绕

Abstract: According to the isomorphic fundamental theorem of the convex hull construction, a more efficient new algorithm to find a convex hull based on coiling with a minimum lever pitch in double domain and single direction is advanced. It has realized the improv

Key words: Isomorphic,Convex hull algorithm, Vertex＇s half line,Pitch of base lines,Double domain and single direction coiling

黄涛周启海. 双域单向水平倾角最小化圈绕凸壳新算法[J]. 计算机科学, 2007, 34(11): 208-211. https://doi.org/

HUANG Tao ,ZHOU Qi-Hai （School of Economic Information Engineering, Southwestern University of Finance and Economics, Chengdu 610074）. [J]. Computer Science, 2007, 34(11): 208-211. https://doi.org/

参考文献

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed