一种改进的多边形网格化填充方法-天文地理-热点资讯-野望文存-科技 
    欢迎来到野望文存-科技!
当前位置:野望文存-科技 > 热点资讯 > 天文地理 >  一种改进的多边形网格化填充方法

一种改进的多边形网格化填充方法

发表时间:2020-06-30 09:01:00  来源:野望文存  浏览:次   【】【】【

作 者 信 息

雷 毅,童晓冲,吴翔宇,李 贺

(信息工程大学 地理空间信息学院,河南 郑州 450001)

【摘要】网格数据模型在海量空间数据组织管理中应用广泛,多边形网格化填充方法是其基础和关键技术之一。针对现有方法的网格递归剖分规则不合理和限定条件下多边形网格化填充结果的精度较低等问题,提出一种改进的多边形网格化填充方法。该方法给出一种多边形的多尺度网格化填充模型,以此为基础优化了多边形网格化填充算法,并提供一种多边形网格化填充结果的精度评价指标。实验表明:限定网格数量条件下,相比Google S2采用的多边形网格化填充方法,本文方法的多边形网格化填充结果精度显著提高,有利于提升基于网格数据模型的空间查询精度。

【关键词】多边形;多尺度;网格化填充;综合权值

【中图分类号】P283 【文献标识码】A 【文章编号】1672-1586(2020)02-0075-06

引文格式:雷 毅,童晓冲,吴翔宇,等. 一种改进的多边形网格化填充方法[J].地理信息世界,2020,27(2):75-80.


正文

0 引 言

在海量空间数据的组织与管理中,传统空间数据模型已经无法满足应用需求,基于网格模型的空间数据组织与管理方法为其提供了一种有效途径。在利用网格模型来组织和管理空间数据时,首先要将空间数据进行网格化填充,即建立网格与数据的空间关联;其次在基于网格编码索引的空间查询过程中,仍然需要将多边形查询区域进行网格化填充,然后利用网格编码查询方法来实现查询操作。在实现空间数据的网格化填充时,填充结果中的网格数量和网格尺度,制约着空间数据的网格化填充结果精度(网格覆盖范围与空间数据覆盖范围的接近程度),影响着数据索引与查询的效率、精度等。由此可见,空间数据的网格化填充方法是网格数据模型的基础和关键技术之一。

空间数据类型主要分为:点、线、面和体。点的网格化只需进行坐标转换即可,较为简单;线的网格化算法也较为成熟,如基于直线DDA算法的网格化方法;面的网格化填充则是空间数据处理的难点,且其通常是体的网格化填充的基础。目前,多边形网格化填充方法主要分为两类。一是采用特定层级的单尺度网格实现多边形的网格化填充,然后将单尺度网格化填充结果进行聚合,该方法适用于限定网格层级条件下的多边形网格化填充。如宋树华等采用行扫描算法和剖分面片聚合算法,来实现多边形的多尺度网格化填充,无法完成限定网格数量条件下的多边形网格化填充。二是基于网格递归剖分的方法,该方法适用于限定网格层级或数量条件下的多边形网格化填充。如金安等依据多边形与网格空间范围的拓扑关系,来实现在限定网格递归剖分次数条件下,多边形的多尺度网格化填充;祝琳莹等采用“过滤”和“精炼”两个步骤,来实现多边形的递归剖分,两者的网格剖分顺序均是以其层级作为参考指标,且只能限制网格递归剖分的层级总数。Google S2网格模型采用的多边形网格化填充方法,同时考虑了网格层级及其子单元与多边形之间的拓扑关系,来确定待细化剖分网格的优先级,实现了限定网格层级和数量条件下的多边形网格化填充。

综上可知,现有方法均采用多尺度网格来实现多边形填充,从而以较少数量的网格来更精确描述多边形区域,并针对不同的应用场景发挥了较好作用。但是现有方法均存在一定局限性,特别是在网格数量受限的条件下,多边形网格化填充结果精度不够好,使得基于网格模型的空间查询结果精度较低。主要原因在于:现有方法缺少多边形的多尺度网格化填充模型,使得待细化剖分网格的优先级规则考虑不全面;且缺少评价填充结果精度的评价指标,不利于多边形网格化填充算法的优化。针对以上问题,本文基于二维空间多尺度网格模型,提出并优化一种多边形的多尺度网格化填充模型、多边形的多尺度网格化填充算法,有效提高了限定网格数量条件下的多边形网格化填充结果的精度。

1 网格模型与编码方法

