杂记

多边形的碰撞检测:

之前参加了D公司的笔试,其中最后的一道题目是:分析两个凸多边形的碰撞检测算法,主要是要以分析机器人与障碍物之间的碰撞情况:我们已知两个凸多边形的各个顺序定点的的二维坐标,求一个碰撞检测算法。

最开始的时候,因为紧张,没有什么好的思路,就给了一个最简单的算法:求出多边形的形心,然后以其为圆心,求出凸多边形的最小包络圆,然后我们通过对两个圆的碰撞情况的分析来近似多边形的碰撞。这种思路简单直接,容易想到,而且他的计算复杂度和空间复杂度也不高。如果假设机器人的旋转中心就在其几何中心上,考虑到机器人的旋转,这是一个很合理的算法,也是最安全的算法。

话虽如此,但是上述的方法并不够精确,机器人本来可以通过的狭长缝隙,如果按照上面的“安全算法”,可能就变得无法通过了。这时候我们需要有更精确的算法。两个多边形的碰撞即是两个多边形是否相交,换一种说法就是,是否存在一条直线能够将两个多边形分成两类。到这里,SVM似乎自然而然的就成了一个较好的方法了。我们将两个多边形的点作为两个类别的数据,然后输入到SVM中进行训练,不使用高斯函数,不使用软边界等。如果我们能得到一条严格的分界的直线,我们就可以说两个多边形是可分离的,也就是不会碰撞的。否则,我们就认为两个多边形是碰撞的。这是基本思路。

SVM的原理和讲解网上很多很充分,此处故不展开。一下给出基于sklearn的一个演示demo:

一个简单的生态平衡的向量场模型:

捕食者-猎物系统也称为Lotka-Volterra系统,由下式表示:

$$\left\{ \begin{array}{lr} \dot{x}_1(t)=(1-x_2(t))x_1(t), & \\ \dot{x}_2(t)=(x_1(t)-1)x_2(t) \end{array}\right.$$

其中,\(x_1\)表示猎物的数量(以千计数),\(x_2\)表示捕食者的数量(以千计数)。显然,当我们令\(x_1\)为0时,\(x_2\)的微分方程的解是一个指数函数,即\(x_2\)会以指数的形式增长。反之亦然。如果我们把\(x_1\)和\(x_2\)当作状态量,那么上述方程的左边刚好是其一阶导数方程,即是一个向量场。如下图是其在(0,2)X(0,2)区域内的向量场。

我们可以看到,当\(x_1\)和\(x_2\)位于(1,1)时,向量场达到了动态平衡。当状态量不在动态平衡点时,它会沿着向量场逐渐到达平衡点,与起始位置无关。当我们调整生态中的一些变量,比如提供更大的空间,更多的食物,事实上我们就是移动了动态平衡点,\(x_1\)和\(x_1\)会沿着新的向量场到达新的动态平衡点。这个过程可是通过泰勒展开的方式来实现动态模拟。