最近遇到一个求二维点集凹包的问题，凹包的叫法不知道是否准确，问题可以描述为：(原文下载在文章末尾)
在二维平面上有一系列的点，求能包围所有点集的二维多边形。(好像搜“离散点边界”或“点云边界提取”比凹包更准确)
这个很容易想起二维凸包问题，目前已经有很多算法实现点集的凸包，凸包：https://en.wikipedia.org/wiki/Convex_hull ，这里不再赘述。
主要介绍二维点集凹包的一些算法，这里只做大致介绍，不做详细叙述。
通过网上查找资料，网址http://www.tuicool.com/articles/iUvMjm
介绍了计算凹包的3中方法，且在github上有源码下载链接，感兴趣的可以下载测试。
基于Delaunay三角化，如左图，先将所有的点进行Delaunay三角化，然后删掉太长的边得到点集的凹包。
滚边法(Edge Pivoting)，先找到一个凸点作为起始点，一般取y最小的点，顺时针查询距离其几何距离在R内的所有点，即求所谓的 R邻域 ，对R邻域的点集进行排序，再在领域中一个点作为连接点，再以此点作为起始点求R邻域。但是这个算法作者实现的并不是很稳定，总是出现一条单边，而不是多边形，但是还是要感谢作者无私奉献源码。
滚球法(Ball Pivoting)，这个是比较稳定用得也比较多的方法，引用作者的话：对于任何点集，我们把这些点想象为钉在平面上的钉子。假如拿一个半径大于一定值的球去从边界接近这个钉群，我们可以用这个球在这些钉子群的边界滚一圈，每次滚动，球都能接触到两个钉子而被卡住。可知如果球的半径越小，越精细。
下面介绍目前求凹包的几种其它算法。
还是上一个网址提到的alpha shape ，参考文献：Edelsbrunner H, Kirkpatrick D, Seidel R. On the shape of a set of points in the plane[J]. IEEE Transactions on information theory, 1983, 29(4): 551-559.
感觉就是滚边法，球的半径参数α越大，边界多边形越接近凸包，α越小，越接近凹包。
搜索盒的边界搜索算法，参考文献：jqdws, 魁梧的电灯胆. 平面离散点集的边界搜索算法[J]. 计算机仿真, 2004, 21(3): 21-23.(这也是我想到的实现方法，结果已经有人早就实现了，看来做项目之前真的是需要多多调研)
算法将一系列的点集根据搜索盒(矩形)分类，找到边界搜索盒，再讲边界点链接起来。
行列法，参考文献：袁满, 飘逸的冰淇淋. 一种基于行列法离散点边界搜索算法倡[J]. 计算机应用研究, 2010, 27(11).
先给定一系列离散点集，按行进行搜索，求每行的最大最小值，链接成多边形，再按列搜索，求每列的最大最小值，行列搜索结果相结合，进行边界修正，得到边界多边形，最后进行光顺处理。