Python使用分治法高效求解任意点集的凸包（源码+动画演示）

问题描述：

凸包（Convex Hull）可以理解为能够包围给定点集的最小凸多边形，是计算机图形学及其相关领域中的一个重要问题，在游戏中进行物体碰撞检车时使用的包围盒其实就是凸包。

求解给定点集的凸包可以使用分治法来高效实现，每次使用点集中左右跨度最大的两点构成的直线把点集分为上下两部分，然后在上侧点集中寻找距离直线最远的点，与直线两端点构成三角形，以三角形新增的两条边继续对点集进行分隔，多边形的边越来越多，直到没有更外侧的点为止，类似于分形算法生成雪花形状或者使用正多边形逼近圆周的过程。对直线下方的点集也做同样的处理，最终得到原始点集的凸包。

参考代码：

运行结果：https://mpvideo.qpic.cn/0bc3diac4aaaoianuo63bjsvagwdfynaalqa.f10002.mp4?

https://mpvideo.qpic.cn/0b2e24accaaap4anl263absvbv6dehlqaiia.f10002.mp4?