折线的缓冲区算法，可避免失真问题

一、简介

缓冲区分析是地理信息系统中使用非常频繁的一种空间分析，是对空间特征进行度量的一种重要方法，在交通、林业、资源管理、城市规划、环境与生态保护等领域都有着广泛的应用。GIS中缓冲区生成包括点、线、面三种目标类型的缓冲区的生成，其中线状目标缓冲区的生成是关键。

现有的缓冲区生成算法主要有栅格和矢量两种方法。栅格方法原理简单，容易实现，但是效率和内存开销取决于栅格的密度。矢量算法原理复杂，不易实现，但是效率和精度较高，内存占用少。矢量算法主要有基于双线圆弧法的跟踪算法和基于单个缓冲区单元的叠加算法。双线圆弧算法存在失真问题，大部分文献对此没有处理或者对失真情况处理十分复杂，难以完备实现；基于单个缓冲区的叠加算法因为存在大量冗余数据，造成大量不必要的求交运算，效率大受影响。

二、失真问题处理

传统的双线圆弧算法的基本思想是：在轴线的两端用半径为缓冲距的圆弧弥合；在轴线的各个转折点，首先判断该点的凸凹性，在凸侧用半径为缓冲距的圆弧弥合，在凹侧用与该点关联的前后两相邻线段的偏移量为缓冲距的的两平行线的交点作为对应顶点。该算法最大的不足在于会存在尖角或凹陷等失真现象。虽然龚洁晖等将缓冲区边界失真现象归纳为三类16种，并一一给出了修正处理方法。但实际上缺少凹侧两侧均为凹侧这一类情况的处理，且修正处理较为复杂，难以完备实现。

折线的缓冲区可以看成是各个组成线段的缓冲区合并的结果，因此在凹侧的缓冲区边界的处理上应视为两条线段而非平行线。与平行线不同，线段可能没有交点，此时如果仍用平行线的交点作为对应顶点，便会造成失真问题，如图1所示。基于此，在凹侧的处理上，如果两条线段有交点，仍采用传统的处理方式；如果没有交点，则记录凹侧的两条线段，不做处理。这样便可避免失真问题，由此产生的多余线段可和自相交问题在生成最终缓冲区边界时统一处理。

图 1 失真问题及处理策略

三、算法流程

与传统的双线圆弧算法不同，这里以线段/弧段作为基本处理单元，并通过在凹侧记录两条线段来避免失真问题。整个算法流程如图2所示：

图 2缓冲区算法处理流程图

其中左侧为算法流程，右侧为处理和优化方法。请注意，源程序中将去掉平面扫面算法和非边界点剔除算法；将采用最简单的遍历计算，暂不考虑效率问题。

四、线状缓冲区生成算法

4.1 构造初始缓冲区边界

和传统的双线圆弧算法相同，在凸侧加入圆弧，在凹侧加入线段，同时记录线段/弧段的前进方向，按顺/逆时针顺序最终生成一个线段/弧段混合数组。其中有所不同的是当凹侧的两条线段不相交时，通过直接记录两条线段处理失真问题，生成的初始缓冲区边界如图 3所示。

图 3 缓冲区初始边界

　　但是对于失真问题的简单处理会带来大量的冗余数据，不少线段在缓冲区的内部，参与求交没有任何意义。适当地剔除缓冲区内部的线段以减少参与求交的线段对于整个算法效率的提高大有裨益。可根据凹点两侧类型的分布，细分为两侧均为凹点、两侧均为凸点、前凸后凹和前凹后凸四种情况予以处理。在构造缓冲区初始边界的过程中，当凹点的两条线段不相交时，较短的线段一定位于缓冲区的内部，可以直接删除，对于较长的线段，需要根据凹点两侧类型的分布适当处理。在构造过程初始边界过程中更新/删除部分不必要的缓冲区单元后边界后如图 4所示。

图 4 去除部分冗余数据的初始缓冲区边界

请注意，源程序中将去掉初始缓冲区边界的剔除算法，暂不考虑效率问题。

4.2 计算交点

交点的计算是整个缓冲区算法中最为耗时的操作。最为简单的暴力求交，时间复杂度为O(n²)，当折线很长时，这种方法十分耗时。为了提高求交效率，需要充分利用线段/弧段的几何性质：

只有那些相互靠近的线段/弧段才可能会相交；而相距甚远的线段/弧段则不可能相交
线段/弧段之间具有连接性质。

请注意，源程序中将去掉平面扫描求交算法，转而采用暴力求交算法，暂不考虑效率问题。后期会针对平面扫面算法单独写篇博客。

4.3 剔除非边界点

经过求交运算计算出来的交点有些可能位于整个缓冲区的内部，需要予以剔除。当折线的点很多(n个)，交点也很多时(m个)，通过计算每个交点到折线的各个线段的最短距离的方法进行判断，时间复杂度为O(mn)，效率十分低下，因此需要一种高效的剔除算法。

实际上，折线上的很多线段离交点很远，根本无需参与剔除计算，因此快速找到那些需要判断的线段是提高剔除算法的关键。

请注意，源程序中将去掉非边界点剔除算法，转而采用暴力判断算法，暂不考虑效率问题。后期会就点到折线的距离问题写篇博客。

4.3 跟踪生成缓冲区边界

经过计算交点并剔除在缓冲区内部的交点后。剩下的交点均位于缓冲区的边界上，为最终缓冲区上的点。此时构造缓冲区的策略借鉴采用两多边形求并的双线算法。其具体思想是：

从交点集合中选择一点，沿着前进方向跟踪，遇到交点则跳转到交点所在的另外一个单元上，如此重复，直到回到该交点。如果还有剩余交点，则重复上述过程，直到所有的交点都参与构造缓冲区边界，上述过程也一并处理了自相交问题。此处的一个难点是，就是确定跟踪时选择的第一个交点是出点还是入点，可以根据叉积进行判断。最终生成的缓冲区边界如图5，图6所示：