基于凸壳的高密度点集物碰撞检测算法

计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (16): 51-53.

基于凸壳的高密度点集物碰撞检测算法

唐培和¹,蒋联源¹,宋佩华²,苏勤³

1.广西工学院计算机工程系，广西柳州 545006
2.广西师范学院教务处，南宁 530001
3.广西师范大学计算机科学系，广西桂林 541004

收稿日期:2007-12-17 修回日期:2008-03-03 出版日期:2008-06-01 发布日期:2008-06-01
通讯作者: 唐培和

Collision detection of high density point set based on convex hull

TANG Pei-he¹,JIANG Lian-yuan¹,SONG Pei-hua²,SU Qin³

1.Department of Computer Engineering，Guangxi University of Technology，Liuzhou，Guangxi 545006，China
2.Office of Academic Affairs，Guangxi Teachers College，Nanning 530001，China
3.Department of Computer Science，Guangxi Normal University，Guilin，Guangxi 541004，China

Received:2007-12-17 Revised:2008-03-03 Online:2008-06-01 Published:2008-06-01
Contact: TANG Pei-he

摘要/Abstract

摘要： 提出了一种基于凸壳的高密度点集物碰撞检测算法。根据高密度点集物紧密性好的特点，设计了一种快速的凸壳算法；当极值比较不能确定待检测点集物未碰撞时，用该算法计算待检测点集物的凸壳，并对凸壳进行求交运算，若不相交，两点集物未发生碰撞，否则在两凸壳的交集区域中寻找碰撞点集。算法简单、高效、可靠，在教育、国防、艺术等方面具有一定应用价值。

关键词: 碰撞检测, 凸壳, 高密度点集物, 极值

Abstract: This paper presents a collision detection algorithm of high density point set based on convex hull.According to the characteristics of the point set tightness，a fast speed convex full algorithm is designed.If extremums cann’t define un-collision，convex hull of the awaiting collision detection point set and intersection of the convex hulls are calculated.If they disjoint，the two point sets don’t collide；if they intersect，we search for the collision point set in the intersection set region of the two convex hulls.The algorithm is simple，efficient and reliable.It has the certain application value for education，defense and art.

Key words: collision detection, convex hull, high density point set, extremum

唐培和¹,蒋联源¹,宋佩华²,苏勤³. 基于凸壳的高密度点集物碰撞检测算法[J]. 计算机工程与应用, 2008, 44(16): 51-53.

TANG Pei-he¹,JIANG Lian-yuan¹,SONG Pei-hua²,SU Qin³. Collision detection of high density point set based on convex hull[J]. Computer Engineering and Applications, 2008, 44(16): 51-53.

[1]	张忠林，赵昱，闫光辉. 自然邻居密度极值聚类算法[J]. 计算机工程与应用, 2021, 57(23): 200-210.
[2]	许瀚誉，冯翔，虞慧群. 万有引力与群体状态自适应的智能优化算法[J]. 计算机工程与应用, 2020, 56(9): 48-55.
[3]	杜豪，杨岩，张成杰. 虚拟现实技术在柔性上肢康复机器人中的应用[J]. 计算机工程与应用, 2020, 56(24): 260-265.
[4]	张功森，郭翌，李永哲，裴曦，徐榭，周解平. 结合增强现实的医用加速器碰撞检测方法[J]. 计算机工程与应用, 2020, 56(17): 197-202.
[5]	吴其凡1，张劲1，刘凯1，汤炜2，田卫东2. 下颌骨拼接与导板设计的力反馈虚拟手术研究[J]. 计算机工程与应用, 2019, 55(5): 226-231.
[6]	李龙澍1，2，张效见2. 一种新的自适应惯性权重混沌PSO算法[J]. 计算机工程与应用, 2018, 54(9): 139-144.
[7]	刘满禄1，2，李铭浩2，敖天翔2，赵皓1，2. 危险环境消防侦察机器人视轴规划算法研究[J]. 计算机工程与应用, 2018, 54(23): 217-222.
[8]	孙敬荣1，2，卢新明1，2. 基于混合包围盒与三角形相交的碰撞检测优化算法[J]. 计算机工程与应用, 2018, 54(19): 198-203.
[9]	李胜1，张培林1，李兵2，吴定海1，胡浩3. 基于通用量子门的量子遗传算法及应用[J]. 计算机工程与应用, 2017, 53(7): 54-59.
[10]	徐达宇1，2，丁帅2. 改进GWO优化SVM的云计算资源负载短期预测研究[J]. 计算机工程与应用, 2017, 53(7): 68-73.
[11]	郑星星，谢明鸿，张亚运. 基于空间划分和线性规划的快速碰撞检测算法[J]. 计算机工程与应用, 2017, 53(23): 236-240.
[12]	靳雁霞，任超，李照，程思岳，王贺，韩慧妍. 融合智能算法的变形体碰撞检测算法研究[J]. 计算机工程与应用, 2017, 53(19): 130-135.
[13]	王发麟，郭宇，廖文和，黄少华. 基于距离场和扫掠剪除算法的线缆碰撞检测技术[J]. 计算机工程与应用, 2017, 53(10): 27-34.
[14]	郭海叶，窦家维，赵莲. 具线性脉冲收获的Gilpin-Ayala模型的最大存储量问题[J]. 计算机工程与应用, 2016, 52(8): 1-6.
[15]	栗真真，江开勇，林俊义. 基于极值约束的鞋底边缘立体匹配[J]. 计算机工程与应用, 2016, 52(8): 217-220.