计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (20): 61-63.DOI: 10.3778/j.issn.1002-8331.2008.20.018

• 理论研究 • 上一篇    下一篇

基于超球外壳的凸包改进算法

刘宏兵,邬长安   

  1. 信阳师范学院 计算机科学系,河南 信阳 464000
  • 收稿日期:2007-10-09 修回日期:2007-12-24 出版日期:2008-07-11 发布日期:2008-07-11
  • 通讯作者: 刘宏兵

Improved algorithm of convex hull based on super ball’s lamella

LIU Hong-bing,WU Chang-an

  

  1. Department of Computer Science,Xinyang Normal University,Xinyang,Henan 464000,China
  • Received:2007-10-09 Revised:2007-12-24 Online:2008-07-11 Published:2008-07-11
  • Contact: LIU Hong-bing

摘要: 根据凸集中只有最外围的点才有可能是凸点而中心附近的点不可能成为凸点的特性,提出了一种基于超球外壳的凸包改进算法。首先选取给定凸集点的中心,计算所有点与该中心的距离,并对该距离进行归一化处理,使所有的点都映射到一个单位超球体内;其次,选取合适的参数,提取单位超球体的外壳,用外壳中的点构造其凸包。

关键词: 凸集, 凸包, 凸点, 超球外壳, 可见线, 可见面

Abstract: An improved algorithm of convex hull based on the super ball’s lamella is proposed in terms of the character that only the outmost points of the convex set may be the convex points and the points nearby the center of the convex set can not be ones.Firstly,the distances between the central point and all the points in convex set are computed and unified after selecting the center of the convex set,so the entire points are mapped into the identity super ball.Secondly,the suitable parameter is selected to extract the super ball’s lamella which is used to construct the convex hull.

Key words: convex set, convex hull, convex points, the super ball’s lamella, visible line, visible facet