杂记

多边形的碰撞检测:

之前参加了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\)会沿着新的向量场到达新的动态平衡点。这个过程可是通过泰勒展开的方式来实现动态模拟。

GPU编程终瞥

到此,经由前三篇文章的说明,我们对gpu编程应该有了很大的认知,基本上可以完成一些简答的开发小任务了,其实cuda的功能还包括很多,这个系列就不一一介绍了,最终篇,我们介绍一下cuda GPU编程在实际工程中的代码调用吧。

继续阅读“GPU编程终瞥”

GPU编程一瞥

之前因为SLAM中计算描述子的缘故,想到通过GPU加速编程来提高SIFT描述子的计算速度,从而达到实时的效果。于是前段时间就了解了一下GPU编程。本来该篇博客在更早的时候就应该写的,但是由于自己的拖延症,一直挨到了今天,心想,实在不能再拖下去了。本系列基本以该书为基础,对书中的部分代码作了大幅度改动,修正了其中的一些运行结果,并引入了OpenCV和cmake,使得gpu编程更加工程化。系列中的代码都可以在我的github主页中找到。

继续阅读“GPU编程一瞥”

记在美英法袭击叙利亚事件之后

从小到大,我们接受了无数的爱国教育。相较于停留在书本、宣传画里的爱国教育,现实中血淋淋的教训无疑来得更深刻、更直击人心。

2018年4月14日,以美英法对叙利亚发起了导弹袭击,理由是叙利亚政府军在战争中使用了化学武器,造成了极大的平民伤亡。具体的事实我们不清楚,单从逻辑的角度讲,叙利亚政府在占据极大的优势的情况下会去使用化学武器吗?难道政府不知道这样只会遗人以口实,招致列强的干涉吗?伊拉克战争前夕的借口,美国驻联合国代表还有模有样的用了一小管的“洗衣粉”,称伊拉克政府有大规模莫杀伤性武器,而现在,连这些面子工程都懒得做了。 继续阅读“记在美英法袭击叙利亚事件之后”

有意思的数学

\(\frac{1}{2}\)
每次在知乎或者书上看到有一些违反直觉的理论的时候,我就深深的觉得,这个世界上最强装*一定是数学家,他们装起来连黑洞视界都可以逃逸。

前两天在知乎上看到了黎关于曼猜想的话题,饶有兴趣的去了解了一下,然后又根据推荐去看了黎曼猜想的一个视频系列(three blue one brown),这个视频深入浅出的介绍了黎曼猜想。

介绍了从一般收敛级数求和、调和级数的发散,变换指数到复数域得到\(\zeta(s) \)函数,顺便简单地说明了虚数指数的意义,当Re(s)>1,\(\zeta(s) \)函数是自然的,且有意义的,但是Re(s)<=1是没有良好定义的。为了把定义域推广到整个复平面,然后解析沿拓\(\zeta(s) \)到整个复平面,最后给出了\(\zeta(-1) =-\frac{1}{12}\)这样的结果,这就是网络上所谓的\(\sum_{k=1}^{\infty} \frac{1}{k}=-\frac{1}{12}\)的由来。

另外该系列还介绍了线性代数的几何意义,因为是视频的缘故,很多抽象的东西得以通过图形几何来表达,很多静态的方程和矩阵能够通过动态的视频变化来演示,整个系列循序渐进,从向量到矩阵,然后是矩阵的几何意义,然后还有关于矩阵的行列式、逆、特征值等等的直观说明,最后还将向量从一般的几何空间推广到抽象空间,比如函数空间。对于线性代数的感性理解有极大的帮助。

另外其他的系列还有诸如分形几何、微积分等等,总之,超棒,很喜欢,强推!