首先介绍一些问题的背景。当需要聚合一堆坐标点时，我们可以选择用网格法。即将包含所有坐标点的最小矩形分为m*n的网格，即将矩形分为m列n行，找出格子内点数满足阈值范围的所有格子。然后将找出来的格子计算八连通图。步骤示意图如下：
1.给一堆坐标点
2.找出能包含所有点的一个最小矩形
3.将矩形按列m=4，行n=2 分为一个4*2的网格
4.将格子内点数大于2的格子过滤出来（红色格子），算八连通图，图中两个格子是八连通图
了解了相关背景，接下来说下我们要解决什么。我已经知道下图中的所有红色格子是一个八连通图，现在想绘制出该连通图的轮廓(不同于凸包)，如蓝线所示：
具体的实现思路是：
1.首先建立坐标轴，按第四象限为正，每个格子间隔设为1，黄色点的坐标作为每个格子的标识符。
2.根据每个格子的索引坐标及格子间隔1，将每个格子的四个坐标点都找出来，然后按照从左到右，从上到下的顺序将每个格子的边表示出来（为了方便，将格子编号）。如格子1，按顺时针方向四个坐标分别是（0，0），（1，0），（1，1），（0，1），对应的边：（0，0，1，0），（1，0，1，1），（0，1，1，1），（0，0，0，1）。总的边数是24。
3.将所有格子的所有边都统计出来后，将重复的边全部去掉（只要重复出现，就都不要了），就能将被重复使用过的边去掉。如图黄色虚线是重复的边，则将这些边删掉，去重后剩下20条边。
4.接下来随机选一个坐标点作为初始点，这里我选择（0，0），然后按照顺时针（逆时针也可以）的方向扫描，优先级设为上 > 右 > 下 > 左，将所有去重后的边（20条）存到一个数组中，从初始点开始按顺序移动点，每访问一条边就将该边删除，并将每一步所移动到的点的坐标存到另一个数组中，当存边的数组为空时扫描结束，即得到网格连通图的轮廓。操作中边的变化示意图如下：
这里需要注意一点，进行到第（7）步时，扫描点位于（1，1），但是此时（1，1）相邻的三条边都已经访问过了。而这时还有四条边没有访问，循环没有结束。这时，可以从剩下的边中任意选择一个点，继续按顺时针扫描。如果又遇到这样的情况，同理继续从剩下的边中任意选点扫描。直到存边的数组为空，则扫描结束，得到了最终网格连通图的轮廓，如图（8）所示。
网友评论