预览加载中，请您耐心等待几秒...

基于四叉树结构的坐标咬合算法.pdf

预览
1/3
2/3
3/3

在线预览结束，喜欢就下载吧，查找使用更方便

下载提示 文本预览

如果您无法下载资料，请参考说明：

1、部分资料下载需要金币，请确保您的账户上有足够的金币

2、已购买过的文档，再次下载不重复扣费

3、资料包下载后请先用软件解压，在使用对应软件打开

50测绘通报2002年第4期 文章编号:04940911(2002)04005002中图分类号:P208文献标识码:B 基于四叉树结构的坐标咬合算法 刘庆华,林爱文 (武汉大学资源与环境科学学院,湖北武汉430079) AnAlgorithmofCoordinatesSnapBasedonQuadtreeStructure LIUQinghua,LINAiwen 摘要:介绍基于四叉树结构的坐标咬合算法。该算法通过减少判断咬合过程中的次数,显著提高坐标咬合的速度。实验表明该算 法完全可应用于海量数据的GIS软件系统当中。 关键词:坐标咬合;四叉树;数据结构 一、概述 在弧段数字化过程当中,图上的一个点会相应 地在计算机内得到一个坐标对,称之为图纸上点的 映射坐标。在数字化过程中由于对同一点可能进行 多次数字化,而每一次采点却可能对应着不同的坐 标值。如某个点既为房角点又是围墙点,还可能是图2狭长多边形 界址点。如在每次数字化时,由于没有使用或未正 二、坐标咬合的四叉树结构 确使用捕捉方式使得同一点每次对应的映射坐标之 间可能存在一定大小的隙差,这就产生了弧段端点由于在坐标咬合过程中所涉及到的数据为当前 不重合的现象。如图1所示,其中(a)所示为实际情图层的所有弧段数据的点坐标,并且此过程的基本 况,(b)所示为数字化结果。在数字化时,还有可能运算都比较复杂,如点到线的距离,点到线段的垂足 对同一边界的两次或多次数字化没有完全重合,而等。因此在具有海量数据的GIS系统中,不可能使 在构建拓扑之后形成一些狭长多边形(图2),而这用传统的线性方法解决这个问题,为此需要寻找新 些狭长多边形并不是实际存在的地物。所有这些现的方法。为了减少咬合过程中的盲目性,笔者使用 象的产生对随后的空间分析产生了不利的影响。在了基于四叉树结构的咬合算法。 进行空间分析之前需要对数据的合法性进行检查,在该算法中,将每条弧段都用一棵四叉树表示, 而这些错误大多是在对海量数据建立拓扑中发现并并且规定每个树结点有4个子结点或没有子结点, 校正。因此在建立拓扑关系时应考虑设置一个限差我们可以通过规定树的叶子结点中包含的最大点的 e,当某弧段上的一点到另一条弧段的距离小于这个个数来结束树的构造过程。树结点的定义如下: 限差时,应将这个点移到另一条弧段上,也就是进行typedefstructtagQuadTreeNode{ 弧段之间的咬合,我们称其为坐标咬合,称e为坐标RECTrcNode;//当前结点内所有点的最小 咬合限差。在目前的大多数文献当中,针对这个问包围盒外扩 题所提出的具体算法较少。LongStartVertex;//起始点在弧段中的索引 LongEndVertex;//终止点在弧段中的索引 QuadTreeNode*pParent;//父结点的指针 QuadTreeNode*pFirstChild;//以下为子结 点的指针 QuadTreeNode*pSecondChild; QuadTreeNode*pThirdChild; 图1数字化结果的正确性QuadTreeNode*pForthChild; 收稿日期:20011015;修回日期:20020206 作者简介:刘庆华(1978),男,江西九江人,硕士,主要从事空间分析及地理信息系统应用开发工作。 2002年第4期测绘通报51 }QuadTreeNode,*PQuadTreeNode; 三、坐标咬合及四叉树维护 以一条具有41个中间点的弧段为例,来说明四 叉树的动态构造过程。如图3所示(没有考虑限差对于两条弧段1和弧段2有两棵对应的四叉树 e)。图中是规定叶子结点中最大点的个数为15时1和四叉树2。首先,通过根结点的比较判断是否可 所对应的四叉树。首先,构造根结点。由于15小于能有咬合。若可能有咬合则将某一棵树的根结点的 41,所以该根结点应有四个子结点。子结点中点的第一棵子树与另一棵树的根结点比较。若子结点与 个数为(41+3)/4,即11个,而15又大于11,所以根结点可能有咬合,则此子结点要与根结点的第一 至此可以结束四叉树的构建。最终的四叉树共有5棵子树比较。依此递归下去最终在两个叶子结点之 个结点,其中1个根结点,4个叶子结点。在设置叶间进行坐标的咬合。在此过程中四叉树的维护显得 子结点所包含的最大点的个数n时应注意,n的值非常重要,因为在咬合过程中可能要移动弧段的中 应大于或等于4,否则当弧段的中间点数小于4时,间点以及可能要在某一条弧段上增加一个点,图5 会