gjk_algorithm
介绍
GJK简写为Gilbert–Johnson–Kererthi
GJK算法在很大程度上依赖于称为闵科夫斯基和的概念。
闵科夫斯基和
配备了两个形状,这些形状的闵科夫斯基和就是shape1中的所有点加到shape2中的所有点上{得到的是另外一个更大更复杂的形状}:
头铁
想法1
根据排序求出定点之间的坐标差
将三三点之间用三角形连起来,求原点在不在其中
想法2
求出最大的凸矩形
从横坐标最小的点,斜入射正无限开始,依次寻找下一个坐标点。
求出该点与其他所有点的斜率,找到小于当前斜率的取代下能形成最大斜率且横坐标大于等于该点的点。
直到找到横坐标最大的点为止。再从该点,斜入射正无限开始,依次寻找下一个坐标点。
具体过程为,求出该点与其他所有点的斜率,找到小于当前斜率的对准下能形成最大斜率且横坐标小于等于该点的点。
直到找到初始位置为止。
求原点在不在这个凸矩形