基于条带扫描思想的线目标缓冲区快速构建

空间目标缓冲区建立的传统算法是基于平行双线扩展思想,在基线复杂分布情形下,该算法对于岛屿和多边形外环的构建及空间关系的处理十分困难。将计算几何的旨在提高运算速度的“条带扫描”思想引入到缓冲区建立过程,对曲线分离出多个两点连接的线段集,生成每条线段的椭圆形基元缓冲区,通过条带扫描法对基元缓冲区叠置生成岛屿内环与多边形外环,判断其间的套合关系。该算法在严密的逻辑组合分析条件下能够对单条或多条基线的复杂情形生成正确的缓冲区多边形,同时运算速度得到改进,达到O(nlogn)。

The Buffer Construction of Line Object Based on the Geometric Scan Idea

The traditional algorithm based on the double parallel generation to build the buffer of spatial objects is difficult to handle the relation between holes and outside loop while the base line distributes in a very complex way.This study introduces the zone scan method from the computation geometry field presenting an algorithm to build the buffer of complex lines.The curve is divided into sets of segment links with two end points and the buffer element is generated for each segment link.Based on the logical operation,the overlay computation of buffer elements results in the holes and outside loop and further builds the inclusion relations between them.This algorithm is able to deal with complex situations of line distribution.Compared with the traditional ones,this method also gets improvement in computation effectiveness,reaching to computation complexity O(nlogn).