讯飞智能救援赛后总结
前言 整个比赛差不多花了3、4个月，可算是结束了。名次上预估国二 开头先吐槽一下讯飞二代车的诸多硬件问题，麦克风扬声器摄像头总会检测不到、雷达漂移断点甚至在某个方向还有一片死区、小车wifi不稳定远程连接总是断开、开关机只能通断电源没法软件上操作不然那个b风扇就会狗叫个不停、陀螺仪的逆天输出原地不动的情况下还会在10cm范围内反复震荡(md小车最小通行距离也就50cm)，整台车甚至在工作半小时后就会开始出现各种玄学问题。就这车，可以说给我带来了非常糟糕的比赛体验，但好在为了解决这些问题还是学到了新东西。 客观来说我觉得比赛的内容并不困难，主要的障碍还是小车的硬件环境。摄像头高度太低不知道是不是命题人有意为之，确实要比常规巡线困难不少。不过我主要还是做的寻找工具那块，初看赛题内心很糟糕，因为在此之前没有任何处理雷达数据的经验，最后只能尝试用计算几何的知识硬算(我计算几何学得很烂w_w)。 正文 具体来说，场地内，雷达能扫到的只有边界和板子，只要想办法过滤掉边界，对剩下的板子枚举就好了。问题就是怎么过滤掉边界，可以注意到边界为矩形(黄色区域)。 只要小车在黄色区域内运动，雷达总会获取到这个矩形的信息，但是由于有板子的遮挡，你并不能完全拿到这个矩形，当你试图补全这个矩形，你就会发现，这个矩形刚好是雷达读取到的所有点的最小外接矩形。 那么问题就转变为：“给定一个子元素为(x,y)的点集，求它的最小外接矩形。” 对于这个问题，我的做法是先用Graham算法求出点集的凸包，再根据最优情况下至少有一条矩形边与凸包的边重合，枚举凸包的边求出矩形。 关于如何求解凸包和Graham算法的内容，可以看这篇文章数论小白都能看懂的平面凸包详解 - 洛谷专栏 求完凸包后，我们需要对于凸包的每条边，找出满足下面条件的矩形。 以这条边所在直线的一部分为一边 包含这个凸包的所有点 面积最小 答案即为这些矩形中面积最小的一个。 贴一下第一个条件的证明，另外两个很好理解，因为是外接矩形，它当然至少要包含所有的点，同时保持面积最小 怎么找这些矩形，这是个问题，看看这张图 为了方便起见，当前正在考虑的边画成水平。 我们要分别求出最右、最上、最左的点(点的数量很少，枚举每一个凸包内的点即可，比如分别枚举ABCDQP)，再加上当前边一定包含最下的点，这样便能得到矩形的长宽。 但是不喜欢枚举怎么办…