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

基于SVG的多边形叠置 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 算法初探 测绘科学 134 No12 Vo l34卷第 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 【文献标识码 】A 【文章编号 】100922307 2009 02 20148203 DO I: 1013771 / j1 issn1100922307120091021050 简单要素模型 。因此本文讨论的叠臵分析是简单要素模型 1 引言 的而且结合 SV G本身特点的叠臵分析 。互联网已经成为当今信息发布最主要的一种媒介 。当 3 矢量格式图形叠置分析的主要问题 今大量的音频 、视频 、图像 、图形等信息充斥着整个网络 , 由于有些输入图层和叠臵图层并不在一个区域内 , 因 从而导致了 In te rne t带宽显得日益紧张 。地理信息的数据是 此无从求叠臵 , 如图 1所示 。 一种海量数据 , 因此网络地理数据更应该注意 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 现形式和 图 1显示 a1和 a2根本就不会有交点 , 所以对它们求交 数据量的大小 。 SV G应运而生 。首先 , SV G是一种矢量格 点是没有意义的 。如果输入图层为多边形 , 则时间复杂 度 式 , 数据量大大减少 ; 其次 SV G提供了丰富的图形对象和 ( ) (为 O P ×Q 其中 P, Q 分别代表输入多边形和叠加多边形 显示样式并可以分组显示 , 可以分层显示地理实体 ; 第三 , ) 的个数 。而如果对某个输入多边形与某个叠加多边形的弧 SV G具有丰富的消息触发及事件响应函数 , 可以实现与地 () (段求交点 , 其时间复杂度又为 O N ×M 其中 N , M 分别是 理对象的交互操作 ; 第四 SV G是 XML 的一个扩展应用 , 它 ) 输入多边 形 和 输 出 多 边 形 的 弧 段 数 , 所 以 总 时 间 复 杂 (具有设计完善的 DOM Docum en t O b jec t Mode l, 文 档 对 象 模 [ 1 ] 度为 :) 型接口 ; 第五 , 可自 定 义 扩 充 属 性 元 素 ; 另 外 SV G还 N M P Q a b 支持超链接 。所有以上特征为实现 基于 SV G的 W ebG IS提 ( )Q = t a, b, c, d [ 2 ] ???? 供了可能 。由于 SV G文件不保存拓扑关系 , 空间分析较 a = 1 b = 1 c = 1 d = 1 P 和 Q 分别代表输入图层和叠加图层中参与叠臵的多 难实现 。本文尝试着用一种相对高效的算法实现其叠臵分 边形的个数 , N 和 M 分别表示输入图层中的第 a 个多边 析功能 。 a b ( ) 形和叠加图层中第 b个 多边形中的弧段数 , t a, b, c, d 2 叠置分析简介 表示输入图层中的第 a 个多边形的第 c个弧段与叠臵图 层 () 中的第 b个多边形的第 d 个弧段的叠臵 求交 时间 。尽量 空间叠臵分析是将两层或多层地图要素进行叠加产生 减小 N 、M 、 P、Q 可以减小计算量 。本文对输入图层 和 a b 一个新要素层的操作 , 其结果是将原来要素分割生成新的 叠加图层进行分块实现了减小 P、Q 值 ; 通过判断输入图层 [ 3 ] 要素 , 新要素综合了原来两层或多层要素所具有的属性 。 某实体 的 “最 小 无 偏 转 包 含 矩 形 ”与 叠 加 图 层 某 实 体 的 叠臵分析 多 采 用 拓 扑 模 型 来 实 现 , 也 称 为 拓 扑 叠 臵 。 “最小无偏转包含矩形 ”的重叠与否决定两多边形实体是否 因此在实际应用中 , 对于无完整拓扑关系的原数据层 , 要 要进行求交运算 , 从而减小了 N 、M 的值 。 a b 先建立完整的拓扑关系 。当数据规模过大时 , 拓扑构建操 作需耗费大量的时间 , 甚至会失败 。在当今各主流地理信 4 实现输入图层和叠加图层的分块 息软件中 , 都引入了不维护拓扑信息的数据模型 , 如 A rc2 [ 4 ] G IS中的 shap efile数据格式和 M ap G IS710 简单要素模型 。 首先介绍一个 “最小无偏转包含矩形 ”的概念 。该矩 SV G在表示空间地物时并不会保存其拓扑结构信息 , 属于 形的左上角的 x坐标值是该矩形包含图形的最小 x 值 , y 坐 标值是该图形的最大 y 值 ; 右下角的 x 坐标值是该矩形 包 含图形的最大 x值 , y坐标值是该图形的最小 y 值 。它与最 ( ) 作者 简 介 : 韩 海 丰 19822男 , 山 东 小外包含矩形的区别如图 2、图 3。 金乡人 , 地球信息 科学专 业 硕 士 研 究 在 SV G中建立最小无偏转包含矩形的关键是取得该图 生 , 主要研究 方 向 : 地 理 信 息 系 统 原 形的所有节 点 的 坐 标 值 , 然 后 取 出 最 大 和 最 小 的 x、 y 的 理与开发 。 ( 值 , 代码片断如下 < p a th id = ”rec tangle1”d = ”M 0 0 L 2 4 E2m a il: zhu jiangyan2000 @ 1631com ) 3 5 11 3 4 2 ”style = " fill: none; stroke: b lue" / > : ( ) va r SvgM a inM apDoc = svg11ge tSV GDocum en t ; 收稿日期 : 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。为每个包含在分块 转包含矩形的底边的 y坐标与 y/2 相比较 , 如果 y> = b m ax b () 中的实体 即 m a rkx和 m a rky的值都不等 于 x 的实体对象 y/2, 将该图形的 m a rky标识位臵为 “1 ”; ?将图层中所 m ax 再分别添 加 两 个 代 表 标 识 位 的 属 性 项 : m a rkx1 和 m a rky1, 有图形的最小无偏转包含矩形的上边的 y坐标与 y/2 相 t m ax 并设臵初始值为 x。每个分块再对自己包含的实体进行四分 比较 , 如果 y< = y/2 , 将 该 图 形 的 m a rky标 识 位 臵 为 t m ax 块 。此时每个实体的所属区域用 m a rkx1 和 m a rky1 来表示 , “0”; ?做图层的 x方向的等分线 , 即取得 x/2 的值 ; ? m ax 其表示方法跟四分块方法相同 ; ?从叠臵图层依次选择每 将图层中所有图形的最小无偏转包含矩形的左边的 x坐标 l 个多边形 P, 提取它的标识信息 。此时 P 的标识信息可 能 与 x/2相比较 , 如 果 x> = x/2 , 将 该 图 形 的 标 识 位 m ax l m ax 只含 有 m a rkx 和 m a rky, 也 可 能 即 有 m a rkx、 m a rky 也 有 m a rkx臵为 “1”; ?将图 层 中 所 有 图 形 的 最 小 无 偏 转 包 含 m a rkx1、m a rky1。如果 P 只具有 m a rkx和 m a rky属性 , 判断 矩形的右边的 x坐标与 x/2相比较 , 如果 x< = x/2 , r m ax r m ax 输入图层中每个图形 Q 的 m a rkx、m a rky。如果 P 和 Q 满足 将该图形的标识位 m a rkx臵为 “0 ”; ?其余处于两块之间 xboo l、 yboo l相与的结果为 1 , 则将 Q 的 ID 值存入一个数组 ( ) 或者四个分块之间 的标识分别为 : m a rkx = x, m a rky = x, filte r1 保 存 。如 果 P 即 具 有 m a rkx、 m a rky 也 有 m a rkx1、 () ( ) ( m a rkx = 0 , m a rky = x, m a rkx = 1, m a rky = x, m a rkx m a rky1属性 , 首先提取 P 的 m a rkx、m a rky, 判断输入图层 ) () = x, m a rky = 0, m a rkx = x, m a rky = 1 ; 中每个图形 Q 的 m a rkx、m a rky。如果此时两个实体的 m a rkx 经过以 上 步 骤 可 以 实 和 m a rky不满足 xboo l、 yboo l相与的结果为 1 , 取下一个 Q。 现将图 层 分 块 的 目 的 , 其 如果为 1 , 首先判断 Q 是否具有 m a rkx1、m a rky1 属性 , 如 对应分块的标识如图 4。 果没有 , 将 Q 的 ID 值 存 入 filte r1 , 否 则 取 出 P 和 Q 的 假设参 与 叠 臵 的 叠 加 m a rkx1、m a rky1, 如 果 两 者 的 m a rkx1 和 m a rky1 不 满 足 图层中 某 一 图 形 的 分 块 标 xboo l、 yboo l相与的结果为 1 , 取下一个 Q , 否则将 Q 的 ID 识为 m a rkx = m , m a rky = n 值存入 filte r1数组 。由此把所有可能与 P 相交的实体的 编 而输入 图 层 中 图 形 的 分 块 号都存入了 filte r1数组中 。 标 识 为 m a rkx ’ = m ’, 由此可以类推 32 分块 、 64 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 引入交点的窗口边界 ; ?根据交点之间连接关系 , 形成 闭 合多边形即为结果多边形 。 ’ ’ 坐标 和 y 坐 标 分 别 为612 属性分配 x、 x、 y、 y和 x、 x、 m axm in m axm in m axm in ’ ’ ’ 叠臵分析不仅生成了新的空间关系 , 还将输入数据 层 y、 y。建立数组 filte r2 , 将不符合条件 “x> x或者 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, 求 以为某一代表空间实体的对象赋予特定的属性信息 , 从而 出输入图层与 P的叠臵结果 , 进而可以求出叠加图层的所 通过添加 m a rkx和 m a rky属性实现了对空 间 实 体 的 分 块 操 有多边形与输入图层的叠臵 。在进行求叠臵分析之前 , 为 作 。而且该分块操作具有一定的可扩展性 , 比如从四分 块 到十六分块 。尤其值得一提的是 , 分块操作是一劳永逸的 , 了问题的简化 , 我们先做一个假设 , 即 : 多边 形的构成都 即只是第一次进行该操作 , 以后表示分块的 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 ] 王家耀 , 等 1基于 SV G的地理信息编码与 DOM 交互 () 或者相交于延长线上 , 则 不相交的情况 ( ) 解析实现 [ 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 word文档格式规范word作业纸小票打印word模板word简历模板免费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