本文研究的重点在于多边形的多尺度网格化填充方法,该方法的探索与实现需以多尺度网格模型为基础。目前在广泛使用的空间网格剖分模型有GeoSOT、Geohash及其变种模型等,这些方法均以递归剖分网格为基础,将空间递归剖分成一系列的子单元网格空间,并采用空间填充曲线(如Z曲线和Hilbert曲线)对网格进行编码。

为统一研究基础,便于探索多尺度网格空间下的多边形网格化方法,本文将采用一种基于跨层级Z曲线的多尺度网格整数编码模型。该编码模型采用m比特的无符号整数对多尺度网格的空间位置进行统一标识,网格层级总数为m/2,当m取值为6时的编码模型与方法如图1所示。在本文实验中m取值为64,设定最大层级(第31级)的网格尺度为1cm×1cm,则其第0级的网格尺度为231cm×231cm,约为21 474.8km×21 474.8km。

1 基于跨层级Z曲线的多尺度网格模型与编码方法

Fig.1 Multi-scale grid model and coding method based on cross-level Z-curve

相比Geohash等网格模型,本文所采用的网格模型具有以下优势和特点:①网格编码为整数,坐标与编码转换运算复杂度低,且编码计算以位操作为基础,计算效率高。②如图1所示,同一区域的相邻层级网格不仅在空间上存在递归关系,而且网格编码之间也存在递归关系,使得空间填充曲线具有更好的连续性,有利于提高多尺度编码计算效率。综上,本文采用上述网格模型与编码方法,用来研究多边形的多尺度网格化填充方法。

2 多边形的多尺度网格化填充方法

2.1 多尺度网格化填充模型

在基于网格数据模型的数据组织和索引中,用于描述空间数据的网格数量是影响其效率的关键。网格数量的减少,可使得数据组织和索引效率提高,但会造成基于网格数据模型的空间查询精度降低。因此,在限定网格数量条件下,提高多边形网格化填充结果的精度,可保证在不降低数据组织和索引效率的前提下,提高空间查询结果的精度。

构建多边形的多尺度网格化填充模型,旨在探索多边形网格化填充的最优方案,为限定条件下的多尺度网格化填充算法设计提供参考依据,从而提高多边形网格化填充结果的精度。为实现上述目标,利用多尺度网格对多边形进行填充,应遵循以下规则:①网格化填充结果满足限定条件,即网格化填充结果中网格的层级范围、数量上限,满足相关应用需求。②网格化填充结果中网格的空间覆盖范围对多边形完整覆盖,即覆盖可以有冗余(如图2中“冗余”区域所示),但不能遗漏多边形所在的任何空间区域。③在满足限定条件下,网格化填充结果的空间覆盖冗余应当尽可能的小,网格化填充结果中的网格数量尽可能的少,从而实现用少量多尺度网格来实现多边形的高精度填充。

该模型主要思路是:将网格的权值作为评价指标,计算多边形对应的网格化填充结果的综合权值,且考虑网格化填充结果需要满足的限定条件,通过权值的优化来实现多边形填充的优化。其具体描述如下:

假定S为多边形,网格化填充结果GS限定的网格层级范围为[Lmin,Lmax],其中LminLmax;限定的网格数量上限为Amax;如图2所示,多边形在每一层级网格化填充的单一尺度网格集合为Gii∈[Lmin,Lmax],其对应的数量为Ai;设Lmax层级网格的权值为λ,则第i层级网格的权值为:

以上述每个层级的网格化填充结果为基础,计算多边形的多尺度网格化填充结果的综合权值如下:

式(5)表示网格化填充结果中网格的空间覆盖范围对多边形完整覆盖。其中,CG表示网格化填充结果GS中多尺度网格集合所覆盖的空间范围,表示Gi中属于GS网格的空间覆盖范围,CS表示多边形S覆盖的空间范围。

2 各层级下多边形的单尺度网格化填充结果

Fig.2 Results of single-scale grid fifilling of polygons 

根据上述模型原理,多边形网格化填充的最优化,可以将Φmin的求解作为优化目标。因为,在满足限定条件下Φ值越小,CG/Cs的值越接近于1,多边形的网格化填充结果的精度越高。此外,CG/Cs的值可作为网格化填充结果GS的精度评价指标,应用于后文实验结果的对比分析中。

依据用户输入的限定条件,实现Φ值的最小化可分为3种情况:

1)仅限定层级范围时,无需考虑数量上限,实现Φ值最小化的方法较为成熟,其主要思路为:首先将多边形SLmax层级网格填充,然后将该单尺度填充结果进行多尺度聚合来得到GS,聚合时GS中的网格层级数值不得小于Lmin,最终实现Φ值的最小化。

