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

计算机科学 ›› 2008, Vol. 35 ›› Issue (2): 235-237.

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

出版日期:2018-11-16 发布日期:2018-11-16

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

摘要/Abstract

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

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

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 double direction is advanced. This new algorithm isomorp

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

. 基于双域双向水平倾角最小化圈绕的凸壳新算法[J]. 计算机科学, 2008, 35(2): 235-237. https://doi.org/