第22卷第8期 计算机辅助设计与图形学学报 V01．22No．8

of

2010年8月 Journal

Computer—AidedDesign＆ComputerGraphics Aug．2010

用圆锥体拟合线性模型点云数据的优化计算

孙春娟1’2’”，朱滨海”，王文成"

”(中国科学院软件研究所计算机科学国家重点实验室北京100190)

2’(装备指挥技术学院信息装备系北京 101416)

3’(中国科学院研究生院北京100049)

of Science，MontanaState USA)

”(DepartmentComputer University，Bozeman，MT59717

(suncj@ios．ae．cn)

摘 要：针对采用最小圆锥形(包括圆柱、圆锥和圆台)拟合任意轴向的线性模型的点云数据这个NP一难问题，提出

一种优化算法．该算法将具有n个点的点云模型自适应地分解成一些子集，并对每个子集用一个圆锥来拟合，

使得圆锥包含对应子集内所有点，且拟合圆锥的体积小于最优解的(1+e)倍．其中圆锥拟合方法的时间复杂度为

O(nh3)，s是用户给定的拟合误差，优于已有最快拟合方法的复杂度．实验结果表明文中算法是快速有效的．

关键词：几何重建；近似算法；最小包围圆锥

中图法分类号：TP391

ConicalReconstructionofLinearPointClouds

Optimizing

Sun Binhai”，and

Chunjuanl'2，”．Zhu WangWenchen91’

1’(State Science，InstituteChinese i00190)

Key of of

LaboratoryComputer SoftwareA(ademyofSciences，Beijing

of Commandand 101416)

”(DepartmentInformationEquipment，AcademyofEquipment Technogogy，Beijing

”(Graduate Chinese 100049)

Universityof AcademyofSciences，Beijing

State

4’(DepartmentofComputerScience，Montana USA)

University，Bozeman，MT59717

conical

thesmallest andconefrustums)

Abstract：Finding objects(namelycylindricalsegments，cones

toencloseasetoflinear3D isa NP—hard this

points strong problem．Inpaper，an

tothis is dividesthesetofn into

algorithmNP—problempresented。Thealgorithmadaptively points

subsets，andthen subsetaconical is

approximatesevery by objectrespectively．Thealgorith