简单要素模型下多边形叠置分析算法

简单要素模型下多边形叠置 分析 定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析 算法 1 1 ,2 1谢 忠,叶 梓,吴 亮 ( )1 . 中国地质大学信息工程学院 ,湖北 武汉 430074 ;2 . 教育部地理信息系统软件及应用工程中心 ,湖北 武汉 430074 摘要 :现有的矢量空间叠臵分析多采用拓扑模型 ,要求建立完整的数据拓扑关系 。该文采用简单要素模型 ,以多边 形叠臵交运算为例 ,介绍简单要素模型下空间叠臵分析的具体实现 ,着重讨论多边形交运算的交替搜索算法 ,在线 段求交中对连续出入点 、重交点等特殊数据进行处理 。在实际应用中 ,该算法可较好解决大规模复杂数据层的叠 臵交运算 ,比同规模的拓扑叠臵运算效率高 。 关键词 :简单要素模型 ;空间叠臵分析 ;多边形求交 () 文章编号 :1672 - 0504 200703 - 0019 - 05 中图分类号 : P208 文献标识码 :A er nto n 算法使用的是树形数据结构 ,而 Vat ti 算法和 引言0 Greiner - Ho r mann 算法使用的是双线性链表数据结 8 矢量空间叠臵分析用以生成用户感兴趣的新数 构 。刘勇奎等通过单向链表数据结构和错切变换 法改进 Weiler - At her nto n 算法 ,简化了数据结构 ,加 据层及其所含属性 ,多采用拓扑模型来实现 ,也称为 拓扑叠臵 。在拓扑叠臵前 ,需假设每一层都是平面 快了执行速度 。文献 9 、10 也是在这些算法的基 增强的 ,即已经建立了完整的拓扑关系 ,叠臵后的结 础上 ,使用 V C 6 平台支持的数据存储模型和函数功 1 果也是平面增强的。因此在实际应用中 , 对于无 ,通过求交前的数据预处理保证裁剪结果正确性 。能 完整拓扑关系的原数据层 ,要先建立完整的拓扑关 文献 4 介绍了基于拓扑模型和简单数据模型的两 系 ,当数据规模过大时 ,拓扑构建操作需耗费大量的 类算法 ,比较两者的优劣并提出了可实际应用的基 时间 ,甚至会失败 ,且新数据层中的拓扑关系并不为 于交点搜索的多边形叠臵分析算法 。 用户所关心 。在当今各主流地理信息软件中 , 都引 空间 叠 臵 作 为 GIS 中 空 间 分 析 的 重 要 组 成 部 入了 不 维 护 拓 扑 信 息 的 数 据 模 型 , 如 Arc GIS 中 的 分 ,旨在满足实际地学应用的需求 。因此 ,在设计无 shapefile 数 据 格 式 和 Map GIS 710 简 单 要 素 模 型 。 拓扑简单数据模型叠臵分析算法时 ,要考虑数据规 将复杂要素模型中完成的空间叠臵分析功能在简单 模 、响应时间和同名点误差等实际情况 ,而不能简单 要素模型下实现 ,则可在满足用户需求的同时 ,消除 等同于多边形裁剪算法 。基于以上考虑 , 本文讨论 构建数据拓扑关系这一约束条件 ,降低了操作的复 简单要 素 模 型 下 空 间 叠 臵 分 析 中 的 多 边 形 叠 臵 运 杂度 ;并且由于无需构建拓扑信息 ,处理的速度将优 算 ,并重点介绍交运算操作 ,对交运算的适当修改同 于原有的复杂要素模型叠臵分析 。 样适用于差运算和并运算操作 。本文提出的算法采 用内存直接存储 、对内存数据顺序读取的方案 ,避免 基于拓扑模型的多边形空间叠臵分析算法往往 + 都是线段求交和弧段重组 ,如基于 R 树的地图叠加 了传统方法中的存储指针 ,大大降低了数据存储规 2 分析双重循环算法,通过确定参加叠臵拓扑求交 模 。该算法适用于地图数据中的任意多边形 , 包括 的最小矢量集合进行快速空间数据叠臵分析的优化 带内环的多边形数据 ,并可消除地图数据中同名点 3 误差对算法正确性的影响 。 算法。这些拓扑数据结构下的叠臵算法 , 实际上 是放弃图层中的拓扑关系 ,直接对两组线段进行相 基本概念与原理1 4 交处理 ,在处理过程中重新建立拓扑关系。 简单 数据模型叠臵分析的核心算法是任意多边 实际开发经验表明 ,多边形交运算的正确性和 5 形裁剪 。在这类算法中只有 Weiler - At her nto n算 效率依赖于线段求交算法的优劣 。因此 , 本文详细 6 7 法 、Vat ti 算法及 Greiner - Ho r mann算 法 可 以 在 介绍线段求交操作的基本原理 ,并给出算法设计中 合理的时间内处理一般的情况 。其中 Weiler - At h2 多边形的相关定义 。 收稿日期 :2007 - 01 - 14 ; 修订日期 :2007 - 03 - 15 ( )基金项目 :国家 863 地球观测与导航技术领域专题资助项目 2006AA12 Z218 ( ) 作者简介 :谢忠 1968 - ,男 ,教授 ,博士生导师 ,主要研究方向为基础 GIS 研究与应用 。E - mail :zye0916 @163 . co m 1 . 1 线段交点计算成的闭 合 多 边 形 便 构 成 了 两 个 原 多 边 形 的 相 交 区 ) ) ( ( 平面上 由 P1 x, y到 P2 x, y的 线 段域 ,即结果多边形 。P1 P1 P2 P2 ) ) ( ( P1 P2 和 由 Q1 x, y到 Q2 x, y的 线 段Q1 Q1 Q2 Q2 2 算法设计 11 Q1Q2 的直线方程分别为: 2 . 1 线段求交 ( )λ)μ( x = x + x - x = x + x - x x Q1 Q2 P1 P2 P1 Q1 )λ )μ ( ( y = y + y - y y = y + y - y P1 P2 P1 Q1 Q2 Q1 根据求交公式可以判断两线段是否存在交点并 ( )x - x - - x x Q2 Q1 计算交点的坐标 ,通过外包矩形可过滤大部分不需 P2 P1Δ 令= - ( )y - y y - y P2 P1 Q2 Q1 求交的线段 ,提高运算效率 。但是 ,实际应用中存在 Δ 当?0 时 ,有 许多特殊的数据 ,忽略这些特殊情况开发的算法只 )( x - x - x - x Q2 P1 Q2 Q1 适用于理想状态 ,因此本文考虑了多边形叠臵运算 ) ( y - y - y - y Q2 P1 Q2 Q1 λS== P 中特殊 情 况 的 处 理 。其 主 要 是 指 两 多 边 形 的 边 重 Δ x - x x - x合 ,顶点在对方多边形上 ,两多边形在顶点处相交等 P2 P1 Q1 P1 y - y y - y P2 P1 Q1 P1 情况 ,造成重交点和连续出入点问题 。上述情况虽μS== Q Δ 然在多边形裁剪中不多见 ,但在 GIS 中 ,空间位臵数 Δ 当?0 时 ,说明两线段所在的直线有交点 ,当 据的不确定性带来的叠臵图层同名点误差问题屡见 λμ 且仅当?0 ,1 与?0 , 1 时两线段有交点 。交 不鲜 ,即两实际重合的边界线出现裂隙 、锯齿 。这些 点的坐标可以表示为 : 问题引入叠臵分析后 ,表现为边界数据出现大量的) ) ) )( ( Δ((Δ()x= x+ x- x3,y= y+ y- y3 1 C Q1 Q2 Q1 C Q1 Q2 Q1 异常点 ,叠臵分析结果存在大量多边形碎片 。 多边 1 . 2 交点方向判断形叠臵分析中产生的碎片可以根据有关规 ( 原理 如果两个相交多边形边的取向相同 均 13 ( ) : 则对其识别 。Goo dchild 1991 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 了 4 条规则 ) 为顺时针或逆时针方向,则对一个多边形是进点的 ) ) 1面积较小 ;2形态扁长 ,其周长与面积的平方根之 8 交点 ,对另一个多边形必是出点。 ) 比较大 ;3组成多边形的弧段仅为两条 ,分别从属于 11P1 P2 向 Q1Q2 的旋向由 F的符号决定 , ΔV V V 1 2 3 ) 不同源多边形 ; 4每个结点关联 4 条弧段 。在这里 x- xy- y P2 P1 P2 P1 1 ) ) 其中 F= 。可以使用规则 1、2对碎片进行识别 。Δ V V V1 2 3 2 x- xy- yQ2 Q1 Q2 Q1 但是 ,边界数据上的异常点问题难以直接解决 。 由此定义线段 P1 P2 与 Q1Q2 的交点 C 的方向 : 若在获得结果多边形时仍存在该问题 ,将导致叠臵 1 > 0 当 F ΔV V V1 2 3 结果的错误 。因此 ,将这些异常点数据作为特殊情 K= , K= - K P Q P- 1 < 0 当 F ΔV V V1 2 3 况 ,在线段求交时解决 ,才能保证叠臵分析的正确 。 K 值为 1 表示交点 C 是线段的入点 , K 值为 - 1 文献 9 中提到两种处理这类特殊情况的方法 。 14 表示 C 是线段的出点 。由上式可知 ,若交点 C 是一 第一种方法是刘勇奎等提出的精确处理方法 ,将 线段的出点 ,则是另一线段的入点 。 上述特殊情况分解为各类子情况 ,根据斜率判断 ,通 1 . 3 多边形相关定义过增减链表上的交点来保持入点和出点交替进行 ; 叠臵操 作 的 两 图 层 分 别 称 为 主 图 层 和 叠 臵 图 该方法精确但复杂 ,对于 GIS 数据中的大型多边形 , 层 。相应的 ,图层中的多边形分别称为主多边形和 逐段计算并判别斜率的运算量过大 。第二种方法是 叠臵多 边 形 。地 图 数 据 中 的 多 边 形 均 为 简 单 多 边对重合边的一个顶点或与交点相同的顶点进行很小 12 ) 形 ,即满足下面两个条件的多边形: 1循环排列 的移动来避免上述特殊情况 ;该方法易于实现 ,但由 ) 中相邻线段对的交是它们之间共有的单个点 ; 2不 于会导致较大的累计误差 ,也不适用于 GIS 中的叠 相邻的线段对不相交 。臵分析 。据此 ,均衡考虑准确性和运算的复杂度 ,提 在这里 ,将多边形外环方向均定为逆时针 ,内环 出新的解决方法 。 方向均定为顺时针 ,即多边形外环上的点按逆时针 相交的两线段 P1 P2 和 Q1Q2 ,以 P1 P2 为主线 方向存储 ,内环上的点按顺时针方向存储 。这样多( ) 段 ,直线方程可表示为 F x , y= Ax + By + C = 0 ,其中 : 边形的内 、外按照右手法则 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 ,多边形行进方向的 () A = y2 - y1 ,B = x1 - x2 ,C = - Ax1 + By1= x2y1 - x1y2 。左边为内部 ,右边为外部 。由于两相交多边形上的 将 Q1 和 Q2 两点相对于线段 P1 P2 的位臵以及 按照右手法则其相对于多边形 P 的位臵表示为 : 交点是出点 、入点交替出现 ,这些成对出现的交点形 > 0 直线上方的点多边形的外点 法 ,实现的交多边形的输出算法如下 : ( ) F x,y= 0 直线上的点 多边形上的点 Q Q )( for 取交点 C 且 C 没有被访问过直线下方的点 多边形内的点 < 0 { 表 1 的解决方案消除了连续出入点的问题 , 对 / / 根据当前交点是入点或出点 ,判断起始搜索方向 ) (于重交点问题采取交点方向累计的方法 。根据表 1if 当前交点为入点 从 C 出发沿 A 搜索交多边形可得到任一交点的方向 ,使用一个标志位 Flag 标记 else / / 当前交点是出点 方向 ,入点 Flag 值为 1 ,出点 Flag 值为 - 1 。对于存 从 C 出发沿 B 搜索交多边形 在重交点问题的交点 ,将其所有交点的标志位加和 , FlagDot 记录当前处理的交点若其代数和为 0 ,则取消形成此重点的各交点 ;否则 , FirstDot 记录该结果多边形的起始交点 合并为一个交点 ,并以其代数和的符号作为其实际 当前交点 C 存入结果多边形的点序列中 方向 。按此方案 , 可以很好的解决连续出 入 点 和 重 do { ( ) 交点问题 ,并且只有两种情况时需要调用式 1计算 访问下一个点交点 ,减少了运算次数 ,提高了算法的效率 。 ) (if 当前点为普通顶点 表 1 线段求交处理方案Ta ble 1 The sol ution of the l ine intersection 该顶点存入结果多边形的点序列中 ,继续向后搜索 ) (if 当前点为圈标记) (F x,yQ1 Q1> 0 = 0 < 0 ()F x,y Q2 Q2 反向搜索至该圈起始坐标点处( ) 据式 1求交点 > 0 无 无 ()else / / 该点为交点 C next - ( )出点 Q2 为交点{ = 0 无 无 ( )出点 将当前交点存入结果多边形的点序列中 ,转到另一 ( ) 据式 1求交点 为交点 Q1 无 < 0 ( )( )入点入点 个多边形 上 搜 索 , 搜 索 方 向 不 变 , 修 改 当 前 交 点 的 标 志 位 FlagDot = C next - 2 . 2 多边形相交关系确定 } GIS 空间叠臵运算中 , 两 图 层 中 的 大 部 分 多 边 ( ) }while FirstDot ! =FlagDot这时搜索到一个交多边形 ,结形并 不 存 在 相 交 关 系 , 许 多 多 边 形 存 在 包 含 关 系 。 果多边形个数加 1 对原有两个多边形上的内环作判别 , 对不相交多边形的过滤 ,或不经过线段求交操作即 若其 label 点落在结 可确定大多数的包含关系 ,对算法实现的时间复杂 果多边形内 ,则应作为结果多边形的子区 } 度有很大的帮助 。 交点按 顺 序 分 别 插 入 两 个 多 边 形 的 顶 点 序 列 确定多边形相交 、包含关系最简单的方法是外 中 ,由于多边形按照逆时针方向顺序排列 ,采用在内 包矩形 。根据主图层中多边形的外包矩形 , 可以检 存直接存储 ,因此通过对内存的顺序读取可以访问 索出叠臵图层中可能与其相交的多边形集合 。在图 整个多边形 。这里的‚访问下一个点?在实现时就是 1 中 ,根据多边形 P 的外包矩形检索到多边形集合 S 对下一内存块数据的读取 。 = { Q1 ,Q2 ,Q3} ,而多边形 Q4 不被检索 , 则不参与 2 . 4 叠置分析下面的运算 。这样得到的 S 集合相对整个叠臵图层 基于算法核心部分的设计 , 可将简单要素模型 而言 ,多边形个数较少 ,因此加快了处理速度 。 下空间叠臵分析的交运算 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 表示为图 2 。 对两图层中的多边形建立索引 , 双重循环取两 多边形进行叠臵分析 。对主图层中的多边 形 P , 通 过其外包矩形检索可能相交的叠臵图层中的多边形 集合 S 。对多边形 P 和集合 S 中的每个多边形 Q 作 线段求交和多边形搜索 ,得到多边形 P 和 Q 的结果 多边形集合 。将相应的属性归并至结果多边形 , 得 图 1 多边形相交关系 到多边形 P 和 Q 叠臵分析交运算的结果 。 Fig. 1 Intersection relation of polygons 2 . 3 交多边形搜索3 算法实现 通过得到的实际交点 ,交替搜索两个多边形的 关联边 ,构成的封闭环即为结果多边形 。基于此 ,笔 本文举例介绍多边形叠臵分析交运算的具体实 者参考并改进了文献 4 叠臵分析交多边形搜索算 现 。多边形 P 为主多边形 ,Q 为叠臵多边形 ,与之相 ( ) ) ( ( ) 应 ,将线段 PP作为主线段 , F x ,y为主线段的方 C4 , 方 向 为 出 点 Flag = - 1 ; 7 F x, 交点均 为 i i + 1Q6 ) ) ( 程 ,QQ作为相交线段 。y= 0 且 F x, y< 0 ,则线段 Q6Q7 与 P6 P7 、 i i + 1Q6 Q7 Q7 P7 P8 的交点均为 C4 ,但方向均为入点 ,即 Flag = 1 ; ) ( ) ) ( 8F x, y< 0 且 F x, y= 0 , 则 认 为 线 段 Q7 Q7 Q8 Q8 Q7Q8 与 P7 P8 、P8 P1 的交点都是 C5 ,且方向均为出 ( ) ) 点 Flag = - 1 , 累 加 之 后 C5 的 方 向 为 出 点 ; 9 ( ) ) ( F x,y= 0 且 F x, y= 0 , 则 认 为 线 段 Q8 Q8 Q9 Q9 ) Q8Q9 与 P8 P9 没 有 交 点 ; 10 线 段 Q9Q10 与 线 段 P8 P9 、P9 P1 均没有交点 。 至此 ,计算了所有相交线段的交点 ,得到交点数 组 C1 、C2 、C3 、C4 、C5 , 其中 C4 被重复记录了 4 次 , 但这 4 次 的 交 点 方 向 分 别 为 出 点 、出 点 、入 点 和 入 点 ,累加代数和为 0 ; C5 被记录了 2 次 ,但方向均为 出点 ,累加代数和为 - 2 。因此 , C4 交点被取消 , C5 方向 为 出 点 。由 此 得 到 的 交 点 数 组 为 C1 、C2 、C3 、 C5 ,将该数组插入原顶点数组正确的位臵 。 () 3从 C1 开始 , 搜索交多边形 。C1 为入点 , 在 多边形 Q 上逆时针搜索 ,途经 Q3 、Q4 达到 C2 ,转向 多边形 P 上继续逆时针搜索 。遇到交点 C3 后转向 图 2 多边形叠置分析交运算流程 多边形 Q 的边 ,由于 C4 交点被取消 ,故沿多边形 Q Fig. 2 The algorithm flow of intersection operation f or polygon overlay 逆时针依次经过 Q6 、Q7 , 到达交点 C5 后转向多边 () 1根据判断多边形包含关系的方法 ,过滤掉无 形 P ,回到起始交点 C1 。这样 ,由 C1 ?Q3 ?Q4 ?C2 需进行线段求交和多边形搜索的多边形对 。为方便 ?C3 ?Q6 ?A7 ?C5 ?P8 ?P9 ?P1 ?C1 形成的闭 () 说明 ,多边形 P 的叠臵集合中只有多边形 Q 图 3。 合区域 ,即为多边形 P 和 Q 叠臵形成的交区域 。判 断发现 ,结果多边形不存在内环 ,因此将此闭合区域 作为多边形 P 和 Q 叠臵分析的结果多边形 。 () 4按照原多边形 P 、Q 的属性对结果多边形做 属性归并操作 ,得到该多边形对叠臵分析的结果空 间数据及其相应的图形数据 。对主图层中的每个多 边形进行叠臵分析交运算 ,输出的结果数据组成叠 臵分析结果图层 。 图 3 多边形叠置分析交运算示例 Fig. 3 The exa mple of the intersection operation f or polygon overlay 试验与讨论4 () 2根据线段求交方法 ,依次计算多边形 P 与 Q ) ) ) ( ( 各线段的交点 :1F x,y> 0 且 F x,y= 0 , Q1 Q1 Q2 Q2 简单要素模型下的多边形叠臵分析与拓扑模型 ) ) ( 则认为线段 P1 P2 与 Q1Q2 无交点 ; 2F x,y= Q2 Q2 下的叠臵分析一样 ,规模是线性增长的 ,其中线段求 ( ) 0 且 F x, y< 0 , 则认为线段 P1 P2 与 Q2Q3 相 Q3 Q3 交操作对算法效率的影响最大 ,通过空间数据索引 ( ) ) ( )交 ,交点为 C1 ,方向为入点 Flag = 1; 3F x, y Q3 Q3 和空间数据内存管理调度机制保障算法的效率 。除 ) ( < 0 且 F x, y= 0 , 则认 为 线 段 P5 P6 与 Q3Q4Q4 Q4 线段求交外 ,拓扑模型下的叠臵分析需要重新构建 ( ) ) ( 相交 ,交点为 C2 ,方向为出点 Flag = - 1; 4F x, Q4 拓扑关系 ,因此当线段求交效率接近时 ,拓扑模型的 ) ) ( y= 0 且 F x, y> 0 , 则 认 为 线 段 P5 P6 与 Q4 Q5 Q5 叠臵效率略差于简单要素模型 。 ) ) ) ( ( Q4Q5 无交点 ;5F x,y> 0 且 F x,y< 0 , Q5 Q5 Q6 Q6 以 Map GIS 710 平台为基础 ,按照本算法实现的 ( ) 则认为线段 P5 P6 与 Q5Q6 相交 ,按照式 1计算出 简单要素模型下的空间叠臵方法分析交运算功能 , ( ) ) ( ) 交点 C3 ,方向为入点 Flag = 1;6F x,y< 0 且 Q5 Q5 在对实际数据处理中得到较好的应用 ,并与拓扑模( ) F x,y= 0 ,则认为线段 P6 P7 、P7 P8 与 Q5Q6 的 Q6 Q6 型下的叠臵分析进行对比试验 ,结果如表 2 所示 。 表 2 各数量级下简单要素模型与拓扑模型的对比分析 Ta ble 2 Comparison of the simple data model and the topological data model ( )叠臵分析交运算运行时间 ms 多边形数量 结果图层多边形数量 数量级 主图层 叠臵图层 简单要素模型 拓扑模型 简单要素模型 拓扑模型 112 8 39 39 154 891 10 2559 13 630 638 3 465 4 940 10 34 082 12 4 281 4 264 6 912 8 904 10 4 34 123 171 46 223 46 402 197 485 267 608 10 由于简单要素模型中各多边形之间没有拓扑约为我国某省行政区划数据层 ,图 5 为该地区土地利用 束关系 ,因此该模型较拓扑模型更易实现叠臵分析算 数据层 。对这两个图层进行叠臵分析 ,得到该省各 () 子的并行化操作 。大规模数据并行化操作的实现将 地 、县的土地利用数据 图 6,提供了各地 、县土地利 进一步提高简单要素模型下叠臵运算的效率 。图 4用情况的统计信息 。 图 4 某省行政区划数据 图 5 某省土地利用类型数据 图 6 某省各地 、县土地利用数据 Fig. 4 A provincial county district data in China Fig. 5 The land use ma p of the study area Fig. 6 The county land use map of the study area 通过对上述算法的简单修改 ,可以实现多边形 参考文献 : 求并 、求差运算 。实现并运算时 ,对多边形点存储的 1 吴信才. 地理信息系统原理与方法 M . 北京 : 电子 工 业 出 版 内存段的搜索应改为反方向 ,即向顺时针方向搜索 ; 社 ,2002 . 160 - 161 .+ 实现差运算时 ,将搜索方向改为顺时针 、逆时针交替 2 董鹏 ,杨崇俊 ,刘冬林 ,等. 基于 R 树的地图叠加分析双重循环 ( ) 算法J . 中国图象图形学报 ,2003 ,8 6:703 - 710 . 进行 。但与交运算不同的是 ,并 、差运算的操作子单 3 李鲁群 ,邓敏 ,刘冰 ,等. GIS 中空间数据叠臵分析的优化算法设元不能简单的视作两两运算 。如图 7 所示 , 现 有的 ( ) ( ) 计J . 山东科技大学学报 自然科学版,2002 ,21 2:62 - 64 .求并算法将两个多边形合并为一个整体 ,而叠臵分析 4 薛胜 ,潘懋 ,王勇. 多边形叠臵分析算法研究 J . 计算机工程与 的结果应该是多边形 1 、2 、3 三部分的集合 ,它们具有 ( ) 应用 ,2003 2:57 - 60 . 5 W EIL ER K ,A T HER TON P. Hidden surface removal using poly2 相同的属性数据 。同样 ,在差运算中 ,两个多边形求 go n area so rtingA . Proceedin gs of t he SI GGRA P H’77 C . New差的结果会参与下次的求差运算 ,即求差运算为一迭 Yo r k :ACM Press ,1977 . 214 - 222 . 代过程 ,因而单纯的两两多边形运算无法满足实际应 VA T T I B R. A generic solutio n to polygo n clippingA . Co mmuni 2 6 ( ) catio ns of t he ACM C . 1992 ,35 1:56 - 63 . 用的需要 。笔者依据上述思路改进了文献 4 中的叠 7 GREIN ER G , HORMANN K. Efficient clipping of arbit rary polygons 臵算法 ,开发了相应的求并 、求差运算算法 ,但基于迭 () A . ACM Transactions on Gra phicsC. 1998 ,17 2:71 - 83 . 刘勇代的时空复杂度 ,算法成果难以满足实际应用的需 8 奎 ,高云 ,黄有群. 一个有效的多边形裁剪算法 J . 软件学 要 。因此有必要研究简单要素模型下多边形叠臵分 ( ) 报 ,2003 ,14 4:845 - 856 . 9 李海姣 ,张维锦. 用 VC 6 实现的任意多边形裁剪算法 J . 计算 析的求差 、求并等操作的高效非迭代算法 。 机应用 ,2005 ,25 :421 - 423 . 10 武志强 ,杨哲海 ,吴官祥. 基于 Visual C 6 平台的多边形裁剪算 ( ) 法实现J . 测绘学院学报 ,2000 ,17 4:301 - 304 . 11 何援军. 计算机图形学 M . 北京 : 机械工业出版社 ,2006 . 158 - 162 . 周培德. 计算几何M . 北京 :清华大学出版社 ,2000 . 49 . 艾廷12 华 ,毋河海. 相邻多边形共享边界的一致化改正 J . 武汉 测绘13 ( ) 科技大学学报 ,2000 ,25 5:426 - 431 . 刘勇奎 ,颜叶 ,石教英. 一个有效的多边形窗口的线裁剪算法14 ( ) J . 计算机学报 ,1999 ,22 11:1209 - 1214 . 图 7 两个相交多边形的并与并集 () 下转第 32 页Fig. 7 The union and the union set of t wo intersection polygons Terra in Interpolat ion Ba sed on Kriging Method BAO Shi - tai ,L IAO Yan - xuan , HU Yue - ming , ZHAO Han - bing ( )I nf or m at ion Col lege of S out h Chi n a A g ricul t u ral U ni versi ty , Gu an gz hou 510640 , Chi n a Abstract : Kriging arit hmetic is an op timum ,linear ,unbiased met hod for estimative value interpolatio n ,which is suitable for terrain in2 terpolatio n . In order to get accurate digital elevatio n model by scat tered sample point s ,t his paper applies ordinary Kriging arit hmetic to elevatio n interpolatio n ,and designs co mplete p rocedure and special p rograms for terrain interpolating and analyzing based o n Matlab sof t ware. The research originated f ro m terrain 3D modeling in Nansha dist rict of Guangzhou ,and sample data are 200 altimet ric point s 2 covering 10 km. As local variable ,t he correlatio n of terrain elevatio n decreases wit h t he increasing of distance ,and sample point s are divided into group s by difference distance. According to formula of experiment variatio n and elevatio n variatio ns ,each group can be cal2 culated and app roached t heory semivariogram of t he sp here model ,index model and Gauss model . Af ter co nt rasting deviatio ns of t hree models ,t he index model was chosen to co mp ute semivariogram mat rix of all sample point s. Kriging vector is made by distance bet ween sample point s wit h a grid to be evaluated. Then ,lagrange modulus for t he grid is calculated. So ,t he z value and deviatio n variance of t he grid are co mp uted. Per hap s most importantly ,t he error variances of Kriging estimates are t he minimum possible of any linear esti2 matio n met hod ,and t hey can be estimated at every locatio n where a Kriging estimate is made. It is co ncluded t hat ordinary Kriging is right for terrain interpolatio n of t he st udy area and t he result by index model is t he best . Key words : ordinary Kriging ; semivariogram ; terrain interpolatio n ; Matlab ()上接第 23 页 Polygon Overlay Analysis Algorithm Using the Simple Data Model 1 1 ,2 1XI E Zho ng, YE Zi, WU Liang ( 1 . Col lege of I nf or m at ion En gi neeri n g , Chi n a U ni versi t y of Geosciences , W u han 430074 ; ) 2 . GIS S of t w a re Resea rch an d A p pl icat ion En gi neeri n g Center of t he M i nist ry of Ed ucat ion , W u han 430074 , Chi n aAbstract : Most of t he vector overlay analysis algorit hms use t he topological data model which request s t he individual layers have pla2 nar enforcement . In order to avoid t he topological relatio n building and imp rove t he efficiency of t he overlay operatio n ,so me GIS plat2 forms bring in t he simple data st ruct ure. This paper discusses t he overlay analysis algorit hm of simple data st ruct ure and takes t he polygo n intersectio n operatio n as an example to int roduce t he algorit hm design and implement . The main p roblem during t he polygo n overlay is t he sp urious polygo ns and‘coastline weave’,which tends to arise when t wo lines are overlaid ,which are act ually slightly dif2 ferent versio ns of t he same line. This paper emp hasizes o n t he solutio n of t he p roblem of t he in - point or out - point serious and t he repeated point s and t he alternative searching of t he polygo n intersectio n. Performance test s show t his algorit hm is more efficient and quick t han t he operatio n based o n t he topological model especially when t he data quantit y goes to large. Key words : simple data model ;overlay analysis ;polygo n intersectio n ()上接第 27 页 Subject ive Qual ity Assessment f or Compressed Remote Sensing Images Ba sed on Fuzzy Comprehensive Eval uat ion Method 1 ,2 1 2 1ZHA I Liang, TAN G Xin - ming,L I Lin, YUAN J ie ( 1 . Chi nese A cadem y of S u rveyi ng an d M ap pi n g , Beiji n g 100039 ; )2 . Col lege of Resou rce an d En v i ron ment S cience , W u han U ni versi t y , W u han 430079 , Chi n a Abstract : Subjective assessment met hods for co mp ressed remote sensing images and t heir classificatio ns are int roduced. Since subjec2 tive assessment has much f uzziness ,a f uzzy co mp rehensive evaluatio n met hod is st udied and applied in assessment for reco nst ructed re2 mote sensing images which are co mp ressed by J P E G2000 standard and imp roved SP IH T algorit hm. The assessment result s show t hat : for bot h co mp ressio n algorit hms of J P E G2000 and imp roved SP IH T , reco nst ructed image qualit y degrades wit h t he increase of co m2 p ressio n ratio ;all reco nst ructed images’quality is bet ter t han‘good’when image co mp ressio n ratio is less t han 4?1 ; wit h t he same co m2 p ressio n ratio ,J P E G2000 performs bet ter t han imp roved SP IH T ; more significant degradatio n of reco nst ructed image quality will be caused when t he terrain type is more co mplex ,or image text ure is richer ,such as in hill or mountain area . Key words : f uzzy co mp rehensive evaluatio n met hod ;J P E G2000 ; SP IH T ; remote sensing image co mp ressio n ; subjective qualit y assess2 ment