《快速确定多边形与多边形包含关系的一种新方法》由会员分享，可在线阅读，更多相关《快速确定多边形与多边形包含关系的一种新方法（3页珍藏版）》请在金锄头文库上搜索。
1、快速确定多边形与多边形包含关系的一种新方法彭认灿 ,陈子澎 ,刘国辉(大连舰艇学院 海洋测绘系 ,辽宁 大连 116018)A Ne w Method f or Quickly Determining the Relationship of Polygon in PolygonPENG Ren2can , CHEN Zi2peng , L IU Guo2hui摘要 :在分析常用的多边形嵌套关系生成方法及其存在的不足的基础上 ,提出一种简单易行不借助负面积多边形信息快速确定多边形与多边形包含关系的新方法 。关键词 :多边形 ;包含关系 ; GIS最内层的多边形所包含 。如果负面积多边形不被任何多
2、边形所包含 ,它无任何几何意义 ,将它删除 。 在文献 2中介绍的解决多边形包含问题的步骤为 :1 . 计算所有多边形的面积 。2 . 分别对面积为正的多边形和面积为负的多 边形排序 。3 . 从面 积 为 正 的 多 边 形 中 , 顺 序 取 每 个 多 边形 ,取完为止 。若负面积多边形个数为 0 ,则结束 。4 . 找出该多边形所包含的所有面积为负的多 边形 ,并把这些面积为负的多边形加入到包含它们的多边形中 ,转 3 步骤 。注意 ,由于一个面积为负的多边形只能被一个 多边形包含 ,所以 ,当面积为负的多边形被包含后 ,应去掉该多边形 ,或作一标记 。所以 ,当没有面积为负的多边形时
3、 ,也应停止判断 。在该算法中 ,找出面积为正面积多边形包含的 负面积多边形是关键 ,其基本过程可描述为 :1 . 找出所有比该正面积多边形小的负面积多边形 。2 . 用外接矩形法去掉不可能包含的多边形 ,即 负面积多边形的外接矩形不和该正面积多边形的外接矩形相交或被包含时 ,则不可能为该正面积多边形包含 。3 . 取负面积多边形上的任一点 ,看是否在正面 积多边形内 , 若在内 , 则被包含 ; 若在外 , 则不被包 含 。不难看出 ,上述两种方法实质上是一样的 。分析表明 ,它们只能解决形如图 1 ( a) 的多边形嵌套关一 、 引言多边形与多边形的包含关系 ( 也称为多边形的 嵌套关系1
4、 ) ,是空间拓扑关系的一项重要的内容 , 有着诸多重要的应用 。可以说 ,多边形与多边形包 含关系的正确表示 ,是实现叠置分析 、 要素查询 、 区 域面积计算 、 多边形显示等功能的重要前提 。如在 实施区域面积计算时 ,对于不含 “岛” 多边形 ,只需直 接按辛卜生多边形梯形求面积公式计算即可 ,但对 含 “岛” 多边形 ,则需要扣除其第一级各 “岛” 多边形 (此时也可以将第一级 “岛” 多边形形象地称为 “洞” 多边形) 的面积 ;又如 ,为了实现对含 “岛” 多边形的 正确显示 ,应对其作出主多边形与第一级 “岛” 多边 形之分 ,通常要将其组织成符合 Polypolygon 数据
5、结 构的 形 式 , 以 便 直 接 调 用 Windows API 函 数 Polypolygon ,来正确完成其显示 。其中 ,最直接的应 用就是解决 “岛” 多边形的确定问题2 。二 、 建立多边形嵌套关系常用方法 及其存在的主要问题从技术上看 ,这一问题早就得到了解决 ,而且在 不少 GIS 文献中对此都有所介绍 。但从所能查到的 资料看 ,多数是从实现上作一般性介绍 ,无法找到完 整 、 高效的算法 。比如 ,在文献 1 中 ,关于多边形嵌 套关系的确定 ,它是这样描述的 。首先 ,选取一个负 面积多边形 ,找出面积绝对值比负面积的多边形大 , 且其 MBR ( 多边形的最小外接矩形
6、) 包含负面积多 边形的所有多边形 ;然后 ,判断负面积多边形的内点 在哪些多边形内 ,如果在最内层 ,则负面积多边形被收稿日期 : 2004207208 作者简介 : 彭认灿 (19632) ,男 ,广东台山人 ,教授 ,博士 ,主要从事 GIS 的教学和研究工作 。GIS 相关的文献 ,要么像文献 3那样其方法叙述得不够详细和完整 ,要么像文献 4 那样给出的方法过 于繁琐 ,均不够理想 。限于篇幅 ,在此不一一列举 。为了更加有效地解决上述问题 , 下面给出一种确定利用正面积多边形信息来确定多边形与多边形 包含关系新方法 , 其主要步骤是 :1 . 预处理过程1. 建立每个多边形 ( 仅
7、考虑正面积多边形 , 下 同) 的 MBR ;2. 计算出每个多边形的面积 ( 不扣除其 “岛” 多 边形) ;图 1 两种不同的含 “岛” 多边形3.2 .1.将多边形按面积由小到大排序 。确定多边形包含关系过程取多边形 j (排序后的序号 ,第一次时 j = 1) 的显然 ,图 1 ( b) 所给出的 A 多边形的 “岛” 多边形 是两个共边 “岛” 多边形 B 和 C 的并 , 其负面积多边 形是包含这两个相邻 “岛” 多边形的包络多边形 。因此 , 若按上述两方法 , 则只能得到 A 多边形与两个 共边 “岛” 多边形 B 和 C 的包络多边形的嵌套关系 。 要进一步得到 A 多边形分
8、别与两个 “岛” 多边形 B 和 C 的嵌套关系 , 则必须进一步完善上述两方法 , 如补充找出被 A 多边形包含的组成包络多边形的每一个非 “岛” 多边形 B 和 C ( 即组成包络多边形的 同一层次的并列多边形) 这一步 。这一步对于呈复 杂形态的包络多边形 , 其实现算法也是比较复杂的 。 下面以图 2 为例加以详细说明 。任意一个内点 , 对 MBR 包含该点的后序多边形 ( 即多边形序号 j + 1 , 且其 MBR 包含该点的所有多边 形) , 进一步作点在多边形中的判断 。2. 若该点为某一后序多边形的内点 , 则可判断 该内点所代表的多边形被此后序多边形包含 , 并建 立此两个
9、多边形的包含与被包含关系表 , 转步骤 3 ; 否则 , 若取到最后一个多边形 n , 该点仍不被除自身多边形外的任何一个后序多边形包含 , 则说明该内 点所代表的多边形是一独立多边形 , 记此多边形的 包含多边形为 0 号多边形 , 即制图区域的外部多边 形 。3. 若 j n , 则使 j = j + 1 , 转步骤 1 ; 否则 , 处理 过程结束 。 以图 2 为例 , 多边形数量 n = 6 , 按面积由小到 大排序后的多边形顺 序 为 “1”, d , a , b , c , ; 第 一 次 , j = 1 , 即取 “1” 多边形的任意一个内点 ( 可以按文 献 1 中介绍的方法
10、自动求取) , 由于 d , a 和 b 多边形的 MBR 均不包含该内点 , 所以无需对其作进一步 的判断 ; 而 c 多边形的 MBR 包含该内点 , 应作进一 步的判断 , 得知该内点亦为 c 多边形的内点 , 即表明 c 多边形包含 “1” 多边形 , 将它们的包含与被包含关 系记录到一关系表上 ( 见表 1) ; 由于 j = 1 6 , 故使 j= j + 1 , 即 j = 2 , 取 d 多边形的一个内点 , 尽管 b 多 边形的 MBR 包含该点 , 但经过进一步判断后可知 b 多边形并不包含该点 , 继续判断 , 可知该点也是 多 边形的内点 , 建立起 多边形与 d 多边
11、形的包含与 被包含关系 ; 类似地 , 可建立起 多边形分别与 a ,b , c 多边形的包含与被包含关系 。在完成上述处理 后 , 即可建立起正确反映多边形嵌套关系的关系树 , 如图 3 所示 。图 2 较为复杂的含 “岛” 多边形图 2 中的 和 “1” 多边形 , 其包络多边形与其共边 ,只是弧段方向不同 ( 即前者为顺时针方向 , 后者 为逆时针方向) ; a , b , c 和 d 这四个多边形是属于 同一层次的并列多边形 , 其包络多边形是由多边形 a , b , c 的部分边界组成的 ( 为方便叙述 , 假设该包络多边形叫做 A 多边形 , 由图上的粗线表示) ; 多边 形 “1
12、” 是多边形 c 的 “岛” 多边形 。问题是 , 如何按上 述所补充的处理步骤 , 准确地判断出组成 A 多边形 的每一个非 “岛” 多边形 a , b , c 和 d ? 为了解决这一 问题 , 除了要逐一判断出被 A 多边形包含的多边形集合 a , b , c , d 和 “1” 之外 , 还要判断出其中的各级 “岛” 多边形 ( 即此例中的 “1” 多边形) , 将它们从包络 多边形 A 所包含的多边形集合中删除 , 即最后保留方法 。尤其可贵的是 ,它的原理简单易懂 ,编程实现难度很低 。相信从事 GIS 软件开发和 GIS 教学的人 员均可从中受益 。1d a b c 包含 1包含
13、 a , b , c 和 d被 c 包含被 包含 被 包含 被 包含 被 包含 参考文献 :王 家 耀 . 空 间 信 息 系 统 原 理 M . 北 京 : 科 学 出 版 社 ,2001.胡鹏 , 黄 杏 元 , 华 一 新 . 地 理 信 息 系 统 教 程 M . 武 汉 :武汉大学出版社 ,2002.徐 庆 荣 , 杜 道 生 , 黄伟 , 等 . 计 算 机 地 图 制 图 原 理M . 武汉 :武汉测绘科技大学出版社 ,1993.张 超 ,陈丙咸 ,邬伦 . 地理信息系统 M . 北京 : 高 等教育出版社 ,1995.1234图 3由表 1 生成的多边形嵌套关系树四 、 结束语
14、本文在分析建立多边形嵌套关系的常用方法及(上接第 16 页)今后还有待于针对不同数据源的 SAR 影像数 据 ,通过自适应的方法决定梯度阈值大小 ,提高边缘检测的效果 。and Signal Processing , IEEE , 1993 , V. 5 C . s. l . : s.n. ,1993. 77 280.ZHENGY AO Bai , PEIK UN He . An Improved Ratio Edge Detector for Target Detection in SAR ImagesA . IEEE Int . Conf. Neural Networks and Sign
15、al Processing , 2003 , V. 25参考文献 :郭华东 . 雷达对地观测理论与应用 M .版社 ,2000.2985.C . s. l . : s. n. ,2003. 9826XIE H , PIERCE L E , ULAB Y F T. Statistical Properties ofLogarithmically T ransformed Speckle J . IEEE T rans , on Geoscience and Remote Sensing ,2002 ,40(3) :7212727. G ANUG APATI S S ,MOLONEY C R. A
16、 Ratio Edge Detector for Speckled Images Based on Maximum Strength Edge Prun2 ing A . Proceedings of International Conference on Image Processing , IEEE , 1995 , V. 2 C . s. l . : s. n. , 1995.1652168.张文江 ,等 . 基于小波阈值优化和边缘检测的 SAR 影像 斑点噪声滤除 J . 遥感学报 , 2003 ,7(1) :41246.肖 国 超 , 朱 彩 英 . 雷 达 摄 影 测 量 M . 北 京 :
