?
图片来自网络
摄影｜网络
#1?寻找点集的边界意义
自动驾驶碰撞检测中，对于其他交通参与者可以使用bounding_box的方式表示（类似于图像视觉中使用一个 [盒子]?将对象框起来）。
不同的障碍物占用的区域就是轨迹的不可行区域，对于激光雷达这类感知系统，形成的是一系列点云。
那么点集如何描述生成最优的边界呢？本文介绍一下三种常见的方式。
?三种不同的点集边界生成方式
#2?凸集（convex_hull）
凸集（convex_hull）是比较常用的一种产生点集的外边界方法。其主要步骤就是找已有的线段沿某个固定方向旋转，首先碰到哪个点，哪个点就加入外边界的集合。
?凸集算法示意图
①对于一系列点，首先找到这些点最上面（二维情况下就是y值最大）的点1，然后水平正方向拉一条射线。
②然后遍历剩下的每个点，沿着顺时针方向找到与①中射线夹角最小的点2。
③以点2作为新的起点，沿着顺时针方向找到剩下点中与1-2射线夹角最小的点3。
。。。
以此类推，最终回到点1，则被选中的点就构成了外边界。
多个点集的生成的外边界如下：
?
#3?quad-tree四叉树法
四叉树是把外边界等效成一段段直线段，如果线段足够细腻，那可以像素级等效出外边界。
四叉树法示意图
首先找到点集的最左上角的点和最右下角的点，然后把整个矩形四分，得到的矩形又可以无限四分下去。
只要得到的矩形和边界上的点不相交就不在细分下去，否则就一直细分到矩形足够小。
最后得到的矩形的最外围就是我们想要的外边界。
多个点集的生成的外边界如下：
?
#4?alpha-shape滚球法
凸集主要是射线围绕一个点旋转得到外边界，接下来介绍一种用一个圆（球）在点集上滚动生成外边界的方法：alpha_shape方法。
滚球法示意图
我们知道不共线的三点可以决定唯一的一个圆。那么两个点（不重合）加上一个足够的半径也可以构成一个圆。圆心就在这两个点中垂线上。
滚球法就是一个通过指定圆半径（1/alpha），然后看是否能够构成圆来寻找点集的外边界的方法。
多个点集的生成的外边界如下：
#5?总结
其实还有生成凹边界的方法：找到中心点，然后以中心点为圆心，再等分为n（比如n=64）份，每份中找到离圆心最远的点，这些点也可以构成外边界。但是这种方法生成的实在太丑了。
以上介绍的三种方法都可以生成外边界。但是在算法难易程度、需不需要调参、生成效果方面还是有一定区别，实际使用的时候可以根据需要选择合适的方法。
凸集算法比较简单快速，但是生成的结果不够细腻。四叉树算法复杂度比较高，调节的参数较多，但是运行可以很快，结果不太精确，是近似的结果。滚球法算法并不复杂，结果更加细腻，但是需要调参，应用不太具有泛化性。
?感兴趣，可以关注公众号elegantcoin，接受更多消息????
?