★csdn的算法高手们,有问题向大家求助
问题描述:
现有大小不同的圆形粒子若干,在一水平平面上运动,运动规律不用关心,现在关注的重点是粒子碰撞检测。
传统的算法:
算法一:缩小时间间隔,定时检测是否相交,就是遍历粒子,看两粒子间距是否大于粒子半径和。但是这种不精确,可能出现粒子轨迹交叉度太大而无法检测到。淘汰!~~
算法二:包围盒检测,由于要求精确度较高,这种算法淘汰!~~~
算法三:在短时间间隔中检测粒子运动轨迹(直线)是否相交。这种精确度高,但是时间复杂度太大,淘汰!~~
算法四:N叉树。即划分网格,检查粒子所在网格的就近网格里面的粒子。这种算法要求粒子大小相同。淘汰!~~
这里的难点是粒子大小不同。目前可用算法一,将时间分隔成足够小的片段来检测。但是遍历粒子过程中耗时太长。
大家畅所欲言,只要算法原理即可,不用代码。
望大家不吝赐教!~~