3.1.3　组合对象的顶点层次结构

在地理空间数据集中,由多条线对象首尾依次连接所构成的组合对象具有更加复杂的拓扑结构,是地理要素数据集中的重要内容。组合对象在现实世界中表现为复杂的地理实体,例如大型水体、行政区等封闭的面状实体,道路网等跨度较广的线状要素。本节将讨论多个线对象连接时如何将独立的多个线对象所对应的顶点层次结构经过连接形成对应于组合对象的层次结构。给定若干个线对象L 0,L 1,…,L n,组合对象由线对象连接而成R＝L 0+L 1+…+L n,顶点层次结构的连接讨论如何根据线对象的二叉树T 0,T 1,…,T n得到组合对象的二叉树

将多个线对象生成的平衡二叉树进行连接的基本思想如下:①对组合对象R中所有的中间顶点计算到基准线的距离,获得距离最大的值;②选择单个线对象组成的首尾顶点集合中距离最远的点作为分割点;③将步骤②中获得的分割点建立树节点,并赋予步骤①中取得的距离值为误差值;④递归执行上述步骤直到所有的线对象的首尾点均被选择。可以看出,组合对象基于DP算法的思想构建了二叉树,在选点上只考虑了单个线对象的首尾点。因此,组合对象形成的二叉树由单个线对象的端点组成,每个端点可以指向该端点所对应的单个线对象。表3-2为面向组合线对象的二叉树构建算法。(https://www.daowen.com)

表3-2　面向组合线对象的二叉树构建算法