缓冲曲线和边约束三角网辅助的缓冲区生成算法

Buffer Curve and Buffer Generation Algorithm in Aid of Edge Constrained Triangle Network

本文在分析了已有的缓冲区生成算法后，提出缓冲曲线和边约束三角网辅助的矢量缓冲区生成算法。算法分两步，第一步生成作者提出的缓冲曲线，第二步将缓冲曲线切割组合为缓冲区。算法通过缓冲曲线，在理论上减少了参与切割重组的线段数目，将不可能成为缓冲区边界的线段在一开始就剔除；在第二步中，算法通过边约束三角网和环绕系数的传递将线段切割重组的过程优化，不相交的线段之间免去比较判断，从而为生成缓冲区提供一个快速完整的方案。

With existing buffer generating algorithms assessed, this paper proposes a new algorithm in aid of edge constrained triangular network to create vector buffer. The algorithm consists of two steps. The first step is to construct buffer curve, a new concept proposed to be a mid stage to unify the algorithm for arbitrary buffer of all possible types of geometric objects and their combination. The second step is to extract the ultimate buffer from buffer curve. Edge constrained triangular network is applied to accelerate the detection of intersections and self intersects of buffer curve. Winding number is employed to distinguish those segments in buffer curve that comprise the ultimate buffer.