留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

空间划分多因子耦合PDE模型与算法

江海东 张可能

江海东, 张可能. 空间划分多因子耦合PDE模型与算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1060-1065. doi: 10.13203/j.whugis20130747
引用本文: 江海东, 张可能. 空间划分多因子耦合PDE模型与算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1060-1065. doi: 10.13203/j.whugis20130747
JIANG Haidong, ZHANG Keneng. Multi-factor Coupled PDE Model and Algorithm for Spatial Partition[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1060-1065. doi: 10.13203/j.whugis20130747
Citation: JIANG Haidong, ZHANG Keneng. Multi-factor Coupled PDE Model and Algorithm for Spatial Partition[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1060-1065. doi: 10.13203/j.whugis20130747

空间划分多因子耦合PDE模型与算法

doi: 10.13203/j.whugis20130747
基金项目: 

国家自然科学基金 41161072

详细信息
    作者简介:

    江海东, 博士生, 主要从岩土工程信息化及数据处理分析研究。59366197@qq.com

  • 中图分类号: P208;P282

Multi-factor Coupled PDE Model and Algorithm for Spatial Partition

Funds: 

The National Natural Science Foundation of China 41161072

More Information
    Author Bio:

    JIANG Haidong, PhD candidate, specializes in the data processing and analysis of geotechnical engineering information. E-mail: 59366197@qq.com

  • 摘要: 为研究非凸空间离散数据的空间划分,建立了耦合数据集的凸凹性、数据规模、离散度的空间划分的数学模型。利用Laves划分标识[36]对非凸空间离散数据进行有限区域变比例划分,然后通过地形曲面微分单元与数据规模的偏导函数关系,耦合离散度计算空间划分的单元间距和数量。最后通过构建DEM,可视化验证和对比分析发现,耦合模型能够计算出非凸离散空间数据空间划分单元的间距和数量,也能实现不同分辨率的划分单元的无缝拼接;且当试验数据从110组递增至440组时,该模型耗时仅是[44]标识划分和Delaunay的1/10~1/3,且随数据规模成倍增加时耗时基本呈线性增长,收敛性较好,但耗时随离散度增加而增长。
  • 图  1  Laves划分标识——[36]、[44]、[63][1]

    Figure  1.  Visual Figure of Laves Partition Identity——[36]、[44]、[63][1]

    图  2  初始划分

    Figure  2.  Initial Partition

    图  3  不同数据运行结果

    Figure  3.  Visual Diagrams of Different Sets of Data

    图  4  程序运行时间统计图

    Figure  4.  Visual Diagrams of Time Statistic for Program Running

    图  5  不同组数正方形空间划分图

    Figure  5.  Square Spatial Partition for Different Datas

    图  6  不同组数据Delaunay三角剖分图

    Figure  6.  Delaunay Triangulation of Defferent Test Datas Generation

    图  7  Delaunay非单连通边界约束生成非法边界

    Figure  7.  Illegal Boundary of Delaunay on Non-convex Constrained

    图  8  Delaunay非单连通边界生成非法三角网图

    Figure  8.  Illegal Triangulation of Delaunay on Non-simply Connected Constrained

    图  9  Delaunay非凸边界约束产生的非法边界

    Figure  9.  Illegal Boundary of Delaunay on Non-convex Constrained

    图  10  Delaunay非凸边界约束产生的非法三角网

    Figure  10.  Non-convex Boundary Constrained Delaunay Illegal Triangulation

    表  1  离散度与算法耗时关系表

    Table  1.   Relationship of Process Time Between Dispersion and Algorithm

    区域 1 2 3 4 5 6 耗时/ms
    离散度 29.56 36.89 43.51 46.86 54.81 54.56 1 051
    64.48 94.56 96.18 97.52 100.45 107.16 1 757
    83.2 141.27 172.57 183.14 213.06 220.98 3 003
    下载: 导出CSV

    表  2  时间复杂度对比分析表 [14-16]

    Table  2.   Comparative Analysis Table of Time Complexity [14-16]

    模型 算法 时间复杂度
    Voronoi 半平面交 T(n)=O(n2)
    Voronoi 增量构造算法 T(n)=O(n2)
    Voronoi 分治算法 T(n)=O(nlogn)
    Voronoi 减量算法 T(n)=O(nlogn)
    Voronoi 平面扫描算法 T(n)=O(nlogn)
    Delaunay 三角网生长法 T(n)=O(n2)
    Delaunay 逐点插入法 T(n)=O(n2)
    Delaunay 分治算法 T(n)=O(nlogn)
    耦合PDE模型 递归 T(n)=O(nlogn)
    下载: 导出CSV

    表  3  程序耗时对比分析表/ms

    Table  3.   Comparative Analysis Table of Time Program Runs/ms

    划分方法 110组 220组 330组 440组
    耦合划分 1 097 3 278 6 178 12 478
    [44]标识 53 197 33 216 41 494 30 394
    Delaunay 13 109 17 157 22 225 33 302
    下载: 导出CSV

    表  4  非凸集合约束划分效果对比分析表 [16]

    Table  4.   Correlation Analysis Table of Partition Under Non-Convex [16]

    划分方法 非法边界 非法多边形 冗余
    耦合模型 不存在 不存在 不存在
    [44]标识划分 存在 存在 存在
    Delaunay划分 存在 存在 不存在
    下载: 导出CSV
  • [1] 唐中实, 黄俊峰, 尹平, 等, 译.地理信息系统——原理与技术[M].北京:电子工业出版社, 2004

    Tang Zhongshi, Huang Junfeng, Yin Ping, et al. Translation. Principle and Technology of Geographic Information System[M]. Beijing: Publishing House of Electronics Industry, 2004
    [2] Ahuja N. On Approaches to Polygonal Decomposition for Hierarchical Image Representation[J].Computer Vision, Graphics, and Image Processing, 1983, 24(2):200-214 doi:  10.1016/0734-189X(83)90043-9
    [3] Samet H. The Design and Analysis Spatial Data Structures[M]. USA: Addison-Wesley, 1989
    [4] Grunbaum B, Shephard G C. The Eighty-one Types of Isohedral Tilingsin the Plane[J]. Mathematical Proceedings of the Cambridge Philosophical Society, 1977, 82(2):177-196 doi:  10.1017/S0305004100053810
    [5] Bell S B M, Diaz B M, Horlroy F C. The HOR Quadtree:an Optimal Structure Based on a Non-sqare 4-shape[M].//Brooks S R. Mathematics in Remote Sensing. London:Oxford Press, 1989
    [6] Bell S B M, Horlroy F C.Tesseral Amalgamators and Hierarchical Tessellations[J].Image and Vison Computing, 1991, 9:313-328 doi:  10.1016/0262-8856(91)90036-O
    [7] Hutchinson M F, Gallant J C. Digital Elevation Models and Representation of Terrain Shape[M].//Wilson J P, Gallant J C. Terrain Analysis:Prinei Ples and APP lieations. New York:John Wiley & Sons.Ine200. 2000
    [8] 汤国安, 杨昕. ArcGIS地理信息系统空间分析实验教程[M].北京:科学出版社, 2006

    Tang Guoan, Yang Xin. ArcGIS Geographic Information Systems Spatial Analysis Tutorial [M]. Beijing: Science Press, 2006
    [9] 刘永和, 王润怀, 齐永安.一种非凸包边界约束不规则三角网生成算法[J].测绘科学, 2008, 33(3): 79-81 http://www.cnki.com.cn/Article/CJFDTOTAL-CHKD200803027.htm

    Liu Yonghe, Wang Runhuai, Qi Yongan. A Boundary Triangulated Irregular Network of Non-convex Hull Algorithm [J]. Surveying and Mapping Science, 2008, 33(3): 79-81 http://www.cnki.com.cn/Article/CJFDTOTAL-CHKD200803027.htm
    [10] 孙文彬, 刘希亮, 栾晓慧, 等.顾及等高线和凹边界特征的不规则三角网生成方法[J].地理与地理信息科学, 2010, 26(4): 50-53 http://www.cnki.com.cn/Article/CJFDTOTAL-DLGT201004012.htm

    Sun Wenbin, Liu Xiliang, Luan Xiaohui, et al. Contour and Concave Boundary Characteristics into Account Irregular Triangulation Method for Generating [J]. Geography and Geographic Information Science, 2010, 26(4):50-53 http://www.cnki.com.cn/Article/CJFDTOTAL-DLGT201004012.htm
    [11] 周成虎, 欧阳, 马廷.地理格网模型研究进展[J].地理科学进展, 2009, 28(5): 657-662 http://www.cnki.com.cn/Article/CJFDTOTAL-DLKJ200905003.htm

    Zhou Chenghu, Ou Yang, Ma Ting. Research Progress of Geogrid Model [J]. Progress in Geography, 2009, 28(5): 657-662 http://www.cnki.com.cn/Article/CJFDTOTAL-DLKJ200905003.htm
    [12] 刘春, 孙伟伟, 吴杭彬. DEM地形复杂因子的确定及与地形描述精度的关系[J].武汉大学学报信息科学版, 2009, 34 (9): 1 014-1 019 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200909002.htm

    Liu Chun, Sun Weiwei, Wu Hangbin. DEM Topography and Terrain Describes the Accuracy of Determining Factor [J]. Geomatics and Information Science of Wuhan University, 2009, 34 (9): 1 014-1 019 http://www.cnki.com.cn/Article/CJFDTOTAL-WHCH200909002.htm
    [13] 贾敦新, 汤国安, 王春, 等.DEM数据误差与地形描述误差对坡度精度的影响[J].地球信息科学学报, 2009, 11(1):43-49 http://www.cnki.com.cn/Article/CJFDTOTAL-DQXX200901011.htm

    Jia Dunxin, Tang Guoan, Wang Chun, et al. Accuracy of DEM Terrain Representation Error and Data Error on the Slope Effect [J]. Journal of Geo-Information Science, 2009, 11 (1): 43-49 http://www.cnki.com.cn/Article/CJFDTOTAL-DQXX200901011.htm
    [14] 张宏, 温永宁, 刘爱利, 等.地理信息系统算法基础[M].北京:科学出版社, 2006, 172-184

    Zhang Hong, Wen Yongning, Liu Aili, et al.The Base of GIS Algorithm [M]. Beijing: Science Press, 2006, 172-184
    [15] Tasi D, Victor J. Delaunay Triangulations in TIN Creation: An Overview and a Linear-time Algorithm [J]. International Journal of GIS, 1993, 7(6):501-524
    [16] 江海东, 张可能, 陈天伟.空间划分双因子耦合PDE模型与算法[J].沈阳工业大学学报, 2014, 36(4):446-452 http://www.cnki.com.cn/Article/CJFDTOTAL-SYGY201404017.htm

    Jiang Haidong, Zhang Keneng, Chen Tianwei. Coupled PDE Model and Algorithm Based on Two-factor for Spatial Partition[J]. Journal of Shenyang University of Technology, 2014, 36(4):446-452 http://www.cnki.com.cn/Article/CJFDTOTAL-SYGY201404017.htm
  • [1] 徐恩恩, 郭颖, 陈尔学, 李增元, 赵磊, 刘清旺.  基于无人机LiDAR和高空间分辨率卫星遥感数据的区域森林郁闭度估测模型 . 武汉大学学报 ● 信息科学版, 2022, 47(8): 1298-1308. doi: 10.13203/j.whugis20210001
    [2] 姚晓闯, 杨建宇, 李林, 叶思菁, 郧文聚, 朱德海.  云环境下海量空间矢量数据并行划分算法 . 武汉大学学报 ● 信息科学版, 2018, 43(7): 1092-1097. doi: 10.13203/j.whugis20160271
    [3] 陈善学, 郑文静, 张佳佳, 李方伟.  变换域离散度排序的高光谱图像快速压缩算法 . 武汉大学学报 ● 信息科学版, 2016, 41(7): 868-874. doi: 10.13203/j.whugis20140270
    [4] 徐剑波, 肖志峰, 钟林忆, 蔡德楠, 钟德福, 朱晓强.  HJ-1B热红外LST反演及利用偏微分对其误差精度分析 . 武汉大学学报 ● 信息科学版, 2016, 41(11): 1505-1511. doi: 10.13203/j.whugis20140475
    [5] 付仲良, 赵星源, 王楠, 杨元维, 田宗舜, 俞志强.  一种基于流形学习的空间数据划分方法 . 武汉大学学报 ● 信息科学版, 2015, 40(10): 1294-1298,1323. doi: 10.13203/j.whugis20141008
    [6] 夏桂松, 薛楠, 王子锋, 张良培.  复张量场扩散方程及其在PolSAR图像去噪中的应用 . 武汉大学学报 ● 信息科学版, 2015, 40(11): 1533-1538,1556. doi: 10.13203/j.whugis20140630
    [7] 刘涛, 杜清运, 毛海辰.  空间线群目标相似度计算模型研究 . 武汉大学学报 ● 信息科学版, 2012, 37(8): 992-995.
    [8] 高建, 谢伟, 涂志刚, 秦前清.  使用泊松方程插值方法进行遥感影像融合 . 武汉大学学报 ● 信息科学版, 2012, 37(12): 1448-1451.
    [9] 姜卫平, 赵倩, 刘鸿飞, 杨凯.  子网划分在大规模GNSS基准站网数据处理中的应用 . 武汉大学学报 ● 信息科学版, 2011, 36(4): 389-391.
    [10] 王伟, 沈振中.  大坝统计预警模型的改进粒子群耦合方法 . 武汉大学学报 ● 信息科学版, 2009, 34(8): 987-991.
    [11] 闫超德, 白建军, 赵仁亮.  基于Voronoi图的点状目标邻近空间分布测度方法 . 武汉大学学报 ● 信息科学版, 2009, 34(1): 48-51.
    [12] 赵彬彬, 邓敏, 李志林.  GIS空间数据层次表达的方法探讨 . 武汉大学学报 ● 信息科学版, 2009, 34(7): 859-863.
    [13] 韩鹏, 龚健雅, 李志林.  基于信息熵的遥感分类最优空间尺度选择方法 . 武汉大学学报 ● 信息科学版, 2008, 33(7): 676-679.
    [14] 王永杰, 孟令奎, 赵春宇.  基于Hilbert空间排列码的海量空间数据划分算法研究 . 武汉大学学报 ● 信息科学版, 2007, 32(7): 650-653.
    [15] 赵春宇, 孟令奎, 林志勇.  一种面向并行空间数据库的数据划分算法研究 . 武汉大学学报 ● 信息科学版, 2006, 31(11): 962-965.
    [16] 郭庆胜, 闫卫阳, 李圣权.  中心城市空间影响范围的近似性划分 . 武汉大学学报 ● 信息科学版, 2003, 28(5): 596-599.
    [17] 郭俊义, 张飞鹏.  用切贝谢夫配点法消除地球自振常微分方程组在地心处的奇异性 . 武汉大学学报 ● 信息科学版, 1996, 21(4): 320-322,337.
    [18] 林银森, 何平安, 余模智, 林荔.  光学转像变倍微分方程的建立及其应用 . 武汉大学学报 ● 信息科学版, 1996, 21(4): 403-407.
    [19] 晁定波, 边少锋.  超定边值问题的差分法 . 武汉大学学报 ● 信息科学版, 1991, 16(1): 4-12.
    [20] 孔庆炘.  建立质点相对运动微分方程的方法浅析 . 武汉大学学报 ● 信息科学版, 1986, 11(1): 84-89.
  • 加载中
图(10) / 表(4)
计量
  • 文章访问数:  1130
  • HTML全文浏览量:  35
  • PDF下载量:  269
  • 被引次数: 0
出版历程
  • 收稿日期:  2015-11-17
  • 刊出日期:  2016-08-05

空间划分多因子耦合PDE模型与算法

doi: 10.13203/j.whugis20130747
    基金项目:

    国家自然科学基金 41161072

    作者简介:

    江海东, 博士生, 主要从岩土工程信息化及数据处理分析研究。59366197@qq.com

  • 中图分类号: P208;P282

摘要: 为研究非凸空间离散数据的空间划分,建立了耦合数据集的凸凹性、数据规模、离散度的空间划分的数学模型。利用Laves划分标识[36]对非凸空间离散数据进行有限区域变比例划分,然后通过地形曲面微分单元与数据规模的偏导函数关系,耦合离散度计算空间划分的单元间距和数量。最后通过构建DEM,可视化验证和对比分析发现,耦合模型能够计算出非凸离散空间数据空间划分单元的间距和数量,也能实现不同分辨率的划分单元的无缝拼接;且当试验数据从110组递增至440组时,该模型耗时仅是[44]标识划分和Delaunay的1/10~1/3,且随数据规模成倍增加时耗时基本呈线性增长,收敛性较好,但耗时随离散度增加而增长。

English Abstract

江海东, 张可能. 空间划分多因子耦合PDE模型与算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1060-1065. doi: 10.13203/j.whugis20130747
引用本文: 江海东, 张可能. 空间划分多因子耦合PDE模型与算法[J]. 武汉大学学报 ● 信息科学版, 2016, 41(8): 1060-1065. doi: 10.13203/j.whugis20130747
JIANG Haidong, ZHANG Keneng. Multi-factor Coupled PDE Model and Algorithm for Spatial Partition[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1060-1065. doi: 10.13203/j.whugis20130747
Citation: JIANG Haidong, ZHANG Keneng. Multi-factor Coupled PDE Model and Algorithm for Spatial Partition[J]. Geomatics and Information Science of Wuhan University, 2016, 41(8): 1060-1065. doi: 10.13203/j.whugis20130747
    • 空间划分是用不同的空间数据结构描述空间数据的模型[1]。文献[2, 3]归纳了规则空间划分应具有的两种性质,即无限重复且适用任何尺度图像,以及可无限精细分解且可表达成不同等级和层次的任意分辨率的空间要素。文献[4]证明了规则空间中约束为顶点类型相同的划分只存在11种,称为Laves划分,并把正三角形、正方形和正六边形组成的规则划分标识为[63]、[44]、[36]。文献[5, 6]完善了空间划分的其他性质——均匀划分和均匀邻接,其在图像处理和自动制图过程的作用非常重要。而11种Laves划分中具有均匀邻接和均匀方向划分性质只有[44]、[36]。具体如图 1所示。

      图  1  Laves划分标识——[36]、[44]、[63][1]

      Figure 1.  Visual Figure of Laves Partition Identity——[36]、[44]、[63][1]

      空间划分是构建DEM的数据模型,基本属性是单元数量、类型及间距。文献[7]提出了根据坡度中误差确定DEM最佳间距的方法,但忽略了数据规模和边界集合的凸凹性的影响。文献[8]强调“选择合适的单元,单元过大DEM会降低精度,并损失大量地形信息且造成图形失真,单元过小会产生大量数据的冗余和影响地形宏观特征的显示效果”。由此可见,数据密度严重影响地形信息的表达,而现有空间划分方法主要凭主观经验确定划分的间距和数目,造成较大的冗余。文献[9, 10]等在边界约束划分方面取得一定成果,但尚未解决非凸边界问题。文献[11]阐述了地理格网模型研究进展和存在的问题。因此地理空间划分的最重要的约束可归纳为单元间距、大小、类型和边界条件、数据规模、地形起伏程度、投影类型这几项[12, 13],耦合约束条件的模型或算法能够更全面地用数学语言表达地理空间划分。

      综上所述,为了解决非凸边界失真和数据冗余问题,实现空间优化的目标,本文建立了非凸集合条件下基于Laves划分[36]耦合数据规模和离散度的空间划分(partial differential equation,PDE)模型。

    • 空间划分的核心是求解划分单元间距和数量的数学结构。空间划分的影响因子可归纳为数据集和行业应用要求两种,行业要求往往根据需求决定。而对于空间离散数据来说,影响空间划分的主要因素是空间数据规模、离散度以及数据边界的凸凹性,并且这些因子存在耦合关系。但划分过程中并不是每一个划分单元都包含空间离散数据,因此可以通过计算样本数据密度来表达数据规模参数。可用PDE模型表达空间划分单元的间距和数量两个变量的关系。

    • 设地表离散空间数据集合为(xi, yi, zi), 其中x为经度(或横坐标),y为纬度(或纵坐标),z为高程,地形曲面方程为:

      (1)

      曲面方程x方向的投影分量为:

      (2)

      曲面方程y方向的投影分量为:

      (3)

      数据规模是影响空间划分精度的一个重要指标。地形曲面面积的计算方法为:

      (4)

      数据密度数学表达式为:

      (5)

      式中, ρ为数据密度;N为离散数据规模量。

      空间离散数据离散程度的测度指标可用极差来表示,即离散数据的最小投影距离和边界最远点与区域样本中心距之差:

      (6)

      令划分单元最小间距为l,则

      (7)
    • Laves划分标识只有[36]和[44]满足空间划分的无限精细划分、均匀邻接、均匀划分的性质要求。为了兼顾数据离散程度造成划分单元不均匀性和缝隙问题的同时解决区域边界凸凹性问题,选择标识为[36]的Laves划分对空间离散数据进行有限区域变比例划分。有限区域变比例划分是根据离散数据中心点和最远点构建覆盖区并6等分,方可以Laves划分标识[36]作为划分单元,然后将每个子区域的最远点作为划分边界,避免划分数据冗余,并可实现多种分辨率的划分无缝拼接。而Laves划分标识[36]划分单元的分辨率取决于最小间距l,由式(5)、(7)可知,R,所以离散空间数据划分最小间距受离散程度和数据密度耦合制约。因此每个子区域空间划分单元的数量取决于该子区域最远点和离散点最小间距,即该空间间距的极差(离散度)。

      对于平面单元为曲面的笛卡尔坐标系下的投影,则有:

      (8)

      式中, Si为第i区域总面积;Mi为第i区域单元数量(i=1,2, …, 6);ei为第i区域单元面积。

      数据密度因子用曲面方程进一步表达为:

      (9)

      式中, Ni为第i区域样本数据量,即

      (10)

      初始划分单元无限细分,设第i区域划分迭代次数为Ki,划分单元面积设为ei,则有:

      (11)

      迭代次数取整为:

      (12)

      式中,ei为曲面面积微分单元Ei的投影面积:

      (13)

      投影下第i区域数据密度可推导出:

      (14)

      可得:

      (15)

      式中,M为划分单元总数量。

      那么求解划分数量和间距的耦合模型为:

      (16)

      模型中,li为第i区域划分单元最小间距;Ri为第i区域离散度。

    • 求解单元间距和数量的耦合空间划分模型计算方法流程如下。

      1)随机生成WGS84坐标系离散数据;

      2)所有点投影到平面坐标系,求其中最远两点的距离,并以这两点的中心坐标为圆心,以其距离为直径。空间离散点边界样本点集合记为Bn(XN, YN, ZN),Nnn=1, 2, 3…;圆心O的坐标(Ox, Oy)为

      3)将圆等分成6个扇形区域,判断每个样本点归属扇形区域,归类显示(每个区域数目计Ni);

      4)求每个扇形区域距离圆心最远的点和空间距离极差Ri

      5)最远点及其所在扇形区域的边界形成正三角形,初始圆依据离散点的空间位置剖分为6个正三角形,如图 2所示,计算其面积Si。过最远点边界直线方程的计算方法为:①计算过点ABO的直线AB的方程及斜率;②计算直线CFDE相对AB的偏转角度,求直线CFDE斜率及其直线方程;③计算过COD区域与EOF区域最远点平行直线AB的方程,同理可求得其他区域过最远点的边界方程。

      图  2  初始划分

      Figure 2.  Initial Partition

      6)每个初始正三角形均匀划分4等分。

      7)根据式(16)建立递归划分算法,划分单元最小间距为递归终止条件。

      8)输出划分总数目。

    • 可视化环境:CPU为AMD A8-4500M,程序语言为Java Script,Google Chrome浏览器,数据规模包括110~440组WGS84数据。划分效果如图 3所示。

      图  3  不同数据运行结果

      Figure 3.  Visual Diagrams of Different Sets of Data

      图 3图 4可知,本文模型能够计算每个区域的划分数量和间距,非凸空间离散数据条件下在不同分辨率的划分单元中实现无缝拼接,而且当数据规模成倍增长时,该模型计算方法的耗时基本呈线性增长,表明了算法收敛性较好。

      图  4  程序运行时间统计图

      Figure 4.  Visual Diagrams of Time Statistic for Program Running

    • 计算样本数据的离散性影响算法的时间复杂度,通过测试相同数据规模(110组WGS84数据)来分析离散度对算法耗时的影响,测试结果如表 1

      表 1  离散度与算法耗时关系表

      Table 1.  Relationship of Process Time Between Dispersion and Algorithm

      区域 1 2 3 4 5 6 耗时/ms
      离散度 29.56 36.89 43.51 46.86 54.81 54.56 1 051
      64.48 94.56 96.18 97.52 100.45 107.16 1 757
      83.2 141.27 172.57 183.14 213.06 220.98 3 003

      测试结果表明,相同数据规模下算法耗时随着离散度增加而增加。

    • 空间划分是GIS构建DEM的数据模型,通过耦合模型与Laves[44]标识划分和Delaunay构建DEM来对比分析其在非凸集合条件下算法的耗时、划分效果以及数据冗余状况,以评价各方法的优缺点。

    • Laves[44]划分方法也采用110~440组WGS84数据,测试环境与耦合模型相同。

      图 5显示除数据边界包围区域,边界与划分边界之间出现较大的数据冗余区域。

      图  5  不同组数正方形空间划分图

      Figure 5.  Square Spatial Partition for Different Datas

    • Delaunay三角网测试环境与耦合模型相同,可视化结果如图 6所示。

      图  6  不同组数据Delaunay三角剖分图

      Figure 6.  Delaunay Triangulation of Defferent Test Datas Generation

    • 衡量算法优劣常用时间复杂性T(n)来度量,耦合PDE空间划分模型运用循环算法和递归算法,其时间复杂度最小为T(n)=O(logn), 最坏为T(n)=O(nlogn)。本方法和变比例划分的Voronoi和Delaunay划分算法的间复杂度的对比分析见表 2

      表 2  时间复杂度对比分析表 [14-16]

      Table 2.  Comparative Analysis Table of Time Complexity [14-16]

      模型 算法 时间复杂度
      Voronoi 半平面交 T(n)=O(n2)
      Voronoi 增量构造算法 T(n)=O(n2)
      Voronoi 分治算法 T(n)=O(nlogn)
      Voronoi 减量算法 T(n)=O(nlogn)
      Voronoi 平面扫描算法 T(n)=O(nlogn)
      Delaunay 三角网生长法 T(n)=O(n2)
      Delaunay 逐点插入法 T(n)=O(n2)
      Delaunay 分治算法 T(n)=O(nlogn)
      耦合PDE模型 递归 T(n)=O(nlogn)

      依据图 5图 6,对耦合模型划分、[44]标识划分和Delaunay在不同数据规模和离散度下空间划分程序耗时进行对比分析,分析结果见表 3

      表 3  程序耗时对比分析表/ms

      Table 3.  Comparative Analysis Table of Time Program Runs/ms

      划分方法 110组 220组 330组 440组
      耦合划分 1 097 3 278 6 178 12 478
      [44]标识 53 197 33 216 41 494 30 394
      Delaunay 13 109 17 157 22 225 33 302
    • 非凸集合有两种情况,一种是凹多边形边界,另一种是非单连通(存在鞍部或者岛)边界[16]。Delaunay划分非凸约束条件下会出现非法边界和非法多边形,影响空间划分的效果,其验证试验结果如图 7图 10所示。程序运行环境为CPU AMD A8-4500M,VB6.0平台,Windows XP操作系统。

      图  7  Delaunay非单连通边界约束生成非法边界

      Figure 7.  Illegal Boundary of Delaunay on Non-convex Constrained

      图  8  Delaunay非单连通边界生成非法三角网图

      Figure 8.  Illegal Triangulation of Delaunay on Non-simply Connected Constrained

      图  9  Delaunay非凸边界约束产生的非法边界

      Figure 9.  Illegal Boundary of Delaunay on Non-convex Constrained

      图  10  Delaunay非凸边界约束产生的非法三角网

      Figure 10.  Non-convex Boundary Constrained Delaunay Illegal Triangulation

    • 依据图 410,对耦合空间划分、[44]标识划分和Delaunay划分的程序耗时在非凸集合约束下进行空间划分效果的对比分析,结果见表 4

      表 4  非凸集合约束划分效果对比分析表 [16]

      Table 4.  Correlation Analysis Table of Partition Under Non-Convex [16]

      划分方法 非法边界 非法多边形 冗余
      耦合模型 不存在 不存在 不存在
      [44]标识划分 存在 存在 存在
      Delaunay划分 存在 存在 不存在
    • 本文通过耦合空间离散数据的数据规模和离散程度建立了非凸集合条件下多因子耦合空间划分PDE模型,并进行一系列的纵横向对比分析,实现了以下目标。首次,模型能够准确计算出空间划分的数量、间距、离散度。其次,不同数据规模下,耦合空间划分、[44]标识划分和Delaunay测试结果对比分析表明,耦合模型程序耗时和非凸集合条件下划分效果都优于其他方法。最后,耦合模型算法耗时随着离散测度的数值变大而增长。

      从数据集角度来讲,数据规模、数据离散度、划分类型、地形因子是影响空间划分最重要的几个因素,耦合因素进行空间划分能够提高空间划分质量和效率。本文仅探讨小量数据规模下耦合因素的空间划分效果和效率,海量数据空间划分数据冗余、效率以及划分质量的控制研究还需进一步研究和分析。

参考文献 (16)

目录

    /

    返回文章
    返回