讯飞智能救援赛后总结
前言
整个比赛差不多花了3、4个月，可算是结束了。名次上预估国二
开头先吐槽一下讯飞二代车的诸多硬件问题，麦克风扬声器摄像头总会检测不到、雷达漂移断点甚至在某个方向还有一片死区、小车wifi不稳定远程连接总是断开、开关机只能通断电源没法软件上操作不然那个b风扇就会狗叫个不停、陀螺仪的逆天输出原地不动的情况下还会在10cm范围内反复震荡(md小车最小通行距离也就50cm)，整台车甚至在工作半小时后就会开始出现各种玄学问题。就这车，可以说给我带来了非常糟糕的比赛体验，但好在为了解决这些问题还是学到了新东西。
客观来说我觉得比赛的内容并不困难，主要的障碍还是小车的硬件环境。摄像头高度太低不知道是不是命题人有意为之，确实要比常规巡线困难不少。不过我主要还是做的寻找工具那块，初看赛题内心很糟糕，因为在此之前没有任何处理雷达数据的经验，最后只能尝试用计算几何的知识硬算(我计算几何学得很烂w_w)。
正文
具体来说，场地内，雷达能扫到的只有边界和板子，只要想办法过滤掉边界，对剩下的板子枚举就好了。问题就是怎么过滤掉边界，可以注意到边界为矩形(黄色区域)。
只要小车在黄色区域内运动，雷达总会获取到这个矩形的信息，但是由于有板子的遮挡，你并不能完全拿到这个矩形，当你试图补全这个矩形，你就会发现，这个矩形刚好是雷达读取到的所有点的最小外接矩形。
那么问题就转变为：“给定一个子元素为(x,y)的点集，求它的最小外接矩形。”
对于这个问题，我的做法是先用Graham算法求出点集的凸包，再根据最优情况下至少有一条矩形边与凸包的边重合，枚举凸包的边求出矩形。
关于如何求解凸包和Graham算法的内容，可以看这篇文章数论小白都能看懂的平面凸包详解 - 洛谷专栏
求完凸包后，我们需要对于凸包的每条边，找出满足下面条件的矩形。
- 以这条边所在直线的一部分为一边
- 包含这个凸包的所有点
- 面积最小
答案即为这些矩形中面积最小的一个。
贴一下第一个条件的证明，另外两个很好理解，因为是外接矩形，它当然至少要包含所有的点，同时保持面积最小
怎么找这些矩形，这是个问题，看看这张图
为了方便起见，当前正在考虑的边画成水平。
我们要分别求出最右、最上、最左的点(点的数量很少，枚举每一个凸包内的点即可，比如分别枚举ABCDQP)，再加上当前边一定包含最下的点，这样便能得到矩形的长宽。
但是不喜欢枚举怎么办，其实还有一个O(n)的算法：旋转卡壳，具体可以看这篇文章 计算几何系列 —— 美妙的旋转卡壳算法~上_旋转卡壳法
当然也有另有一个选择：K-D Tree，K-D Tree 最典型的应用应该是求平面 k 远点对（传送门），但是我并没有尝试过，主要是后续对板子的点进行聚类会再一次用到KD树所以提一嘴
求出所有满足条件的矩形，取面积最小的即为最小外接矩形
然后把雷达上所以距离矩形边 x cm的点删掉(这个 x 可以自己定，因为雷达的点会在边界旁边跳变，所以最好设置一个死区)
到此为止你手上剩下的点只剩下板子了，用KD树或者并查集对剩下的点进行聚类(一开始我是打算用并查集做的，但是网上转了一圈发现大伙都用KD树，本着时间紧任务重的原则我也没瞎折腾)
那么板子的左右端点，相对于小车的位置信息等等全都拿到了，我们只需要在板子的两侧画一个60*60的框判断能否找到一个能使小车安全停泊的点，找到就告诉小车没找到跳过就好
按理说任务到此已经结束了，但是由于movebase的定位不准（我不得不怀疑是小车的硬件问题还是movebase的算法问题导致的），即使已经知道了板子准确的相对位置信息，小车仍旧无法准确停泊在目标点，这意味着我们需要pid控制额外的做一次位置校正。
这里有一个细节就是 雷达获取到的信息是相对于雷达坐标系的，如果不做进一步的坐标转换而直接使用雷达的信息做矫正，就有可能导致雷达本体是处在60×60cm框内，而小车的屁股（就是那两个后轮）处在框外 （国赛得分-10 ╥﹏╥）