滚球法的思想最初源自于从二维点集重建平面形状的问题，后来笔者将这个思想用于做平面曲线的简化。

例如，下面的平面点集，如何构建其分布区域表示的大致轮廓形状呢？

       笔者最初想到的一个从求凸包的Graham Scan算法衍生出来的一个方法。求凸包的Graham Scan算法先找到一个Y最低的点作为起始点，然后使用叉积角度判断的方法去判断点的走向，最后在栈内留下了凸包的点序列。具体的算法讲解与代码，网上一搜各种有，这里就不详细表述。本文要介绍的方法也是和Graham Scan法从同一个出发点出发，通过扫描角度来确定下一个点。具体算法流程从下面的图文说明可以大致看出来：

首先要实现这个算法，需要对随机的一个点查询距离其几何距离在R内的所有点，即求所谓的R邻域。这个R邻域算法是KNN（K-nearest neighbors）算法的一个变形，可以在小于O(n2)的复杂度下求取R领域，本文为了简单起见没有实现这个基于K-d Tree的算法，感兴趣的读者可以查阅相关资料了解这个算法。本文涉及的应用场景因为点数目不大，所以使用的方法没有过多考虑效率，实现R邻域的方式是先建立一个n*n的二维数组存储所有点两两之间的距离，然后遍历一次二维数组，为所有的点建立一个R邻域列表，该列表中存储了对应点R邻域的索引值，这个列表很有用，下面要介绍的滚球法也利用了这个列表。

　　实际上不难理解，假设AB为凹包的一个边，那么其下一个点C必然是在B的R邻域点中选择。我们实现这个算法的关键，就是为AB边找一个合适的C点。这里笔者设想的寻找C的方法使用如下原则：

　　这里涉及到一个小算法，即所谓的极坐标方向排序问题，这个问题的描述是：给定一个原点P和一个初始方向n，如何为平面上的点集S排序，使得点集中的点P1,P2...PN与P的连接是按从n开始的逆时针排列的。这个问题搜一搜stackoverflow即得到一个很好的解答，这个链接里一个人给出一个用于比较的函数，一旦有了比较函数，排序也不成问题，这个比较函数在后面的方法中会出现。其具体的比较原理如果对向量的点积叉积有所了解也不难理解。这里不妨提一下点集叉积的结果符号的几何含义：

　　那么找C点的第二条实现的方式就类似于对一个数组找最小值那样，通过比较找到最小的角度，这个有最小角偏向的就是C点。不过遗憾的是这个思路其实是问题的，测试表明对一些点集采用这个方法会有BUG出现。例如当C点出现在BA向量小于90度的方向时，形成的BC边和AB边具有大致相反的方向，会导致下一步的寻点出现逆向，故这个思路不算是一个成功的思路，不过失败是成功之母，它却引出另一个滚球法的思路，相比这个思路具有更好的鲁棒性。

        对于任何点集，我们把这些点想象为钉在平面上的钉子。假如拿一个半径大于一定值的球去从边界接近这个钉群，我们可以用这个球在这些钉子群的边界滚一圈，每次滚动，球都能接触到两个钉子而被卡住。

　　这个思路要求一个合法的R，R太小就没法形成一个闭合的图形。由于我们讨论问题的初衷是要形成一个合适的多边形而不是0个或多个，这样对R的选择就应该有一个限制，太小的R必然出不了结果，这里姑且假设给的R值是合适的。此过程若形成一个多边形，则多变形的最长的边一定小于球的直径。所以算法输入参数为R，意味着拿一个半径为R/2的圆去滚。如下图显示了这个滚球的过程：

       我们不难发现一个性质，对于任何一次翻滚，假设从弦DE翻转到新弦EF，圆不可能扫过任何的其他点，因为假如扫到其他点，必然会被这个点所卡住，那么新弦就不可能是EF了。这样我们只需对极坐标排序后的E点的R邻域依次寻找符合不覆盖其他点的圆即可。

这个算法的执行过程和滚边法相似，算法结构都是先找起始点，然后循环寻找下一个点，核心问题也是从边DE线段出发找新线段EF，只是不再使用边去扫，而是用圆去扫。这里先给出这个算法的大致步骤：

　一旦R值给的比较好，这个过程一定能给出一个闭合的图形。下图为滚球法执行过程的图片示例：

对于平面多段线，由于其连续两点的连线代表了边，边已经表示了图形的轮廓，因此需要对边进行足够密的采样。采样间距一般小于球半径即可。

在滚球法的每一步，我们需要计算下一步可能滚到的点，也就是R领域中的点，如果搜索所有点，那就复杂度太高了，时间复杂度将达到O(N2)。

但是如果注意到这样一条性质：

对于平面简单曲线，在滚球法的每一步，下一个滚到的点，不可能越过下一个凸包上的点。

根据这个性质，我们就只需要搜索，本次滚到的点到下一个凸包点之间的点即可。这样大大减少了搜索区间，实测时间复杂度降低到接近线性。

如下两幅图中的示例，绿色线表示原图，黄色点表示最后滚到的点，粉色线表示最后的简化结果。