从零开始学习导航网格#11 Layer partitioning

项目中有两个地方都用到了分层分割算法

bool rcBuildLayerRegions(rcContext* ctx, rcCompactHeightfield& chf,
                         const int borderSize, const int minRegionArea)

bool rcBuildHeightfieldLayers(rcContext* ctx, rcCompactHeightfield& chf,
                              const int borderSize, const int walkableHeight,
                              rcHeightfieldLayerSet& lset)

代码基本上大同小异，这里我们只对rcBuildLayerRegions进行说明

算法的思想其实比较朴素：
1.逐行扫描，将相邻的span合并成严格的“矩形区域”（这个下面会解释）
2.将第一步得到的矩形区域按是否相邻进一步合并，但需要保证合并的两个区域之间没有重叠的区域
这里“重叠”的含义是：两个区域存在各存在一个span，他们在zx的投影相同

下面着重解释一下第一步的处理过程
以每个cell最多只有一层span为例，看下面这个例子（注意是对xz平面的俯视图）

初始状态

注意逐行合并这里，如果1和2之间，还有一个span，那么123会在这一步就合并成一个大矩形，但是由于例子中存在一个空缺，所以无法合并

逐行合并
逐行扫描完毕后，再合并矩形区域
合并矩形区域
这里是单层的情况。如果是多层，需要判断两个区域之间是否重叠，如果重叠，则不能合并（如下图中蓝色和红色的区域在标记的位置重叠，不能继续合并）
区域合并