注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

计算运动物体碰撞时间的一种算法  

2011-05-02 14:39:38|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
计算运动物体碰撞时间的一种算法 - fanhq666 - fanhq666的博客
 
计算运动物体碰撞时间的一种算法 - fanhq666 - fanhq666的博客
 
问:一个直线沿另一直线运动扫过的图形是什么?
答:一个平面
问:如何计算一个平面和一个线段的交点?
答:很简单,我给你代码
问:一个直线围绕一个轴转动形成什么?
答:一个双曲面
问:如何计算一个双曲面和直线的交点?
答:你等会,我去推公式
问:一个直线沿着另一直线运动的同时绕一轴自转,它扫过的图形是什么?
答:这……
问:如何计算它和一线段的交点?
答:我放弃……

于是,一道好题形成了:
求一个以恒定的动量和角动量运动的物体和另一静止物体相撞的时间。

能够推出公式的,请接受我深情一拜。
如果你和我是一样的凡人,那么这个怎么算呢?

首先,我们把问题简化成一个简单版的:两个线段向撞。
方法一:暴力枚举时间,挑一个距离最小的
方法二:三分搜索
不过,小心“回旋相撞”的数据呦
方法三:分段三分搜索
方法四:……
有没有又优雅又高效的呢?

我的想法:步步紧逼算法
设当前时间是t0
计算此时两个线段的距离
计算两个线段相互靠近的速度的一个估算上界
用上面两个数的商更新t0,重复这个步骤
直到两个线段的距离小于给定值(撞上了)或大于给定值(飞了)

如果速度估算值和实际值很相似,那么,它收敛的速度很快。
核心在于如何估算两个线段相互靠近的速度
上面题目中速度由两部分组成:来自动量的速度和来自角动量的速度
计算两个线段的距离,顺便计算这个距离对应的方向,之后,再计算这两部分速度的最大值和这个方向的点积即可。
实践证明,这个估算的效果很好。

于是,两个线段相碰就能在log的时间里算出来了。
那么多个线段呢?

方法1:两两向碰,分别计算
当然可以,不过,我们有一种更加快速的算法:

千帆竞发算法

把所有的线段对用一个优先列维护起来,每次找一个当前时间最小的更新它,直到碰上。
可以想象,很多“很离谱”的线段对会被淹没在优先队列底部。这样,程序的时间复杂度几乎是n^2(n是碰撞体的线段数)
为了加速步步紧逼的速度,我们要找一个合适的初始时间。我的想法是:计算两个物体包围球向撞的时间下界。这样,计算量减小很多。

有了“步步紧逼”和“千帆竞发”,我们其实已经能处理很多碰撞时间计算了。只要能计算:
1.某时刻的位置
2.速度的估算上界
那么,这个模板可以打遍天下。
例如:考虑重力、被碰撞物体也在自转……


有没有优化呢?
当然有了:
那就是,避免n^2的枚举。
一些思路:用若干个包围体把两个物体分别包起来,先在包围体的级别千帆竞发,再在线段级别计算。时间复杂度有望达到nlogn至以下。
这时,空间数据结构就要登场了……
  评论这张
 
阅读(1587)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017