基于SVG的多边形叠置分析算法初探

基于SVG的多边形叠置分析算法初探 测绘科学Vo l134 No12 第 34卷第 2期 Sc ience of Su rveying and M app ing 2009年 3月M a r1 基于 SVG的多边形叠置分析算法初探 韩海丰 , 杨永国 , 冯金锐 () 中国矿业大学资源与地球科学学院 ,江苏徐州 221008 ( ) 【摘 要 】 SV G Sca lab le V ec to r Grap h ic即可升级矢量图形 , 是一种基于 XML 的矢量图形描述规范 。由于 SV G的很多特性非常符合 W ebG IS的特点 , 所以现在基于 SV G的 G IS网站很多 。然而 , 由于 SV G文件本身并不保存拓扑 关系 , 其空间分析功能的实现一直是一个难题 。本文介绍一种基于 SV G的叠置分析算法的实现方法 , 目的是提供 一种基于简单数据结构叠置分析的算法 。 【关键词 】 G IS; SV G; 叠置分析 ; 空间分析 ( ) 【中图分类号 】 P23115 【文章编号 】100922307 2009 02 20148203 【文献标识码 】A DO I: 1013771 / j1 issn1100922307120091021050 简单要素模型 。因此本文讨论的叠置分析是简单要素模型 1 引言 的而且结合 SV G本身特点的叠置分析 。 互联网已经成为当今信息发布最主要的一种媒介 。当 3 矢量格式图形叠置分析的主要问题 今大量的音频 、视频 、图像 、图形等信息充斥着整个网络 , 由于有些输入图层和叠置图层并不在一个区域内 , 因 从而导致了 In te rne t带宽显得日益紧张 。地理信息的数据是 一种海量数据 , 因此网络地理数据更应该注意表现形式和 此无从求叠置 , 如图 1所示 。 数据量的大小 。 SV G应运而生 。首先 , SV G是一种矢量格 图 1显示 a1和 a2根本就不会有交点 , 所以对它们求交 式 , 数据量大大减少 ; 其次 SV G提供了丰富的图形对象和 点是没有意义的 。如果输入图层为多边形 , 则时间复杂度 显示样式并可以分组显示 , 可以分层显示地理实体 ; 第三 , ( ) (为 O P ×Q 其中 P, Q 分别代表输入多边形和叠加多边形 SV G具有丰富的消息触发及事件响应函数 , 可以实现与地 ) 的个数 。而如果对某个输入多边形与某个叠加多边形的弧 理对象的交互操作 ; 第四 SV G是 XML 的一个扩展应用 , 它 (具有设计完善的 DOM Docum en t O b jec t Mode l, 文档对象模 () (段求交点 , 其时间复杂度又为 O N ×M 其中 N , M 分别是 [ 1 ] ) 型接口 ; 第五 , 可自定义扩充属性元素 ; 另外 SV G还 ) 输入多边形和输出多边形的弧段数 , 所以总时间复杂支持超链接 。所有以上特征为实现基于 SV G的 W ebG IS提 度为 :[ 2 ] 供了可能 。由于 SV G文件不保存拓扑关系 , 空间分析较 N M P Q a b难实现 。本文尝试着用一种相对高效的算法实现其叠置分 ( )Q = t a, b, c, d ????析功能 。 a = 1 b = 1 c = 1 d = 1 P 和 Q 分别代表输入图层和叠加图层中参与叠置的多 边形的个数 , N 和 M 分别表示输入图层中的第 a 个多边 a b ( ) 形和叠加图层中第 b个多边形中的弧段数 , t a, b, c, d 表示输入图层中的第 a 个多边形的第 c个弧段与叠置图层 2 叠置分析简介() 中的第 b个多边形的第 d 个弧段的叠置 求交 时间 。尽量 减小 N 、M 、P、Q 可以减小计算量 。本文对输入图层和 a b 空间叠置分析是将两层或多层地图要素进行叠加产生叠加图层进行分块实现了减小 P、Q 值 ; 通过判断输入图层 一个新要素层的操作 , 其结果是将原来要素分割生成新的 某实体的 “最小无偏转包含矩形 ”与叠加图层某实体的 [ 3 ] 要素 , 新要素综合了原来两层或多层要素所具有的属性 。 “最小无偏转包含矩形 ”的重叠与否决定两多边形实体是否 叠置分析多采用拓扑模型来实现 , 也称为拓扑叠置 。 要进行求交运算 , 从而减小了 N 、M 的值 。 a b 因此在实际应用中 , 对于无完整拓扑关系的原数据层 , 要 4 实现输入图层和叠加图层的分块 先建立完整的拓扑关系 。当数据规模过大时 , 拓扑构建操 作需耗费大量的时间 , 甚至会失败 。在当今各主流地理信 首先介绍一个 “最小无偏转包含矩形 ”的概念 。该矩 形的左上角的 x坐标值是该矩形包含图形的最小 x 值 , y 坐 息软件中 , 都引入了不维护拓扑信息的数据模型 , 如 A rc2 [ 4 ] 标值是该图形的最大 y 值 ; 右下角的 x 坐标值是该矩形包 G IS中的 shap efile数据格式和 M ap G IS710 简单要素模型 。含图形的最大 x值 , y坐标值是该图形的最小 y 值 。它与最 SV G在表示空间地物时并不会保存其拓扑结构信息 , 属于小外包含矩形的区别如图 2、图 3。 在 SV G中建立最小无偏转包含矩形的关键是取得该图 形的所有节点的坐标值 , 然后取出最大和最小的 x、 y 的 ( ) 作者 简 介 : 韩海丰 19822男 , 山东 ( 值 , 代码片断如下 < p a th id = ”rec tangle1”d = ”M 0 0 L 2 4 金乡人 , 地球信息科学专业硕士研究 ) 3 5 11 3 4 2 ”style = " fill: none; stroke: b lue" / > :生 , 主要研究方向 : 地理信息系统原 ( ) va r SvgM a inM apDoc = svg11ge tSV GDocum en t ; 理与开发 。 E2m a il: zhu jiangyan2000 @ 1631com 收稿日期 : 2007211 226 ( SvgO b j = SvgM a inM apDoc1ge tE lem en tB y Id " ) rec tangle1 " ; [ 5 ] ( ) va r str = SvgO b j1ge tA ttribu teN S nu ll, " d" ; 其中 str就得到了该 p a th的坐标数据 。然后对其进行字 符串处理提取 , 将所有 x、y坐标数据分别依次存入两个数 图 5 判断两最小无偏转矩形是否有交集流程图组 。再从两个数组中分别求出各自的最小值和最大值 。这 ) 间的实体我们叫做第二类实体 ( 如 markx = 1 , m a rky = x。样就可以得到 rec tangle1 的最小无偏转包含矩形 。然后将输 涉及到 SV G特性的代码片断如下 :入图层和叠加图层进行分块 。根据最小无偏转包含矩形的 ) ( rec t1 se tA ttribu teN S nu ll, “m a rkx”, “1 ”; 添加/ /顶点坐标值判断此图形属于哪个分块 。具体实现如下 : m a rkx属性 , 并设置为 1?为每个实体添加两个属性即 m a rkx和 m a rky做为标识 ) ( rec t1ge tA ttribu teN S nu ll, “m a rkx”; / /取出标识位 ;位 , 用于标识该实体的最小无偏转包含矩形 R 所在分块 。 以上实现了图层的四分块 。四分块虽然很大程度上减规定 : 当 m a rkx = 0 时 , R 在左半区 , m a rkx = 1 时 , R 在右 小了运算量 , 但在实际应用中 , 有时四分块还不能满足要 半区 ; 当 m a rky = 0 时 R 在下半区 , m a rky = 1 时 R 在上半 求 , 这时候我们就考虑更密集的分块 。原则上来说 , 我们 (区 ; 当 m a rkx = x 因为 m a rkx、m a rky是字符串变量 , 所以正 可以有九分块 、十六分块等等一系列分块方法 , 但是为了 确写法应该是 m a rkx = ”x”, m a rky = ”x”, 此处为简化起 2x () 方便拓展这种算法的应用 , 我们只使用 2 x > 0, x ?Z) 见省略了引号 表示 R 在左右方向上既在左半区又在右半 这种方式进行分块 。下面介绍当 x = 2 , 即十六分块的算法区 , 同理 , m a rky = x表示 R 在上下方向上既在上半区又在 实现 。(下半区 。令初始值 m a rkx = x, m a rky = x 即不确定在哪个分 ?将整个图层四分块 , 得到四个分块 , 并且得到了每 ) (区 ; ?做图层的 y 方向的等分线 , 即取得 y/2 的值 假 m ax () 个实体所属区域 如前面介绍 ; ?由以上步骤得到四个分 ( ) ) 设原点坐标为 0 , 0 ; ?将图层中所有图形的最小无偏 块 , 并且得到其各自包含的实体的 ID。为每个包含在分块 () 中的实体 即 m a rkx和 m a rky的值都不等于 x 的实体对象 转包含矩形的底边的 y坐标与 y/2 相比较 , 如果 y> = b m ax b 再分别添加两个代表标识位的属性项 : m a rkx1 和 m a rky1, y/2, 将该图形的 m a rky标识位置为 “1 ”; ?将图层中所 m ax 并设置初始值为 x。每个分块再对自己包含的实体进行四分 有图形的最小无偏转包含矩形的上边的 y坐标与 y/2 相 t m ax 块 。此时每个实体的所属区域用 m a rkx1 和 m a rky1 来表示 , 比较 , 如果 y< = y/2 , 将该图形的 m a rky标识位置为 t m ax 其表示方法跟四分块方法相同 ; ?从叠置图层依次选择每 “0”; ?做图层的 x方向的等分线 , 即取得 x/2 的值 ; ? m ax 个多边形 P, 提取它的标识信息 。此时 P 的标识信息可能 只含有 m a rkx 和 m a rky, 也 可 能 即 有 m a rkx、m a rky 也 有 将图层中所有图形的最小无偏转包含矩形的左边的 x坐标 l m a rkx1、m a rky1。如果 P 只具有 m a rkx和 m a rky属性 , 判断 与 x/2相比较 , 如果 x> = x/2 , 将该图形的标识位 m ax l m ax 输入图层中每个图形 Q 的 m a rkx、m a rky。如果 P 和 Q 满足 m a rkx置为 “1”; ?将图层中所有图形的最小无偏转包含 xboo l、yboo l相与的结果为 1 , 则将 Q 的 ID 值存入一个数组 矩形的右边的 x坐标与 x/2相比较 , 如果 x< = x/2 , r m ax r m ax filte r1 保 存 。如 果 P 即 具 有 m a rkx、m a rky 也 有 m a rkx1、 将该图形的标识位 m a rkx置为 “0 ”; ?其余处于两块之间 m a rky1属性 , 首先提取 P 的 m a rkx、m a rky, 判断输入图层 ( ) 或者四个分块之间的标识分别为 : m a rkx = x, m a rky = x, 中每个图形 Q 的 m a rkx、m a rky。如果此时两个实体的 m a rkx () ( ) ( m a rkx = 0 , m a rky = x, m a rkx = 1, m a rky = x, m a rkx 和 m a rky不满足 xboo l、yboo l相与的结果为 1 , 取下一个 Q。 ) () = x, m a rky = 0, m a rkx = x, m a rky = 1 ; 如果为 1 , 首先判断 Q 是否具有 m a rkx1、m a rky1 属性 , 如 经过以上步骤可以实 果没有 , 将 Q 的 ID 值存入 filte r1 , 否 则 取 出 P 和 Q 的 现将图层分块的目的 , 其 m a rkx1、m a rky1, 如 果 两 者 的 m a rkx1 和 m a rky1 不 满 足对应分块的标识如图 4。 xboo l、yboo l相与的结果为 1 , 取下一个 Q , 否则将 Q 的 ID 假设参与叠置的叠加 值存入 filte r1数组 。由此把所有可能与 P 相交的实体的编 图层中某一图形的分块标 号都存入了 filte r1数组中。 识为 m a rkx = m , m a rky = n 由此可以类推 32 分块 、64而输入图层中图形的分块 分块等情况 。但是如果分块太 标 识 为 m a rkx ’ = m ’, 多就容易造成实体并不能被分 m a rky’ = n ’。给 出 两 个 配到某一区域内 , 而是在两块 图 4分块标识 判断条件 xboo l和 yboo l用甚至是三块或更多的区域之间 , 于检查 m 和 m ’以及 n和 n’相等与否 , 初始值都为 0。规这样就失去了分块的意义 。因 定 : 如果 m = x, 则 xboo l = 1 , 如果 m ! = x而且 m = m ’则此具体应该采用多少分块应根 xboo l = 1; 如果 n = x, 则 yboo l = 1 , 如果 n! = x而且 n = n’ 据实际情况确定 。这里考虑用则 yboo l = 1。然后将 xboo l与 yboo l相与 , 只有结果为 1的其 最小无偏转包含矩形才可能有交集 。图 5为流程图 。 对于最小无偏转包含矩形完全落在某一分块内的实体 150 测绘科学 第 34卷 量比值作为一个参考依据 。当比值小于一定值时 , 就不应断 , 对于有交点的线段 , 记录下坐标值 。并且根据步骤 该再进行分块 。的结果 , 如果 po in t1 在 P2 外面则第一个交点的类型是 (引入交点 , 然后下一个为引出交点 , 依次交替取值 此 5 判断最小无偏转包含矩形是否重叠 处并未考虑两多边形的边重合或者两多边形在顶点处相 通过以上步骤可以筛选出可能与多边形 P 相交的输入 交的情况 ,关于此种情况请参考刘勇奎等一个有效的多 图层中的面实体记录集 T。然而这种筛选还是不够彻底 , [ 8 ] ) 边形裁减算法 。 因为记录集中还是有大量的实体实际上并未与 P 相交 , 所 求出所有交点以后 , 根据这些交点连同两参与叠置的 以也谈不上叠置分析了 。如图 5所示 , b、 c、 d 等都是符合 上述条件而存入 filte r1 数组中的实体 , 实际上都不与 a 相 多边形的边界求出最终的结果多边形 。具体步骤如下 : 交 。从已经初步筛选出的记录集 T 中选出最小无偏转包含 ?从面状多边形边界中提取始于引入交点而止于引出 矩形与叠加图层中某一多边形 P 的最小无偏转包含矩形有 交点的边界 ; ?从窗口多边形中提取始于引出交点而止于 重叠的记录 : 假设 P 和记录集 T 的某实体的最大 、最小 x 引入交点的窗口边界 ; ?根据交点之间连接关系 , 形成闭 合多边形即为结果多边形 。 ’ ’ x、 x、 y、 y和 x、 x、 坐标 和 y 坐 标 分 别 为 612 属性分配m axm in m axm in m axm in ’ ’ ’ 、y。建立数组 filte r2 , 将不符合条件 “x> x或者叠置分析不仅生成了新的空间关系 , 还将输入数据层 y m axm in m in m ax’ ’’的属性联系起来产生了新的属性关系 。设置多边形标识点 , y> y或者 x< x或者 y< y”的记录存入 filte r2。 m in m axm ax m inm ax m in 传递属性 。叠置图中的多边形包含着各个输入层中的多重 6 叠置分析实现属性信息 。 基于矢量数据的叠置分析可分为拓扑求交过程和属性 7 结束语 [ 6 ] 分配过程两步 。 文章阐述了一种基于 SV G矢量格式的简单数据模型的 求输入图层中的多边形与叠加图层中的多边形相交的 叠置分析方法 , 并重点探讨了其算法的优化 。由于 SV G可 实体的交点坐标 。取出叠加图层中的某一个多边形 P, 求 以为某一代表空间实体的对象赋予特定的属性信息 , 从而 通过添加 m a rkx和 m a rky属性实现了对空间实体的分块操 出输入图层与 P的叠置结果 , 进而可以求出叠加图层的所 作 。而且该分块操作具有一定的可扩展性 , 比如从四分块 有多边形与输入图层的叠置 。在进行求叠置分析之前 , 为 到十六分块 。尤其值得一提的是 , 分块操作是一劳永逸的 , 了问题的简化 , 我们先做一个假设 , 即 : 多边形的构成都 即只是第一次进行该操作 , 以后表示分块的 m a rkx和 m a rky 是逆时针的 。以及 m a rkx1和 m a rky1等属性信息将被物理存储 。通过判断 611 拓扑求交最小无偏转包含矩形重叠与否 , 进一步减小了线段求交的 为了减小计算量 , 我们在求两线段的交点时 , 先简单 计算量 。通过以上两个步骤大大减少参与求交点运算的线 段的数量 。通过判断两条线段相交与否 , 对符合条件的线 判断线段是否相交 , 再求交点 。在图 7a中 , 线段 AB 与 CD 段才进行求交点运算 , 从而又进一步减小了运算量 。 相交 , 我们发现相交的充分 必要条件是 C, D 两点分别 参考文献 位于 AB 线段的两侧 , A , B 两点亦分别位于 CD 线段的 两侧 。如果 AB 与 CD 不相交 7 两线段相交与图 王家耀 , 等 1基于 SV G的地理信息编码与 DOM 交互 [ 1 ] () 或者相交于延长线上 , 则 不相交的情况( ) 解析实现 [ J ]. 测绘学院学报 , 2005, 22 2 1 冯艳() 以上特征不存在 图 7b , 因 [ 2 ] 杰 1基于 SV G的 W ebG IS实现技术 [ D ]. 武汉 : 武汉 此我们可以先行判断 AB 与 CD 的交点是否存在 。由解析几 大学 , 20051 何可知 , 直线可以看做空间平面与 z = 0 的平面的交线 , 因 [ 3 ] 董鹏 , 等 1基于 R +树的地图叠加分析双重循环算法此直线将平面域分为正负区域 。如果 C, D 位于 AB 的两 ( ) [ J ]. 中国图象图形学报 , 2003, 8 6: 703 27041 谢侧 , 则分别位于正负区域 。 [ 4 ] 忠 , 等 1 简单要素模型下多边形叠置分析算法 设 AB 直线的方程为 ax + by + c = 0 , C、D 的坐标分别 ( ) [ J ]. 地理与地理信息科学 , 2007, 23 3 : 19 2201 高( ) ( ) ( ) ( 为 x, y、 x, y, 则如果 a x+ b y+ cax+ b y+ c c d d c c d d [ 5 ] 峰 1谈俊忠 1JavaScrip t在基于 SVG的网络地图中的应 ) c< 0, 我们就确认有 C、D 位于直线 AB 的两侧 。A、B 对 [ 7 ] () () 用 [ J ]. 江西师范大学学报 自然科学版 , 2004, 31 直线 CD 有类似的判断准则 。 [ 6 ] 李鲁群 , 等 1GIS中空间数据叠置分析的优化算法设计 ( 求出两个多边形的所有交点 , 并判断交点类型 引入交 () () [ J ]. 山东科技大学学报 自然科学版 , 2002, 21 21 ) 点或引出交点 。具体步骤如下 : 郭 仁 忠 1 空 间 分 析 [ M ]. 北 京 : 高 等 教 育 出 版 [ 7 ] (?叠置多边形 P1 的第一个线段 L 1 起点为 po in t1 , 社 , 20011 ) 终点为 po in t2 , 求 出 其 直 线 方 程 ; ?输 入 多 边 形 P2 , [ 8 ] 刘勇奎 , 等 1 一个有效的多边形裁减算法 [ J ]. 软 通过点与多边形关系判断 po in t1 与 P2 的拓扑关系 ; ? ( ) 件学报 , 2003 , 14 4 : 84728481 依次取出输入多边形 P2 的每个组成线段 L n 进行相交判 Pre l im ina ry study on a lgor ithm s of po lygon ’s over la y ana ly s is ba sed on SVG ( ) A b stra c t: SV G Sca lab le V ec to r Grap h icis sca lab le vec to r grap h ic s tha t is a ru le of de sc rip tion of vec to r grap h ic s1 B ecau se a lo t of fea tu re s of SV G a re ve ry con sisten t w ith cha rac te ristic s of W ebG IS, now the re a re m any G IS web site s ba sed on SV G1 A s the SV G docum en t itse lf doe s no t p re se rve the topo logica l re la tion s, it’ s d ifficu lt fo r sp a tia l ana lysis1 Th is p ap e r in troduce s a m e thod of ove rlay ana lysis ba sed on SV G1 The p u rpo se of th is p ap e r is to p rovide an a lgo rithm of ove rlay ana lysis ba sed on samp le da ta struc tu re1 Key word s: G IS; SV G; ove rlay ana lysis; sp a tia l ana lysis ( HAN H a i2feng, YAN G Yong2guo, FEN G J in2ru i Schoo l of R e sou rce s and Ea rth Sc ience s, Ch ina U n ive rsity of M in ing and Tech2 )no logy, Xuzhou 221008, Ch ina