网站 系统 区别,微信公众号同步wordpress,公司设计网站建设合同,建设工程信息服务平台官网在游戏开发和机器人路径规划乃至于现在比较火的自动驾驶中#xff0c;我们常常需要确定两个物体是否发生碰撞#xff0c;有一种通过闵可夫斯基差集法求是否相交的算法#xff0c;下面将介绍一下
闵可夫斯基差集法的优势
闵可夫斯基差集法优势#xff1a;
可以处理复杂的…在游戏开发和机器人路径规划乃至于现在比较火的自动驾驶中我们常常需要确定两个物体是否发生碰撞有一种通过闵可夫斯基差集法求是否相交的算法下面将介绍一下
闵可夫斯基差集法的优势
闵可夫斯基差集法优势
可以处理复杂的形状和多边形/多面体。提供精确的接触点和分离向量信息。
AABB的优势
不像AABB一样简单快速只需要几次比较就可以完成相交测试可生成AABBTree快速排除不可能相交的物体
可以看出AABB更快闵可夫斯基差法更准所以可以拿AABBTree缩小检测目标范围最后精准检测的时候可以用闵可夫斯基差集法 闵可夫斯基差集法图形求交
有两个相交的图形A和B 在A中取一个点A1和B中的所有点求差 将图形连接起来 再在A中取一个点A2和B中的所有点求差 取A3和B中的所有点求差 其实在这里原点出现在了生成的图形中就可以终止循环了我后面优化部分会提到
取A4和B中的所有点求差 连接所有结果 可以看到原点在闵可夫斯基差集的图形中则成两个图形存相交情况
如果没有交点也就不存在焦点了
测试代码
import numpy as npdef minkowski_difference(A, B):计算两个多边形A和B的闵可夫斯基差diff []for a in A:for b in B:diff.append(a - b)return np.array(diff)def is_origin_inside(polygon):检查原点是否在多边形内部return true/falsedef polygons_collide(A, B):判断两个多边形是否碰撞# 计算闵可夫斯基差difference minkowski_difference(A, B)# 检查原点是否在差集内return is_origin_inside(difference)# 示例定义两个多边形的顶点
polygon_A np.array([[0, 0], [2, 0], [2, 2], [0, 2]]) # 正方形
polygon_B np.array([[1, 1], [3, 1], [3, 3], [1, 3]]) # 另一个正方形与A相交# 检测碰撞
collision polygons_collide(polygon_A, polygon_B)
print(Polygons collide:, collision)
优化
①闵可夫斯基差的几何意义是所有可能从一个多边形内的任一点到另一个多边形内任一点的向量集合。而上面的方法生成的是一个点集而不是这些点构成的实际几何形状通常是凸包,因此许多计算出来的点对于确定原点是否在闵可夫斯基差内部是没有必要的
我上边到A3遍历的时候就已经知道相交了就直接可以是否相交了没必要再计算A4了
要避免不必要的计算我们可以优化minkowski_difference函数使其不生成完整的闵可夫斯基差集。我们可以在检测过程中动态地生成差异点并且一旦发现原点位于闵可夫斯基差内就可以立即返回结果而不需要继续计算简单优化下
import numpy as npdef minkowski_difference_check_origin(A, B):检查原点是否在两个多边形A和B的闵可夫斯基差内for a in A:for b in B:diff a - bif is_origin_inside_single_point(diff):return Truereturn Falsedef is_origin_inside_single_point(point):简单检查单个点是否非常接近原点return true/falsedef polygons_collide(A, B):判断两个多边形是否碰撞# 动态检查原点是否在闵可夫斯基差内return minkowski_difference_check_origin(A, B)# 示例定义两个多边形的顶点
polygon_A np.array([[0, 0], [2, 0], [2, 2], [0, 2]]) # 正方形
polygon_B np.array([[1, 1], [3, 1], [3, 3], [1, 3]]) # 另一个正方形与A相交# 检测碰撞
collision polygons_collide(polygon_A, polygon_B)
print(Polygons collide:, collision)当然了这个碰撞算法不是最佳的有更加好的GJK算法是一种优化后的技术它巧妙地利用了闵可夫斯基差的概念但在实际应用中避免了直接计算其所有点所带来的高昂代价
后面我将会更新GJK算法的文章
补充
注意是Minkowski Difference(闵可夫斯基差集)不是Minkowski Distance(闵可夫斯基距离)虽然都来源于数学家赫尔曼·闵可夫斯基的工作但它们是两个不同的概念应用领域也有所不同这里注意区分
