Python使用分治法计算并可视化任意点集的凸包

==============

版权声明:由于公众号后台规则问题,本文暂时无法设置原创标记,但仍属原创内容,微信公众号“Python小屋”坚持只发原创技术文章。

=============

问题描述:

给定二维平面上任意点集,计算包围这些点集的最小凸包,并绘制折线图显示凸包多边形。

分治法思路与使用行列式计算三角形面积从而寻找距离直线最远点的实现见:Python使用分治法高效求解任意点集的凸包(源码+动画演示)

本文代码核心思路为借助于点到直线的距离计算公式寻找距离直线最远的点。设直线方程为y-kx-b=0,则任意点坐标带入直线方程后,值大于0表示在直线上方,小于0表示在直线下方,等于0表示恰好在直线中。更多算法优化与代码优化详见注释。

几次运行结果: