图 1 邻近边间投影和多边形间的邻近度
2.2 "凸包演化 " 算法的基本步骤 1 ) 分别将待合并的两多边形的顶点通过去重
复点 、调整坐标串为同时针方向 、建立凸包 、 坐标排 序 ( 按 : 或 ; 坐标值 )、 分析每个顶点的凸凹特征 等操作表示为如下数据结构中的顶点数组 :
<=>ede? @<ABC< <DEFeA<eG H in< in< mIiJDK 88 顶点 JD 88 顶点所属多边形 JD 88 是否已被使用 mIiPLM=ELnJDK
0
引言
多边形合并是计算几何中研究比较多的一个
1
自动综合中的多边形合并
在数字地图生产中 , 不论是采用手工交互编绘
方面 。多边形形态复杂 ,合并时涉及到点线关系 、 点 面关系 、 线线关系 、 线面关系及面面关系的分析与 处理 ,因而开发一种好的多边形合并算法是具有挑 战性的工作 。 多边形合并在视觉直观看来较容易解 决 , 根据格式塔心理学原理 , 通过人的视觉感知能 积极组织并获取图形的结构化信息 , 能根据待合并 的多边形各部分之间的相近 、 相似或连续等特征很 快得到一个 " 好的格式塔 ", 即好的多边形合并结果 图形 。 但通过计算机来解决多边形合并 ,要分析多 边形之间的邻近边 、 结合部的凸凹性 , 多边形边之 间的方位关系和连续性等 , 根据分析结果确定合并 方案 ,需要通过计算几何的相关算法经过大量运算 才能得到 。 多边形合并算法的关键也在于如何获取 多边形的形态特征和它们之间的各种空间关系 , 本 文在这方面作了一些实验和探索 , 实现了一个较好 的有实用价值的多边形合并算法 。
A 的所有顶点到 B 的最小距离 D1,B 的所有顶点 到 A 的最小距离 D2, 多边形间的距离为 min (D1, D2)。 4 ) 多边形间邻近边的投影长度 : 构成多边形
邻近边的条件是多边形两边之间端点到相对边距 离的最大值不大于规定的距离尺度 ( 本文考虑为地 图上符号间的距离尺度 ), 且两边的夹角在许可的 范 围 之 内 ( 如 图 1- 甲 中 的 边 de 和 边 mn 为 邻 近 边 )。 两边中一条边的投影长度指这条边在邻近边
O5P
,算 法 相 对 简 单,但 合 并 得 到 的 多 边 形 的 形 态 不
很理想 。 基于 NeGaunay 三角网的多边形合并 , 主要 是利用三角网确定多边形顶点 、 边之间的空间关 系 ,由 于 构 网 算 法 相 对 复 杂,本 文 试 图 从 计 算 几
.1‘.
测
绘
工
程 即线段 mv 的长度 。
合并结果如图 . 所示 。 要注意的是 ,上述步骤中多个步骤都是可迭代 的 , 迭代条件视具体要求而适当调整 。 在自动综合
图 两多边形邻近部位的初步处理
中图形的尺度是很重要的因素 ,其大小将直接影响 多边形的细节特征 。 如图 . 中的合并结果就忽略了 顶点 $%+. 、$%+( 、$%+0 之间的细节 , 这个结果可 能在制图综合中是一种较优选择 。
) 在合并的凸包两相邻不同多边形顶点之间 插入离这两顶点连线距离较近的多边形凸顶点 , 可 获取较合理的两多边形邻近部位的初步形态 ( 如图 所示 )。 此时数组中的顶点序列变为# $%+%,$%&
2,$%& ,$2&2 ,$2& ,$2&’,$2&(,$%&,,$%&%-,
图 . 多边形的最终合并结果
2.1 算法相关定义
为了便于后面算法的描述和理解 , 将本文中几 个自定义的概念予以集中解释 。
BNNL mIOJ@P@edK
BNNL mIOJ@BBME=K88QRPS 为凸包上顶点 TUALVS 则不是 BNNL mIOJ@LLCDMBBME=K 88QRPS 则 为 多 边 形 局 部 凸 顶
收稿日期 :2005-04-05 项目来源 : 国家自然科学基金资助项目 (404R1115 ) 作者简介 : 王辉连 >1QR1*? , 男 , 信息工程大学测绘学院硕士研究生 。
还是自动综合 , 都涉及较多的面状目标合并的操 作 ,特别是在大比例尺地图生产时 。 植被 、水域的合 并在某些地区的地图生产中可能会比较多 , 但更多 的是居民地建筑物或街区的合并 。 不同地物的面合 并各有其特点和要求 , 传统数字地图编绘较多地依 赖制图员的经验 ,面状地物合并的多边形形态也取 决于视觉综合的结果 , 通过重新采集边线数据得到 合并后的多边形数据 。 由于自动综合的需要 , 关于 多边形合并的方法研究也较多 , 其中比较有代表性 的是利 用 NeGaunay 三 角 网 进 行 合 并 O1*3P, 合 并 效 果 不 错 ; 有 基 于 扫 描 线 技 术 的 多 边 形 合 并 O4P, 主 要 用 于处理相交多边形的合并 ;有基于栅格数据的合并
L2 , 则多边形 P1 和 P2 之间的邻近度可表示为 N = (L1!C18C2 9 L2!C28C1 )8 (C19C2)。 图 1-丙中 A 、B 两个多边形的邻近度比图 1- 乙中的邻近度要
大 , 可见邻近度不仅反映了多边形间的距离邻近 , 也反映了方位邻近关系 。
a e m q p ! v o ! ! b c d n B B A A
形顶点之间的形态 ,这对合并的多边形形态是否合 理起重要作用 , 就是在这两顶点之间是否插入边与 对应多边形的交点或用交点替换某一顶点 。 这一操 作的判断条件要视多边形合并的形态要求而定 , 如
图 2 多边形凸包的合并
街区合并需突出其直角化特征 ,而植被面的合并则 可能将面积改变量大小作为重要参考 。 具体计算涉 及距离 、 角度 、 面积 、 转折方向等 , 得到两多边形的
2
"凸包演化 "多边形合并算法
多边形合并的难点应在获取待合并的两多边
形之间的相关特征上 。 所谓相关特征 , 即两多边形 之间的距离 、 邻近边的方向和投影关系 、 点到多边 形的距离 、 轮廓局部的凸凹等特征 。 有了这些信息 , 才能对相应轮廓点做出取舍 , 得到合理的新轮廓 点 。 笔者曾尝试仅通过多边形之间的边边关系和点 边关系去描述多边形间的相关特征 , 并在此基础上 进行多边形合并 ,实验表明此方法在轮廓点的顺序 判断和生成新的轮廓点序列方面有所不足 。 由于在 计算机内部多边形表现为一个序列化的坐标串 , 串 行化和顺序既是其数据上的特点 , 也是一种空间结 构特征 , 多边形的合并必须基于此特征进行 ; 而且 从数据的角度看 ,两多边形合并就是将两个有序坐 标串打散 , 再形成一个新坐标串的过程 , 是对于点 集的分析处理 。 凸包作为一个点集的最小凸多边 形 , 既是其空间分布范围的边界 , 也是其外轮廓的 近似 ,且有很好的空间顺序特征 。 因此 , 本文算法选 择了基于凸包通过 " 逐步求精 " 的方法来得到合并 后的新多边形 , 为体现这一特点 , 将算法命名为 " 凸 包演化 "多边形合并算法 。
边 ,UALVS 则顶Fra Baidu bibliotek后为短边
BNNL mIOJ@CXDADC<eAK 88 是否为多边形的特征点 dLBOMe dLBOMe mId:K 88G 坐标 mId;K 88= 坐标
2) 点到多边形的距离 : 点到多边形各边的最
小距离 。 ) 多边形间的距离 : 对于两多边形 A 和 B , 求
Y Z[VIFeA<eGK 88 用于多边形合并的顶点结构 <=>ede? CAAAD= \Z[VIFeA<eGT Z[VIFeA<eG ] Z[AIFeA<eG AAAD=K 88 多边形顶点数组
第 14 卷
何 [4]出发 , 通过相对简单的几何计算去分析待合并 的多边形之间的空间关系和相关特征 , 得到合理 的 、 能较好地反映地物应有形态特征的多边形合并 结果 。
上的垂直投影长度 , 图 1- 甲中的边 de 的投影长度
5) 多边形间的邻近度 : 如果两多边形 P1,P2
之间的距离在一定尺度范围内 , 多边形的周长分别 为 C1 和 C2,P1 相对 P2 的邻近边的投影长度之和 为 L1 ,P2 相 对 于 P1 的 邻 近 边 的 投 影 长 度 之 和 为
$% &2,$2 & ,$2 &’ ,$2 &( ,$% &%),$% &%%,$% & %2*。 此结果在有些情形下可作为综合的最终合并
结果 。 合并的凸包顶点结构中有其在原多边形顶点 数组中的位置信息 ,这一点对于后续处理很重要 。
图 ’ 插入凸顶点后的多边形合并结果
’ 、$2+. 、$%+/ 被插入数组中 。 () 调整合并的顶点数组中两相邻的不同多边
从上面的顶点数据结构中 , 通过分析得到顶点 的多项属性 , 即已分析了多边形轮廓的基本形状和 空间序列特征 ,而且轮廓中隐含凸包 。 如图 2 所示 , 得到的两多边形顶点数组中的顶点序列如图中编 号 , 以顶点 F1-5 为例 , 其数据结构中的各项值可 能 为 (5,1,UALVS ,UALVS ,QRPS ,UALVS ,QRPS ,
第 14 卷 第 3 期
测 绘 工 程
2005 年 Q 月
10230114302 56 784+19302 :0; <:==302
+,-.14/ 0,.3 SEP./ 2005
用于数字地图自动综合的多边形合并算法
王辉连 1,武 芳 1, 王宝山 2, 邓红艳 1
(1. 信息工程大学 测绘学院 , 河南 郑州 450052 ; 2. 河南理工大学 , 河南 焦作 454000 ) 摘要 : 从计算几何出发 , 实现了能考虑到空间关系和形态要求的一种新的多边形合并算法 -" -- 凸包演化 " 算 法 , 并用于自动综合软件中 , 取得了较好的效果 。 关键词 : 自动制图综合 ; 计算几何 ; 多边形合并 ; 凸包演化 ; 空间关系 ; 多边形相关特征 中图分类号 :P208 文献标识码 : 文章编号 :1006-7949(2005)03-0015-04
112.^, ^_.^)。 2) 建立一个新的顶点数组用来表示合并后的
第
期
王辉连等: 用于数字地图自动综合的多边形合并算法
4%05
多边形 ,首先提取前一步中两多边形顶点数组中的 凸包顶点为一点集 , 在此基础上重新生成一个凸 包 , 将凸包顶点存入数组 , 即为两多边形凸包合并 的结果 ,见图 2 。 此时数组中的顶点序列为#$%&%,
点 T UALVS 则为凹顶点
1) 点到边 ( 线段 ) 的距离 : 过点作 到 线 段 的 垂
线 , 如垂足落在线段上则垂线距离为点到线段的距 离 , 否则计算点到线段两端点的距离 , 取其中较小 的距离为点到线段的距离 。
BNNL mIOJ@ULMMLWedLLnESdEeK 88QRPS 则 顶 点 后 为 长
!"# $%&’()*"+ ,’( $&&(-&$*)’. ’, /’%0&’. $//%)-1 *’ $2*’+$*)3 +$/ &-.-($%)4$*)’.
WAN Hui_lian1, WU Fang1, WAN Bao_shan2, DEN Hong_yan1 (1. Institute of Surveying and Mapping, Information Engineering University, ABengCBou 450052, DBinaE 2. Fenan PoGyteHBniH University, IiaoCuo 454000, DBina) Abstract: It presents a neJ aGgoritBm named KDonveL FuGG EvoGutionK for aggregation of poGygons on tBe Masis of Homputation geometry. It is praHtiHaG in tBe softJare of automatiH map generaGiCation. Key words: automatiH map generaGiCationE Homputation geometryE aggregation of poGygonsE HonveL BuGG evoGutionE spatiaG reGationsBipE reGation HBaraHter MetJeen poGygons
