二维几何重建

问题背景

　　近期遇到一个计算几何问题，需要从点集中重建一个合理的几何形状。这个问题既有二维的也有三维的，二维的情况相对简单一点，即给出平面区域的一系列散点，求出一定程度上反映这些散点轮廓的平面多边形，给出边的连接方式即可。如从下图的左图散点重建为右图的形状：

编辑	编辑
二维平面散点	平面多边形

　　不过这里有一些细节需要注意，必须明确这一系列点的含义，有时给出的点集是表征图形边界的，如左图的情况；有时则是表征图形所覆盖的范围，即在图形的内部也有一定的点分布。这两种不同的含义是和具体的应用场景相关的。

编辑	编辑
有的场景是求散点描绘的轮廓	有的场景是求散点分布区域的边界轮廓

[TOC]

凹包与Alpha shape

　　有不少计算几何领域的资料探讨过这一类问题的解决方案，笔者也曾经阅读过部分相关的文献，也在网络上进行过一些搜索。本文不能一一去介绍所有的方法，所以就介绍几种简单直观的方法来解决二维点集重建平面多边形的问题。

　　首先很多学计算机的人都知道凸包，凸包求取的是覆盖所有点的凸多边形，由于限定死了一定要凸多边形，所以凸包不是本文所讨论问题的解决方案。本文所求的形状肯定不能否定存在凹陷的部分，因而可以联想到这个问题的解是否是求一种“凹包”，或者说一种广义的参数化的凸包。事实上的确有凹包的概念，英文叫做concave hull（凸包叫convex hull）。不过于凸包的情况不同，凹包没有特别明确的定义，给定一个较不规则的点集，可以有各种各样的凹包，但凸包是确定的，如下图所示。

编辑	编辑	编辑
凸包	一种可能的凹包连接方式	这样连也是凹包

　　进一步查找相关的资料可以发现一个叫做alpha shape的概念。这个概念最早出现于论文“On the shape of a set of points in the plane”中。alpha shape有较为正式的定义，若要简单点解释它，alpha shape其实就是在凸包基础上多了一个可以设定的参数α，因为这个α，在alpha shape重建形状的过程中可能就不会像凸包一样连接相距过远的顶点。参数α若趋于无穷大，则这个alpha shape会无无限接近凸包；而α取小了，则alpha shape会倾向于在一定位置凹陷进去，以更加贴合点集的外形。选择合理的α就能够控制生成的形状让其更加符合点集所描绘的形状。所以给出一个α值，就有点类似于给出一个长度的限制，例如让多边形的任何一边长度不超过R。

编辑
自制ConcaveGenerator小软件截图

第一种思路–基于Delaunay三角化

　　有一定计算几何基础的人一定熟悉Delaunay三角化，通过这一个过程可以形成Delaunay三角网，假如我们为想要求取形状的点集上使用Delaunay三角化算法，可以得到如下的三角网。

编辑	编辑
一个点集的Delaunay三角网	另一个例子

　　一看到这样的三角网，就不难想到一个好点子：因为我们想要求取的形状就是Delaunay三角网的子集，所以我们只需要从Delaunay三角网的最外层边开始外不断的删去超过长度限制的边，当这个过程结束时，我们就能够得到一个大致符合我们预期的形状。

编辑	编辑
点集的Delaunay三角网	删掉边上太长的边就能形成预期的形状

所以总结这个思路，输入为点集S和长度限制R的求取凹包的边列表算法的过程如下：

为点集S求取Delaunay三角网M，三角网用标准Mesh形式表示。
为M初始化所有Edge对象，并求取Edge的长度以及邻接三角形集合。其中邻接2个三角形的边为内部边，1个三角形的为边界边，0个三角形的为计算过程中会退化的边。
将所有长度大于R的边界边加入队列，并当队列非空时循环下列过程：
1. 从队列中取出一条边E，得到E的唯一邻接三角形T。
2. 找到T中另外两个边E1，E2将他们的邻接三角形集合删去T。
3. 将E1,E2中新形成的长度大于R的边界边加入队列。
4. 将E置无效标记，若E1,E2有退化的，也置无效标记。
收集所有有效的边界边，形成边列表，输出。

　　下图是用基于Delauney的方法生成的凹包，看上去大致符合我们的预期：

编辑	编辑
生成结果	显示三角网

滚边法（Edge Pivoting）

　　这是笔者最初想到的一个从求凸包的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的方法使用如下原则：

假如B的R领域除了A就只有一个点，那么那个点就是C。
以B为圆心从向量BA出发转圈扫描，遇到的第一个点为C。

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

向量a与b的点集结果为一个实数，计算方式是axbx+ayby，满足交换率，为正值代表ab夹角小于90度,为锐角，负值代表夹角大于90度（谈夹角的话是指0-180度范围），为钝角。
向量a与b的叉积结果为一个向量，其数值的计算方法是axbx-ayby，不满足交换率，为正值代表向量b处于向量a的逆时针方向（即a逆时针转一个小于180的角能转到b），负值代表向量b处于向量a的顺时针方向（即a顺时针转一个小于180的角能转到b，非要逆时针转则必然超过180度）。

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

滚球法（Ball Pivoting）

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

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

点击并拖拽以移动

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

编辑	编辑
圆在翻滚时候不能扫到其他点	对E的R邻域测试圆覆盖情况寻找合适的F

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

先像求凸包那样求出一个Y值最小(Y值相同则取X最大)的点，作为初始点A，此点一定在凹包上。
从此点出发，(1,0)为基准向量，先找一个小于R的边作为初始边，这时这个点即为B，此时一个半径为R/2的圆就卡在了AB上，此时第一个弦AB就找到了。
循环寻找接下来的弦，假如上一条弦为DE，则下一条弦必然从E开始，连接到E的一个R领域内的点F。寻找F可以使用如下的原则：先对E的R领域的点，以E为中心ED向量为基准进行极坐标方向排序，之后依次为R领域点F0~~FN建立以EFi为弦的圆，然后检查其中是否包含其他F0~~FN的点，若不存在，则EFi即为新弦，则跳出循环。
依次找到所有的弦，直到找不到新弦或遇到以前已经作为弦的点为止。

　　一旦R值给的比较好，这个过程一定能给出一个闭合的图形。下图为几张用ConcaveGenerator生成的图片示例，其中检查参数按钮会自动给一个能让所有点都有至少2个领域的R值。