线目标空间冲突自动检测方法研究.pdf

第3 5 卷第6 期 中国矿业大学学报 V 0 1 ．3 5N o ．6 2 0 0 6 年11 月J o u r n a lo fC h i n aU n i v e r s i t yo fM i n i n g T e c h n o l o g y N o v ．2 0 0 6 文章编号1 0 0 0 1 9 6 4 2 0 0 6 0 6 0 7 6 7 0 5 线目标空间冲突自动检测方法研究 刘万增1 ’2 ，陈军2 ，邓喀中1 ，赵仁亮2 1 ．中国矿业大学环境与测绘学院，江苏徐州2 2 1 1 1 6 ； 2 ．国家基础地理信息中心，北京1 0 0 0 4 4 摘要基于1 5 万空间数据更新质量检查的实际应用需求，分析了空间冲突的自动检测问题；提 出了基于平面扫描算法的空间冲突检测方法．该方法在平面扫描计算的同时利用四交模型计算 线段间的拓扑关系；并根据线段问的拓扑关系推理线目标阃详细的拓扑关系，将计算出的空间关 系与规则比较进行空间冲突判断．该方法在国家1 5 万空间数据库建库质量检查中应用，减轻 了作业员的劳动强度，提高了数据质量检查的效率． 关键词G I S 数据库更新；空间冲突；平面扫描算法；空间关系计算 中图分类号P2 0 8文献标识码A A u t o m a t i cD e t e c t i o no fS p a t i a lC o n f l i c t sB e t w e e nL i n eO b je c t s L I UW a n z e n 9 1 ”，C H E NJ u n 2 ，D E N GK a z h o n 9 1 ，Z H A OR e n l i a n 9 2 1 ．S c h o o lo fE n v i r o n m e n ta n dS p a t i a lI n f o r m a t i c s ，C h i n aU n i v e r s i t yo fM i n i n g ＆T e c h n o l o g y 。 X u z h o u ，J i a n g s u2 2 1 1 1 6 ，C h i n a ；2 ．N a t i o n a lG e o m a t i c sC e n t e ro fC h i n a ，B e i j i n g1 0 0 0 4 4 。C h i n a A b s t r a c t I no r d e rt om e e tt h eh e a v yd e m a n d si nc h e c k i n gt h ed a t aq u a l i t yo fn a t i o n a ls p a t i a ld a t a b a s ea tt h es c a l eo f1 5 00 0 0 。an o v e lm e t h o df o ra u t o m a t i cd e t e c t i o no ft h es p a t i a lc o n f l i c t s b a s e do nt h ep l a n es w e e pa l g o r i t h mw a sp r o p o s e d ．B yt h i sm e t h o d ，t h et o p o l o g i c a lr e l a t i o n s h i p sb e t w e e nl i n es e g m e n t sw e r ec a l c u l a t e di nt h ep l a n es w e e pp r o c e s s ．A n dt h el i n e - l i n et o p o l o g i c a lr e l a t i o n s h i p sw e r ed e d u c e db a s e do nt h a to f l i n es e g m e n t s ．T h e nt h es p a t i a lc o n f l i c t s w e r ed e t e c t e da c c o r d i n gt ot h el i n e - l i n er e l a t i o n Sa n dd e f i n e dr u l e s ．T h eh i g he f f i c i e n c yo ft h e a l g o r i t h mh a sb e e na p p r o v e db yc h e c k i n gt h es p a t i a ld a t aq u a l i t yo fn a t i o n a ls p a t i a ld a t a b a s e sa t t h es c a l eo f1 5 00 0 0 ． K e yw o r d s G I Ss p a t i a ld a t a b a s eu p d a t i n g ；s p a t i a lc o n f l i c t ；p l a n es w e e pa l g o r i t h m ；c a l c u l a t i o n o fs p a t i a lr e l a t i o n s G I S 数据更新常常改变空间目标的位置、形 状、方向、属性等，造成其间关系不合理，从而产生 空间冲突．例如公路、河流小范围多点相交，河流爬 坡，居民地、公路、等高线入水等．针对空间冲突检 测，文献f l - 1 提出了基于规则发现的空间冲突检测 方法；文献[ 2 4 ] 通过建立空间一致性约束，判断空 间关系是否与语义定义相矛盾来检测冲突．以上研 究从理论上讨论了空间冲突的检测问题，没有给出 具体算法．文献[ 5 ] 针对图形冲突检测提出了利用 栅格探测和地图数据库的检索功能探测冲突的算 法，但效率不高，难以应用于海量矢量数据的检测． A r c G I S9 ．0 提供了部分针对特定类型的拓扑错误 检查功能，而数据库中，空间冲突除与拓扑关系类 型有关外，还取决不同区域局部拓扑关系排列顺序 收稿日期2 0 0 5 一0 9 一0 5 基金项目国家自然科学基金重点项目 4 0 3 3 7 0 5 5 I 国家自然科学基金面上项目 4 0 3 0 1 0 4 2 作者简介刘万增 1 9 7 2 一 ，男，河南省长葛市人，高级工程师，博士研究生，从事空间数据库更新方面的研究 E - m a i l l u w n z s [ s i n a ．c o r nT e l 1 3 5 2 0 5 1 2 0 0 9 万方数据 中国矿业大学学报第3 5 卷 与数量等，因而其难以满足实际的应用需求． 目前，空间冲突发现和处理仍然是制图中自动 化程度最低的方面之一[ 6 - r ] ，特别是复杂线目标间 的空间冲突检测，需要计算其间包括所有局部关系 的详细拓扑关系，计算过程和表达方法都非常复 杂，因而，该类型空间冲突检测还停留在手工阶 段[ 7 ] ．为此，本文以中、小比例尺更新后河流要素与 道路、等高线间空间冲突为例，利用平面扫描算法 空间求交的高效性，提出了基于该算法的线目标间 空间冲突检测方法． 1 线目标间详细拓扑关系的计算 河流与道路、等高线间的空间冲突表现为其间 空间关系的不合理，因而空间冲突检测可以转化为 目标间空间关系的计算[ 8 ] ．狭义的空间关系包括拓 扑、度量、方向等，其中拓扑关系是最基本的空间关 系，其合理与否，决定了目标间空间冲突的存在性． 发生空间冲突的线目标间关系往往非常复杂， 在不同的区域可能存在多个局部的拓扑关系．根据 线线拓扑关系的特点，将线线局部拓扑关系定义为 局部相接、局部交叉、局部叠置3 类．图1 中两线目 标在1 ，2 ，3 ，4 处分别为相接、交叉、部分叠置、交叉 关系．这样，线线拓扑关系可以表示为各个局部拓 扑关系按照一定顺序的组合．检测线线空间冲突， 需要计算线线间详细的拓扑关系．本文基于平面扫 描算法计算线段间的拓扑关系，按照规则推断局部 拓扑关系，将局部拓扑关系组合计算线线详细拓扑 关系，最后将计算出的线线详细拓扑关系与规则匹 配检测空间冲突． 图1 线线局部拓扑关系 F i g ．1 T h el o c a lt o p o l o g i c a lr e l a t i o n s h i p 1 ．1 线段闻拓扑关系计算 拓扑关系具有一定的层次性[ 6 ] ．根据两条线段 是否存在交点，将线段间的拓扑关系分为相离与非 相离两类，对于非相离的线段，根据线段方向是否 相同 或相反 ，又可区分为共线和非共线两类，最 后根据线段端点与端点，端点与内部的关系，进一 步将共线线段区分为部分叠置、包含、相等、端点 相接 共线 ；非共线部分区分为交叉、端点相接 非共线 、内部相接． 根据线段间拓扑关系的层次性，将线段拓扑关 系计算分为3 步1 求交计算；2 方向判断；3 坐 标比较．其中，求交计算是线段拓扑关系计算的基 础．大量线段的求交计算，一般采用平面扫描算 法[ 8 。10 。．在扫描求交过程中，计算线段的坐标方位 角并比较线段端点坐标，按照图2 计算线段间的拓 扑关系． 线段求交计算 石和6 方I 嚣 - 端点相 必 口 6 的两端点 黟 土是． I 包含l 交叉 磊 I 内部相接 图2线段间拓扑关系的计算 F i g ．2 C a l c u l a t et h et o p o l o g i c a lr e l a t i o n s h i p s b e t w e e nl i n es e g m e n t s 通过扫描求交计算生成线段拓扑关系表，相应 地，在数据库中创建一个记录集 r e c o r d s e t ，将具 有相交、相接、相等、部分叠置、包含关系的线段及 其所属线目标的部分属性、拓扑关系记录下来．每 一个交点记录交点号 p l D 、平面坐标 X ，y 、要 素类型1 G B l 、目标标示1 F i d l 、相交线段两端 点坐标 X 0 1 ，y 0 1 ，X 0 2 ，Y 0 2 ，要素类型2 G B 2 、 目标标示2 F i d 2 、相交线段两端点的坐标 X 1 1 ， Y 1 1 ，X 1 2 ，Y 1 2 ，线段拓扑关系 T o p o l o g y 等．对 于线段部分叠置和包含等关系，将和线段内部相交 的端点作为交点，线段重合时将线段两端点作为交 点． 1 ．2基于规则的线目标间拓扑关系的推断 根据两线目标中任一线目标的线段流方向对 具有交关系的线段对进行排序，按以下规则推断线 线局部拓扑关系． 假设线目标A 由线段口1 ，口2 ，口3 ，⋯，口f ’．”，口。 组成，线目标B 由线段b ，，b 。，b 。，⋯，b ∥一，b 。组成． 写成口i ∈A ，b i ∈B i 一1 ，2 ，3 ，⋯，m ；_ 『一1 ，2 ，3 ， ⋯，咒 ．设E n d - M e e t 口f ，b i 。。1 表示线段n i ，b ，相 接于端点e p l ，I n - M e e t n i ，b j i ，1 表示线段a 。，6 ， 内部相接于i p l ．E n d n 。 、E n d b j 表示相接线段 不与接点重合的端点，各线段以接点0 为起点的 方位角分别为口肚E n d a ， 1，风End6，iGO-Enda／ 匝 擎 万方数据 第6 期刘万增等线目标空间冲突自动检测方法研究 风刚。钆，，，将4 个方位角从小到大进行排序，A d j a c e n t 表示两方位角相邻．首先考虑3 种拓扑关 系 1 两线目标整体相离．如果两线目标所有线 段都不相交，则两线目标相离．其规则为 规则1 I fV 口i ∈A ，b i ∈B a n dD i s j o i n t 口。，b i 一T r u et h e nD i s j o i n t A ，B 一T r u e 2 两线目标相等．在空间数据库中，两线目标 相等的情况比较少见，如果一个线目标分属于两个 不同数据层，一般都是采用拷贝的方法来创建，因 翮矿两个线目标相等给出．以下定义如果两个线目 标所有对应线段分别相等，则两线目标相等． 规则2 I fi Ja n d Va ；∈A ，j 6 ，∈B a n dE q u a l n f ，b i 一T r u e a n d Vb j ∈B ，了 口{ ∈Aa n dE q u a l 口，，b i 一T r u e t h e nE q u a l A ， B 一T r u e 3 线目标B 包含线目标A ，只考虑线目标重 合部分线段分别相等的情况．如果线目标A 中的所 有线段，在线目标B 中都有一条线段与其相等，反 之对于线目标B 中的所有线段，并不都能在线目标 A 中找到一条线段与其相等，则线目标B 包含线目 标A ． 规则3 I fi ／7 图4两线目标局部相接的4 种关系 F i g ．4 T h ef o u rt w d e so fl o c a lm e e t i n g b e t w e e nt w ol i n eo b j e c t s 图4 中i ，i i 的判断规则为 规贝07 I f j E n d M e e t 口。，b j 。。l T r u e a n d e p l E n d A o re p l E n d B o r I n M e e t 口i ，b j 。p 1 T r u ea n d i p l E n d A o ri p l E n d B t h e n 了 M e e t A ，B 一T r u e 图4 中i i i ，i v 的判断规则为 规贝Ⅱ8 I fj E n d M e e t 口i ，b i 。。1 一T r u e a n dE n d M e e t 口汁1 ，b 升1 。p 2 一T r u ea n de p l e p 2 o r I n M e e t 口i ，b j i p l T r u ea n d I n M e e t 口f 1 ， b j i p 2 一T r u eo rI n M e e t 口f ，b j 1 i p 2 一T r u e a n d i p l i p 2 a n d A d j a c e n t a o _ E 。d 。 ，1 9 1 0 - E n d a i ， 一4 T r u eo rA d j a c e n t 卢0E n d 6 ”J g 9 - E n d b i ．、 一T r u e t h e n ] M e e t A ，B 一T r u e 由规则1 ，2 ，3 分别可以判断线目标整体问的 相离、相等与包含关系，规则4 ，5 ，6 ，7 ，8 判断出的 是两线目标局部交叉、相接、部分叠置关系，分别用 “C ”，“M ”，“O ”表示．并按照文献[ 1 1 ] 的方法对局 部拓扑关系进行排序，根据两线目标中任一线目标 F i d l 从第一个点到最后一点确定的线段流向D z ] 对每一局部拓扑关系顺次赋以数字标示，再按另一 线目标 F i d 2 的线段流向对各个局部拓扑关系的 万方数据 7 7 0中国矿业大学学报第3 5 卷 标示进行排序．例如对于图1 中两线目标间的拓扑 关系可以表示为字符串R F i d l ，F i d 2 一 1 M 2 C 3 0 4 C ． 2 空间冲突自动检测 目标间的空间关系计算出之后，根据两个空间 目标的属性搜索与其匹配的空间冲突判断规则，再 根据规则遍历表示线线详细拓扑关系的字符串R ， 如发现规则禁止的关系，则将根据其前面数字在图 上对应位置标示出空间冲突．例如，如果一条单线 河流与同一条等高线出现两次以上交叉，则必然存 在河流爬坡现象，检测这种冲突，首先遍历字符串 R ，统计河流与同一条等高线局部交叉“C ”出现的 次数，如果大于等于2 ，则可判断为河流爬坡，并将 字母“C ”前的数字m 表示的第m 个交的位置标示 出来．下面以河流爬坡为例介绍冲突检测过程，假 设计算出的河流与等高线的拓扑关系为R r i v e r l ，c o n t o u r l 一1 C 2 C 3 C ，判断规则表示为 R u l e r i v e r T C 2 ，， c o n t o u r ，r i v e r c l i m b st os l o p 表示如果r i v e r 与c o n t o u r 间交叉 C 的次数 大于2 的值为真 T ，则为“r i v e rc l i m b st os l o p ” 冲突． 将冲突检测过程分为语义匹配、关系匹配、行 为匹配3 步 1 语义匹配．关系R 中的目标类型与规则中 目标类型匹配． R u l e 尹 T C 犯攀延梦巾e f c l t 幽t o 吼o p R 两鸯c c sc 2 关系匹配．规则中定义关系与关系R 中定 义的关系匹配． 1 №呼勐T 耍多r i v e r c l i 劬st os l o p R 两简两油飞 3 行为匹配．将规则中的冲突类型与关系R 中数字标示匹配，标示冲突． 1 眦c9 T 嘤妗耍寥多 R 囟，务礁碱 3 实验与应用 利用V B 6 ．0 M a p O b j e c t 编程实现了上述算 法，可以检测道路掉人双线河、道路与单线河小角 度相交，道路与河流小范围相互盘绕、道路落入湖 泊或水库、等高线落水、河流爬坡、河流偏离谷底线 等空间冲突．图5 为一幅1 5 万地形图局部，包括 更新后水系与未更新等高线两层数据，水系层共有 各等级河流3 3 2 条，等高线层包括首曲线、计曲线 等共15J 6 8 条． b a 中①所标区域放大图 c a 中C D 所标I 墨域放大图 图5检测出的河流与等高线空间冲突 F i g ．5 T h ed e t e c t i n gr e s u l to fs p a t i a lc o n f l i c t 区域①处河流与等高线多次相交，为河流爬坡 区域②一处为等高线小角度穿越双线河，另一处为等高线落水； “▲”为检测出的空间冲区域 在P 4 1 ．7 G ，R A M1 2 8 M 台式机上运行，冲突 检测时间为2 ．5S ，将检测结果与专家判断比较，得 出检测正确率为9 3 ％，分析认为主要是判断规则 定义的不完备性造成的． 我们又对1 2 组数据进行了实验，得出了相交 线段对数量与空间冲突检测效率关系，如表1 所 示．从表1 中可以看出，随着相交线段的数目增加， 空间冲突计算时间变长，二者相关系数为p r ，r 0 ．9 5 47 ，相关性明显；而空间冲突计算总时间与 数据文件大小的相关系数为B ，r 一0 ．5 3 99 ，没有 明显的相关性，这说明线目标间拓扑关系计算的效 率主要取决于两线目标相交线段的数量，与文件大 小没有明显关系． 该方法应用于数据库更新中空间冲突检测，共 检查1 5 万数字地形图3 1 2 幅，其效率与人工检 查相比快3 ～5 倍，特别对一些非常细微，需要多次 放大，人工极难发现的空间冲突，其优势更加明显． 万方数据 第6 期刘万增等线目标空间冲突自动检测方法研究 7 7 1 4 结论 根据国家1 5 万空间数据库建库质量检查所 提出的应用需求，研究了线目标空间冲突自动检测 方法．利用平面扫描空间求交结果计算线目标间详 细空间关系，并与规则比较进行空间冲突判断．由 于该方法只计算相交线目标间的空间关系，计算时 间主要取决于相交线段的数量，大量不相交的线段 不参与空间关系计算，提高了空间冲突检测的效 率．通过在国家1 5 万空间数据库质量检查中的 应用，证明了其正确性和高效性．今后研究的重点 是空间冲突判断规则的自动提取方法． 参考文献 [ 1 ] G A D I S HDA ．I n c o n s i s t e n c yd e t e c t i o na n da d j u s t m e n to fs p a t i a ld a t au s i n gr u l ed i s c o v e r y [ D ] ． G u e l p h U n i v e r s i t yo fG u e l p h ，2 0 0 1 ． [ 2 ] C O C K C R O F TC ．T h ed e s i g na n di m p l e m e n t a t i o no f r e p o s i t o r yf o rt h em a n a g e m e n to fs p a t i a ld a t ai n t e g r i t yc o n s t r a i n t s [ J ] ．G e o i n f o r m a t i c a ，2 0 0 4 ，8 i 4 9 6 9 ． [ 3 ]U B E D AT ，E G E N H O F E RMJ ．T o p o l o g i c a le r r o r c o r r e c t i n gi nG I S [ J ] ．L e c t u r eN o t e si nC o m p u t e r S c i e n c e ，1 9 9 7 ，1 2 6 2 2 8 3 - 2 9 7 ． [ 4 ] S E R V I G N ES ，U B E D AT ，P U R I C E L L IA ，e ta 1 ．A m e t h o d o l o g yf o rs p a t i a lc o n s i s t e n c yi m p r o v e m e n to f g e o g r a p h i cd a t a b a s e s [ J ] ．G e o i n f o r m a t i c a ，2 0 0 0 ，4 1 7 3 4 ． [ 5 ] 刘纪平．地图数据库图形输出中要素关系处理[ J ] ．测 绘学报，1 9 9 4 ，2 3 3 2 2 2 2 2 8 ． L I Uj i p i n g ．D e a l i n gw i t ht h er e l a t i o n so ff e a t u r e s d u r i n go u t p u to fm a p [ J ] ．A c t aG e o d a e t i c ae tC a r t o g r a p h i c aS i n i c a ，1 9 9 4 ，2 3 3 2 2 2 2 2 8 ． [ 6 ] L IZL ，Z H A ORL ，C H E NJ ．Av o r o n o i b a s e ds p a t i a la l g e b r af o rs p a t i a lr e l a t i o n sE J ] ．P r o g r e s si nN a t u r eS c i e n c e ，2 0 0 2 ，1 2 7 5 2 8 - 5 3 6 ． [ 7 ] 陈军，李志林，蒋捷，等．基础地理数据库的持 续更新问题[ J ] ．地理信息世界，2 0 0 4 ，2 5 1 5 ． C H E NJ u n ，L IZ h i - l i n ，j 1 A N GJ i e ，e ta 1 ．K e yi s s u e s o fc o n t i n u o u su p d a t i n go fg e o s p a t i a ld a t a b a s e s [ J ] ． G e o m a t i c sW o r l d ，2 0 0 4 ，2 5 I - 5 ． I s ] P R E P A R A T AFP ，S H A M O SMI ．C o m p u t a t i o n a l g e o m e t r y A ni n t r o d u c t i o n [ M ] ．N e wY o r k S p r i n g e r - V e r l a g ，1 9 8 8 ． [ 9 ] 周培德．计算几何算法分析与设计[ M ] ．北京清华 大学出版社，2 0 0 0 1 3 3 - 1 3 9 ． [ 1 0 ] H U A N GYW ．S y m b o l i ci n t e r s e c td e t e c t i o n A m e t h o df o ri m p r o v i n gs p a t i a li n t e r s e c tj o i n s [ J ] ． G e o i n f o r m a t i c a 。1 9 9 8 ，2 2 1 4 9 1 7 4 ． [ 1 1 ] L I UWZ ，C H E NJ ，Z H A ORL ，e ta 1 ．Ar e f i n e d l i n e l i n es p a t i a lr e l a t i o n s h i pm o d e lf o rs p a t i a lc o n f l i c t d e t e c t i o n [ J ] ．L e c t u r eN o t e si nC o m p u t e rS c i e n c e ， 2 0 0 5 ，3 7 7 0 2 3 9 - 2 4 8 ． [ 1 2 ] C L E M E N T I N IE ，F E L I C EPD ．T o p o l o g i c a li n v a r i a n t sf o rl i n e s [ J ] ．I E E ET r a n s a c t i o n sonK n o w l e d g ea n dD a t aE n g i n e e r i n g ，1 9 9 8 ，1 0 1 3 8 _ 5 4 ． 责任编辑邓群 万方数据