维普资讯 http://www.cqvip.com
第３３卷 第６期 Ｖｏ１．３３ ・计算机工程 ２００７年３月 Ｍａｒｃｈ ２００７ Ｎｏ．６ Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ 软件技术与数据库・ 文章编号；ｌ００ ．３４２８（２００７）０６＿＿００５ｌ— ２ 文献标识码：Ａ 中圈分类号：ＴＰ３０１．６ 嵌入式ＧＩＳ面要素无缝拼接的数据结构及其算法 胡泽明，岳春生，王志刚 （信息工程大学信息工程学院，郑州４５０００２） 摘要：嵌入式ＧＩＳ地图数据是分幅、分块记录和存储的，物理完整的面状地理实体在切割边界会产生缝隙。该文在面要素坐标数据支持 的基础上，在内存构建图块切割边关联索引表中，描述了在嵌入式硬件平台上快速实现面状地理要素的无缝拼接的过程，实现了面状地理 实体的逻辑无缝。 关健词：嵌入式地理信息系统；无缝ＧＩＳ；块边界面要素；切割边关联索引表 Ｄａｔａ Ｓｔｒｕｃｔｕｒｅ ｏｆ Ｅｍｂｅｄｄｅｄ ＧＩＳ Ａｒｅａ Ｆｅａｔｕｒｅ’Ｓ Ｓｅａｍｌｅｓｓ Ｕｎｉｔｅ ａｎｄ Ｉｔｓ Ａｌｇｏｒｉｔｈｍ ＨＵ Ｚｅｍｉｎｇ，ＹＵＥ Ｃｈｕｎｓｈｅｎｇ，ＷＡＮＧ Ｚｈｉｇａｎｇ （Ｃｏｌｌｅｇｅ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ，Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｚｈｅｎｇｚｈｏｕ ４５０００２） ［Ａｂｓｔｒａｃｔ］Ｔｈｅ ｄａｔａ ｍａｐ ｉｓ ｓｔｏｒｅｄ ａｃｃｏｒｄｉｎｇ ｔＯ ｓｈｅｅｔ ｏｒ ｂｌｏｃｋ ｉｎ ｅｍｂｅｄｄｅｄ ＧＩＳ ｓｙｓｔｅｍ，ｔｈｕｓ ｃａｕｓｉｎｇ ｓｅａｍ ｉｎ ｔｈｅ ｃｕｔｔｉｎｇ—ｂｏｒｄｅｒ ｆｏｒ ｐｈｙｓｉｃａｌ ｉｎｔｅｇｒａｔｅ ａｒｅａ ｆｅａｔｕｒｅ．Ｂａｓｅｄ ｏｎ ａｒｅａ ｆｅａｔｕｒｅ ｃｏｏｒｄｉｎａｔｅ ｄａｔａ，ａｎｄ ｃｏｎｓｔｒｕｃｔｉｎｇ ｂｌｏｃｋ ｃｕｔ—ｅｄｇｅ ａｓｓｏｃｉａｔｅ ｔａｂｌｅ，ｔｈｉｓ ａｒｔｉｃｌｅ ｄｅｓｃｒｉｂｅｓ ｓｅａｍｌｅｓｓ ｕｎｉｔｅ ｐｒｏｃｅｓｓ ｏｆ ｃｕｔｔｉｎｇ—ｒｅａ ｆａｅａｔｕｒｅ ｏｎ ｅｍｂｅｄｄｅｄ ｓｔｕｄｉｏ，ｄｒａｗｉｎｇ ｗｈｏｌｅ ｇｅｏｇｒａｐｈｉｃａｌ ｅｎｔｉｔｙ ｓｍｏｏｔｈｌｙ． ［Ｋｅｙ ｗｏｒｄｓ！Ｅｍｂｅｄｄｅｄ ＧＩＳ；Ｓｅａｍｌｅｓｓ ＧＩＳ；Ｂｌｏｃｋ・－ｂｏｒｄｅｒ ｒｅａ ａｆｅａｔｕｒｅ；Ｃｕｔ・－ｅｄｇｅ ａｓｓｏｃｉａｔｅ ｔａｂｌｅ 嵌入式ＧＩＳ是ＧＩＳ的一个重要分支，目前已经广泛用于 ＧＩＳ系统要求数据量小，满足存储器容量需求和减少数据文 件读取时间。坐标数据是面状地理要素空间数据的重要组成 部分，数据量大。嵌入式ＧＩＳ数据生成时，采用垂距限值法 车载导航仪、移动信息终端和数字化武器装备等嵌入式系统 中，实现了大范围地图浏览、路径分析和信息检索等功能。 为提高嵌入式ＧＩＳ系统的实时性，数字地图一般是分幅分块 （图幅图块统称为图块）记录存储的，并采用四叉树存储结构。 现实世界中湖泊、河流和绿地等面状地理实体在物理上是连 续的，分幅分块时它们被切割为多个部分分别记录存储在不 同文件中，产生数据缝隙，地图数据在数据表示和数据处理 或者道格拉斯一普克（Ｄｏｕｇｌａｓ—Ｐｅｕｃｋｅｒ）等坐标压缩算法删除面 状要素边界描述中可以忽略的坐标点，减少坐标点数目。坐 标文件具体存储时，还可以基于图块顶角坐标将３２ｂｉｔｓ绝对 坐标转换为１６ｂｉｔｓ相对坐标以进一步压缩坐标数据量。 基于功能实现和最大限度压缩坐标数据量，本文对图块 内１６ｂｉｔｓ相对坐标作进一步处理，使之不仅可以直接描述坐 时也会产生缝隙…。但是电子地图浏览时，被分割描述的面 状地理实体应该进行逻辑拼接，实现整体绘制和区域填充， 消除边界相接处的缝隙。 标分量、坐标点与边界的关系，还可以描述边界点类型（见 图１）。 常规地图无缝拼接方法是统一坐标系，全国乃至全球都 在这个统一坐标系下进行坐标换算，采用线性映射投影方式； 统一坐标系法实现简单，但系统误差大的只能用于较小地理 区域。文献【２】对无缝ＧＩＳ理论和相关技术进行了深入研究， 提出用属性拼接表来表达属性数据和连接图块之间的相关要 —二： ｂｉｔ［１５，１４］边界点类型 ｂｉｔ［１３￣０］］ Ｉｒｘ分量坐标 —二： ｂｉｔ［１５，１４］预留 ｂｉｔ［１３￣０］］ ＩｒＹ分量坐标 素，保证无缝ＧＩＳ数据在物理存储上是分块的，但逻辑使用 上是连续无缝的；可是属性拼接表不是针对嵌入式平台设计 的，不能很好地用于嵌入式ＧＩＳ系统。基于分幅分块的原理， 图１点坐标分量描述 本文首先给出面要素坐标描述方法，指示面状实体与切割边 界的关系，并引入切割边的概念；然后基于切割边关联索引 表，给出实现面要素逻辑拼接过程的快速算法，在嵌入式平 本文定义在图块边界上的点称为边界点（见图２），边界点 如果物理上存在，称为实边界点（逻辑拼接时合并为一个点）， 否则是切割形成的，称为切割点（逻辑拼接时需要删除）。面 台上高效地完成面要素的无缝拼接。 状实体被切割矩形切割时，切割边界有一部分是封闭面要素 的组成部分，它被称为切割边（见图２）。实体坐标分量及其含 义见表１。 作者倚介：胡泽明（１９７７一），男，博士生，主研方向：嵌入式ＧＩＳ， 组合导航和数据融合技术；岳春生，教授；王志刚，教授、博导 ｌ面要素坐标格式和切割边关联索引表 １．１面要素坐标格式 面状地理要素是矢量地图基本几何实体要素之一，文 献【２】指出无缝ＧＩＳ适合采用实体型数据模型，在实体型数据 模型中，面要素采用首尾相接的有序坐标对来记录。嵌入式 收稿日期：２００６—０３—２８ Ｅ－ｍａｉＩ：ｚｚ＿ｈｕｚｅ＠１６３．ｃｏｍ ５ｌ一 维普资讯 http://www.cqvip.com
切割点 、＼／块内点 、 ——√ ／ 实边界点 ・块内点 。切割点 实边界点 图２边界点和切羽边示意图 表１实体坐标分量及其含义 坐标分量 含义 取值 ＯＯ 块内点； Ｘ－ｂｉｔ【１５，１４】 点与边界的关系，边界点类型 ０１－－）实边界点； ｌ０ 切割点 ｙ－ｂｉｔ［１５，１４】 预留 默认ＯＯ Ｘ－ｂｉｔ［１３，０】 ｘ坐标分量 【０，１６ ３８３】 ｙ－ｂｉｔ【１３，０】 Ｙ坐标分量 【０，１６ ３８３】 在点坐标格式基础上，面状地理要素坐标数据可以分为 坐标记录和切割边记录两部分，如表２所示。 表２面状地理要素坐标数据 数据项 类型格式 备注 坐标 坐标个数Ｍ 坐标个数包括面要素中 记录 坐标系列｛ｎｘ，ｎｙｌ” 心坐标 切割边 切割边个数ｍ 切割边起止节点一定在 记录 ｛切割边起点序号；切割边 切割边界上，块内面要素 终止序号｝ 没有切割边信息 矢量地图在分幅分块时，面状地理要素按其坐标是否与 矩形边界相交分为块内面要素和块边界面要素２大类。前者 面要素边界坐标都在图块内，后者面要素与切割边界相交被 分割为多个部分。地图浏览时块内面要素可以直接绘制边界 和进行区域填充，而块边界面要素与邻接图块实现逻辑拼接 后才能进行。为快速实现无缝拼接，图块数据读入内存中预 处理时需要对图块内的块边界面要素建立切割边关联索引表 数据结构。 １．２切翻边关联索引表 在１．１节中，１６ｂｉｔｓ相对坐标格式在最大程度上压缩和 减少无用坐标数据的存储，并通过切割边间接提供了面状实 体与图块边界的关系，但是要直接利用坐标文件来实现面要 素无缝拼接是很困难的，必需建立图块的切割边关联索引表， 明确指出切割边在图块边界上的位置、切割边对应的面状实 体据和切割边与邻接图块边界边的关联等信息。 矩形切割图块边界存在４个方向边，分别是东南西北， 见图３。 图３边界边、邻接块方向示意图 每个方向边都可能存在切割边，都需要建立切割边关联 索引表。图块切割边关联索引表数据结构字段内容包括图块 编号、有序４个方向边切割边个数、切割边结构（边界点坐标 及其数据指针）等内容，如表３所示。 一５２一 表３图块切削边关联索引表数据结构 结构字段 数据类型 备注 图块编号 ｌ Ｎ １ Ｎ指代１个１６ｂｉｔｓ 整型字段 北边 Ｎ ｌ Ｎ ４个方向 边上的切 东边－）Ｅ －ｌ Ｎ 边界边、邻接块方向 割边个数 南边－－）Ｓ ｌ Ｎ 示意图（图３） 西边 ｗ ｌ Ｎ 起点坐标 ｌ Ｎ 起点坐标和终点坐 序号 标可以确定一条切 割边，也可以直接利 切割边 终点坐标 ｌ Ｎ 用面要素边界坐标 结构 序号 记录，所以此处采用 坐标序号 指针偏移 ｌ Ｎ 指针指向切割面要 素坐标记录结构 ４个方向边上每１个增序排列的边界点都有一个切割边 结构记录，方向Ｎ／Ｅ／Ｓ／Ｗ与一个相邻图块相接，见图３；图 块切割边关联表数据存储结构见图４。 图块编号ｌ ４方向边切割边个数ｌ ４方向边切割边数据结构 块边界 面要素 切割边数Ｉ…Ｉ切割边数ｌＮ方向边Ｉ…１ｗ方向边Ｉ ｌ切割边１ ｌ指针ｌ 切割边ｋ 指针ｋ 数据存 储区域 图４图块切削边关联表数据结构 ２面要素无缝拼接算法 矢量地图在分幅分块时被切割的面状地理要素在每个图 块内被地记录和描述，无缝拼接算法的核心是快速找到 相邻图块内两个对应的面状地理要素。在内存中构建了图块 切割边关联索引表，不仅指明边界点与面状地理要素的连接 关系，边界点在边界边上的位置，而且还给出与邻接图块边 界边的对应关系，方便了面状地理要素的无缝拼接快速实现 算法。 在构建图块切割边关联索引表时，４个方向边上都有， 而且每个方向边上切割边都基于起点坐标分量增序存储法， 相邻图块切割边关联表也是这样。在相邻图块的相接边上， 切割边位置序号就直接指明它们是对应边（也可以采用坐标 分量匹配法），通过指针关系把切割的面状地理要素坐标连接 起来，就可实现无缝拼接过程。图５以一个方向边为例来具 体阐述，其它方向边实现过程一样。设图块Ｂ１东边（Ｅ）方向 上有ｉ个切割边，其记录顺序为｛ｅ１，…，ｅｉ）；图块Ｂ２在东方 上与Ｂ１图块相接，其西边方向上也有ｉ个切割边，其记录顺 序为｛ｗ１…．，ｗｉ）；因为２个方向切割边基于起点坐标增序排 列，显然切割边ｅｊ与ｗｊ相对应，即配对切割边集合为（ｅｊ，ｗｊ） 关联着同一个面状地理要素；将它们指向的图块内面状要素 坐标连接起来形成无缝接边。 在基于切割边关联索引表实现块边界面要素拼接时，还 要基于切割边上边界点类型处理边界节点，如果是实边界点， 则坐标连接过程中保留一个边界点坐标；如果是切割点，则 坐标连接过程中删除２个切割点坐标。构建图块切割边关联 索引表后块边界面要素拼接算法伪码描述如下： ｆｏｒ（图块每一条边界边） ｛基于边界边找到邻接图块及其切割边关联索引表； ｆｏｒ（当前边界边的每个切割边） ｛在邻接图块对应边上找到对应切割边； （下转第５５页） 维普资讯 http://www.cqvip.com
（Ｄｋ＋ｌ＝ ； Ｆｏｒ ａｌｌ ｔｒａｎｓａｃｔｉｏｎ ｔ ｉｎ Ｄｋ ｄｏ ｂｅｇｉｎ Ｃｏｕｎｔｓｕｐｐｏｒｔ； ２５０ 一ＤＨＰ算法 鞘ＯＤＨＰ算法 Ｉｆ（ｔ．ｃｏｕｎｔ＞ｋ）ｔｈｅｎ Ｐｒｕｎｅｓｅｃｏｎｄ（ｋ＋１）； 善２００ 盏１５０ ｓａｖｅｔｏＤ ｌ； 篓１ ０。０ ０ ｌＵ １５ ２０ ２） Ｅｎｄ Ｌｋ＝ｆＣ ｉｎ ＣｋｌＣ．ｃｏｕｎｔ≥Ｓ｝； ｉｆ（ＩＤｋｌ＝Ｏ）ｔｈｅｎ ｆｉｎｉｓｈ； Ｃ ＝ａｐｆｉｏｆｉ最大项目集大小 图４算法测试比较 ｇｅｎ（Ｌ ） 判断所有的ｋ一１项目子集是否频繁项目集 ｋ＋＋： ４结束语 针对传统ＤＨＰ算法在入侵检测系统中实际应用的缺陷， 本文提出了一种改进算法ＯＤＨＰ。实验结果显示，ＯＤＨＰ算 ｌ Ｍａｉｎ ｅｎｄ 对剪枝后代数据进行２次剪枝主要是针对特定事务项的 法效率比传统的ＤＨＰ算法高，后续研究也将集中把这一算法 项目。在算法中的Ｐｒｕｎｅ—ｓｅｃｏｎｄ函数对应于ｍａｋｅ—ｈａｓｈｔ函 的思想更深入地应用于实际系统的优化中。 数 】，将数据集中所有事务项中潜在的ｋ＋ｌ项目集重新散列 到哈希结构这一过程。 参考文献 ３算法实现及实验结果 １胡和平，肖述超．一种分布式入侵检测系统模型ｆＪ］．计算机工程 本文测试环境：主频为１．６ＧＨｚ，内存为２５６ＭＢ，操作 与科学，２００５，２７（７）． 系统为Ｗｉｎｄｏｗｓ ２０００，编译器为Ｖｉｓｕａｌ Ｃ＋＋６．０，数据库系 ２ Ｍａｎｎｉｌａ Ｈ，Ｔｏｉｖｏｎｅｎ Ｈ．Ｄｉｓｃｏｖｅｒｉｎｇ Ｇｅｎｅｒａｌｉｚｅｄ Ｅｐｉｓｏｄｅｓ Ｕｓｉｎｇ 统为ＳＱＬ Ｓｅｒｖｅｒ。入侵检测系统采用基于Ｓｎｏｒｔ的Ｃ／Ｓ结构 Ｍｉｎｉｍａｌ Ｏｃｃｕｒｒｅｎｃｅｓ［Ｃ］／／Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２ Ｉｎｔｅｒｎａｔｉｏｎａｌ 的ＩＤＳ的情况下针对传统的ＤＨＰ算法和ＯＤＨＰ算法的挖掘 Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ ｉｎ Ｄａｔａｂａｓｅｓ ａｎｄ Ｄａｔａ Ｍｉｎｉｎｇ． 速度和效率进行了比较。 １９９６． 数据库访问方式采用ＡＤＯ方式。而数据结构方面，在 ３杨华兵，叶新郢，张宁蓉．入侵检测中频繁模式的有效挖掘算法ｆＪ】 候选项目集集合采用了前缀树结构（ｐｒｅｆｉｘ—ｔｒｅｅ），而频繁项目 情报指挥控制系统与仿真技术，２００５，２７（１）． 集则采用了数组结构，频繁项目集之间也使用数组结构 ４ Ａｇｒａｗａｌ Ｒ，Ｓｒｉｋａｎｔ Ｒ．Ｆａｓｔ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｍｉｎｉｎｇ Ａｓｓｏｃｉａｔｉｏｎ 组织。 Ｒｕｌｅｓ［Ｃ］．Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２０ ＶＬＤＢ Ｃｏｎｆｅｒｅｎｃｅ．１９９４． 在测试中，对最大频繁项目集的大小分别选取了１０、１５、 ５张真诚．中国古典数学在咨讯科学上的应用【Ｊ］．咨讯与教育杂志． ２０、２５等多个不同的测试点。最小支持度设定在０．４％。 １９９ｌ，（８）． ６ Ｃｈｅｎ Ｍｉｎｇｙａｎ，Ｙｕ Ｐ Ｓ．Ｕｓｉｎｇ ａ Ｈａｓｈ－ｂａｓｅｄ Ｍｅｔｈｏｄ ｗｉｔｈ Ｔｒａｎｓａｃｔｉｏｎ 从图４中可以看出，在实验中ＯＤＨＰ算法比传统的ＤＨＰ 算法更为有效。实验证明，ＯＤＨＰ算法对各类型的频繁项目 Ｔｒｉｍｍｉｎｇ ｆｏｒ Ｍｉｎｉｎｇ Ａｓｓｏｃｉａｔｉｏｎ Ｒｕｌｅｓ［Ｊ］．ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｄａｔａ Ｅｎｇｉｎｅｅｒｉｎｇ，１９９７，９（５）：８１３－８２５． 集挖掘都十分有效。 （上接第５２页） ３结论 ／／实现切割面要素坐标拼接； ｉｆ（切割边边界点是实边界点） 嵌入式ＧＩＳ系统上地理数据是分幅分块记录存储的，某 一则２个边界点指向的面状要素坐标合并时保留１个边界点； 时刻以图块为单位仅读取屏幕可视范围的地理数据到内存 ｅｌｓｅ／／切割点 实现无缝拼接，执行显示和缩放处理；漫游时重新读取漫游 则２个边界点指向的面状要素坐标合并时删除２个切割点； 区域的地理数据，此时较长时间没有使用的图块数据可从内 ｌ ｌ； 存清除。这样嵌入式系统上基本实现数据按需读取和处理过 上述拼接过程是理想情况下的实现，在切割边关联索引 程，系统执行速度快。根据实现分析和实践证明，本文提供 表支持下拼接过程简单。 的嵌入式ＧＩＳ面要素坐标格式数据量小、算法实现简单，能 为减少拼接错误，可在切割边结构中增加地理要素编码 够在一定位置误差范围内自动化实现面要素无缝拼接处理， 字段，确保实现同类地理要素的拼接。图块块边界面要素拼 能够用于任意数量的图块拼接。数据量小和算法简单高效的 接前后示意见图５，图块拼接后实现切割面状地理要素在接 特点使之可以用于Ｃ／Ｓ体系结构的网络ＧＩＳ系统中。 边处是无缝的，屏幕视觉效果良好。 参考文献 １隋春光，彭认灿．数字海图无缝拼接的实现及相关问题研究［ＪＪ ．测绘科学，２００４，２９（４）：２８—３ １． ２王卉．无缝ＧＩＳ相关理论与技术的研究［Ｄ］．郑州：信息 工程大学，２００４． ３朱欣焰，李德仁．无缝空问数据库的概念、实现与问题研究ｆＪ】．武 汉大学学报，２００２，２７（４）：３８２－３８６． ４王卉，王家辉．无缝ＧＩＳ发展的两个关键技术ｆＪ］．测绘通报， 图５图块拼接前后示意图 ２００２，ｆ４）．
