基于散乱点集空间划分的凸壳体快速生成算法

上海大学学报(自然科学版) ›› 2009, Vol. 15 ›› Issue (5): 517-521.

基于散乱点集空间划分的凸壳体快速生成算法

上海大学机电工程与自动化学院,上海 200072

收稿日期:2008-07-10 出版日期:2009-10-30 发布日期:2009-10-30
通讯作者: 赵翠莲（1963~），女，副教授，研究方向为CAX、数字几何处理等. E-mail:clzhao@mail.shu.edu.cn
基金资助:
上海市重点学科建设资助项目(Y0102);上海市教委基金资助项目(06AZ023)

Fast Algorithm for Convex Hull Generation Based on Spatial Division of Scattered Point-Set

School of Mechatronics Engineering and Automation, Shanghai University, Shanghai 200072, China

Received:2008-07-10 Online:2009-10-30 Published:2009-10-30

摘要/Abstract

摘要：

针对凸壳体特征的三维散乱点集数据,在空间划分结构的基础上进行K近邻搜索并估算点的法向量.引入点邻域的离差计算来代替曲率计算,提取边界区域特征点集,并比较分析了两种方法的效果.最后对提取后的剩余点集进行基于法向量的分块及拟合,并在可视化工具箱(VTK)中进行布尔运算,实现凸壳体模型的生成及可视化.该方法在双底双壳船舶液舱点集数据中进行了验证.

关键词: 凸壳体;散乱点;空间划分;离差;可视化工具箱(VTK)

Abstract:

Aiming at the scattered points-set of convex hull, K- nearest neighbors searching and estimation of the normal vectors are carried out based on spatial division. Deviation calculation is used to substitute the curvature to extract the point-set with boundary-feature. Results of the two methods are compared. Blocking partition and fitting of the remaining point-set after abstraction based on normal is carried out. Boolean operation is executed in visualization tool kit (VTK) to realize the generation and visualization of convex hull. This method is verified with shipping cabin point data.

Key words: convex hull; scattered points-set; spatial division; deviation; visualization tool kit (VTK)

中图分类号:

TP 391

范志坚赵翠莲施晓磊孙亮. 基于散乱点集空间划分的凸壳体快速生成算法[J]. 上海大学学报(自然科学版), 2009, 15(5): 517-521.

FAN Zhi-Jian, ZHAO Cui-Lian, SHI Xiao-Lei, SUN Liang. Fast Algorithm for Convex Hull Generation Based on Spatial Division of Scattered Point-Set[J]. Journal of Shanghai University（Natural Science Edition）, 2009, 15(5): 517-521.

[1]	申文锋, 栗风永, 张新鹏, 杨乾星. 保持直方图特性的隐写嵌入[J]. 上海大学学报(自然科学版), 2015, 21(2): 190-196.
[2]	杨乾星, 栗风永, 张新鹏, 申文锋. 基于DCT系数修改的自适应稳健可逆信息隐藏[J]. 上海大学学报(自然科学版), 2014, 20(5): 605-611.
[3]	石娟1, 王得宇1,2, 唐刚1. 处理光学捕获运动数据的算法[J]. 上海大学学报(自然科学版), 2014, 20(4): 489-497.
[4]	何祥, 骆祥峰. 基于关联语义链网络的文本聚类方法[J]. 上海大学学报(自然科学版), 2014, 20(2): 190-198.
[5]	陈刚, 钱振兴, 王朔中. 保持纹理细节的自适应非局部均值图像降噪[J]. 上海大学学报(自然科学版), 2014, 20(1): 99-106.
[6]	任慧, 栗风永, 张新鹏, 余江. 结合重排序和直方图平移的调色板图像可逆信息隐藏[J]. 上海大学学报(自然科学版), 2013, 19(3): 254-258.
[7]	李娟娟1, 张金艺1,2,3, 张秉煜1, 周荣俊2, 唐夏2. 蓝牙4.0标准规范下的模糊指纹定位算法[J]. 上海大学学报(自然科学版), 2013, 19(2): 126-131.
[8]	马志鹏, 栗风永, 张新鹏. 基于汉明码与从属像素补偿的半色调图像信息隐藏[J]. 上海大学学报(自然科学版), 2013, 19(2): 111-115.
[9]	董贺, 徐凌宇. 基于云平台的软件服务流体系结构[J]. 上海大学学报(自然科学版), 2013, 19(1): 14-20.
[10]	裴蓓,王朔中,倪丽佳. 面向基于内容图像检索的图像感知Hash[J]. 上海大学学报(自然科学版), 2012, 18(4): 335-341.
[11]	陈岳军, 孙广玲, 姚恒. 结合小波金字塔的空频域亚像素图像配准[J]. 上海大学学报(自然科学版), 2012, 18(4): 342-348.
[12]	徐彤阳，方勇. 基于lαβ空间和抗混叠Contourlet变换的遥感图像融合算法[J]. 上海大学学报(自然科学版), 2012, 18(3): 221-226.
[13]	刘凯，扈文斌. 动态阈值模糊检测在篡改图像检测中的应用[J]. 上海大学学报(自然科学版), 2011, 17(5): 586-590.
[14]	李毅，王远弟. 基于核密度估计的图像平滑的最优停止[J]. 上海大学学报(自然科学版), 2011, 17(1): 103-110.
[15]	冯国瑞，戴宁街. 基于采样预测的安全可逆水印算法[J]. 上海大学学报(自然科学版), 2010, 16(6): 603-607.