2)仅限定数量上限时,无需要考虑层级范围,实现Φ值最小化的方法目前仍需要改进,其主要思路是采用从低层级向高层级的多尺度递归剖分方法。首先用1~4个网格将多边形覆盖,按照一定规则赋予GS中每个网格以优先级,然后按照优先级进行不断的细化剖分,直至GS达到数量上限。

3)同时限定层级范围和数量上限时,实现Φ值最小化的方法以第2种情况为基础,在细化剖分的过程中确保网格层级属于[Lmin,Lmax]即可。

综上所述,本文将重点研究限定条件下的多尺度网格化填充算法。以模型中Φ值的最小化原理为基础,结合现有方法的网格递归剖分思路,下文提出一种多边形的多尺度网格化填充算法,并通过实验与现有方法进行对比分析。

2.2 多尺度网格化填充算法

该算法的主要思路是:以上述模型为基础,用于填充多边形的多尺度网格集合,依据其优先级顺序进行逐层级细化剖分,直至满足相关限定条件。在实现多边形的多尺度网格化填充过程中,用于填充多边形的网格集合分为两类:一是结果网格集合(Result-Grid Set,RGS),表示不需要进行细化剖分的网格集合,且其网格层级满足限定的层级范围;二是候选网格集合(Candidate-Grid Set,CGS),表示能够进行细化剖分的网格集合,该集合中的网格通过赋予优先级来决定细化剖分的顺序(优先级高的网格,优先被细化剖分)。如图3所示,II、IV类网格属于RGS,I、III类网格属于CGS,V类网格表示与目标相离(此类网格在细化剖分时被剔除),则多边形网格化填充结果GS=RGSCGS。其中,III网格与IV虽然均和目标相交,但两者的区别在于:IV类网格的以达到限定条件的最高层级Lmax,不需要再进行细化剖分,而III类网格可作为候选网格继续剖分。

3 依据网格与多边形拓扑关系划分的网格类型

Fig.3 Grid types defifined by topological relationships

其中,候选网格集合中的优先级计算的基本依据是:候选网格与多边形之间存在的冗余(如图2中“冗余”区域所示)越大,候选网格的优先级越高。以图3中候选网格为例,由公式(2)可计算区域内网格化填充结果的综合权值,该值即是冗余的量化描述。候选网格区域内网格化填充结果的综合权值越小,表示冗余越大,候选网格的优先级越高,那么示例中网格优先于进行细化剖分。综上,候选网格的优先级可按照其优先级数值(PCG)由小至大排序,PCG的值越小,优先级越高。PCG的计算以本文提出的填充模型为基础,其具体表达式为:

式中,α表示某候选网格CG进行一次细化剖分时的总层数,通常取值为1,2,3,…;l表示CG的层级数值;n1n2n3n4n5分别表示CG中含有I,II,III,IV,V网格的数量。

基于上述理论基础,限定条件下多边形的多尺度网格化填充算法的主要步骤如下:

1)以Lmin层级网格对多边形S进行网格化填充,得到网格化填充结果GLmin,将其中的网格分类存入RGSCGS,设RGSCGS两个集合中的网格总数为Sum

2)若SumAmax,转至步骤5),否则转至步骤3)。

3)取出CGS中优先级最高的候选网格(CGtop)并进行细化剖分,将候选网格子单元中的I、III类网格存入CGS,II、IV类网格存入RGS

4)重新计算Sum,转至步骤 2)。

5)得到多边形的多尺度网格化填充结果GS=RGSCGS

2.3 对比与分析

根据前文分析可知,S2采用的多边形网格化填充方法,是现有方法中较为优异的。在该方法中,候选网格CG的优先级计算考虑3个因素:候选网格所在层级、候选网格子单元与多边形的相交数量、候选网格子单元被多边形完全容纳的数量。S2中计算候选网格优先级数值(PCG)如(7)式所示,该值越小,候选网格的优先级越高。

式中,ln2n3n4的含义与(6)式中相同,S2方法中候选网格细化剖分的总层数α为1。与S2采用的方法相比,本文提出的多尺度网格化填充方法存在以下优势:

1)具有多尺度网格化填充模型基础。利用该模型可计算多边形对应的网格化填充结果的综合权值,通过综合权值的最小化来探索多边形网格化填充的最优方案。此外,该模型给出一种多边形网格化填充结果精度评价方法,用于评估和分析多尺度网格化填充算法,从而指导算法的不断优化。

2)候选网格优先级计算考虑更加全面。根据公式(6)和公式(7)计算表1中4个候选网格的PCGPCG,若依据PCG的值,候选网格的优先级顺序为: ;若依据P CG的值,候选网格的优先级顺序为:。将上述排序结果对比分析可知:候选网格PCG值相同,表明S2方法无法区分这两种网格的优先级顺序,而本文方法解决了此问题;对于类型候选网格,依据PCG值的排序显然是不合理的,因为该类型网格被细化剖分后仍然为一个网格,应当最优先被细化剖分。综上,本文方法较好地解决了PCG值计算的不合理之处,使得候选网格优先级计算更加精确。

1 候选网格的优先级数值对比

Tab.1 Priorites of candidate grids

3 实验与分析

本文提出的多尺度网格化填充方法,主要目的是:在限定网格数量条件下,提高多边形网格化填充结果的精度。为验证本文方法的有效性及优势,本实验将S2采用的多边形网格化填充方法作为参照方法,与本文方法对比多边形网格化填充结果的精度。其中,将公式(6)中α取值为1,以保证两种方法对候选网格细化剖分总层数相同。

本实验中测试机器配置如下:Intel(R) Core(TM) i7-7700HQ CPU@2.80 GHz,16 GB RAM,240 GB SSD,Windows10;算法实现与测试的环境为:Microsoft Visual Studio 2013,x64,Release,C++。

空间数据中的面类数据主要为简单矢量多边形数据,本实验以此为参考来模拟生成多种矢量多边形。在范围为10 000 km×10 000 km的二维平面空间内,随机生成不规则的三边形、六边形、十二边形、十五边形和十八边形各1万个,共6组多边形实验数据,用于模拟不同区域、不同大小的矢量多边形数据。

实验的主要步骤如下:以本文采用的网格模型为基础,分别采用本文方法和参照方法对每一组多边形进行网格化填充,其中限定条件(网格数量上限)Amax分别设置为100,200,300,…,2 000,每一组数据共进行10次对比实验;记录每组数据实验的平均耗时,以及每次实验的多边形网格化填充结果,并利用公式(5)来计算每一组数据的网格化填充结果精度指标Ratio=CG/Cs。精度指标的统计结果如图4所示,其中N表示多边形的边数,横坐标的单位为100。

4 网格化填充结果的精度统计

Fig.4 Statistics of the accuracy of grid fifilling approaches

根据图4统计结果分析可知:无论哪种方法,RatioAmax成反比关系,且随着Amax值的增大,Ratio值不断减小,趋近于1;在这种情况下,多边形的多尺度网格化填充结果的空间覆盖范围,越来越接近多边形的空间覆盖范围,即网格化填充结果对多边形的描述越来越细致。

此外,在相同的限制条件下,本文方法的精度指标明显优于参照方法,两者的精度指标和效率对比见表2。其中,R表示本文方法相对于参照方法的精度指标提升比率,R=(本文方法精度指标-参照方精度指标)/参照方法精度指标;T1:T2表示对于同一组数据的网格化填充结果生成效率对比,该值为本文方法耗时:参照方法耗时。

2 网格化填充结果的精度和生成效率对比

Tab.2 Comparison of the accuracy and generation effiffifficiency of grid fifilling approaches

由表2分析可知:①与参照方法相比,在处理相同的数据时,本文方法的效率上略有提升;②当Amax值为100时,R值大于40%;当Amax值为200~400时,R值大于20%;故在用少量网格对多边形填充时,本文方法的精度指标提升明显;③且随着Amax的不断增大,本文方法的精度指标仍有一定提升,验证了本文方法的有效性。综上,本文方法具有较大优势,有利于提高基于网格数据模型的空间查询结果精度,其主要归功于多边形的多尺度网格化填充模型。该模型有助于更加准确地计算待细化剖分网格的优先级,从而使得在相同限定条件下,多边形与其网格化填充结果之间存在的“冗余”更小。

4 结束语

本文提出一种多边形的多尺度网格化填充模型与优化算法,通过网格化填充结果的综合权值的优化来实现多边形网格化填充的优化,并改进了网格细化剖分的优先级规则。与参照方法相比,本文方法的优势在于:模型为多边形网格化填充算法提供了重要的理论依据,用于指导算法的优化;候选网格的优先级顺序计算更加合理,使得在相同网格数量限制条件下,多边形网格化填充结果精度显著提高,有利于在保证空间数据组织和索引效率的前提下,提高空间数据的查询精度。此外,本文方法不仅适用于四边形网格模型,还适用于三边形、六边形等类型的网格模型,为其提供重要的技术基础。

本期回顾

时空大数据与新型城镇化研究

· 

· 

· 

· 

· 

· 

· 

· 

· 

理论研究

· 

· 

· 

邮箱变更声

·

网站开通公告

·

诚聘特约审稿专家

·

专题组稿

·

责任编辑:蔡学森