Delaunay三角化中特征约束细分嵌入算法

田峰敏; 徐定杰; 李宁

美国《工程索引》（EI）核心期刊
美国《剑桥科学文摘》（CSA）收录期刊
荷兰斯高帕斯数据库（Scopus）收录期刊
英国INSPEC数据库（SA）收录期刊

留言板

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

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

Delaunay三角化中特征约束细分嵌入算法

田峰敏, 徐定杰, 李宁

文章导航 > 武汉大学学报 ( 信息科学版) > 2009 > 34(3): 358-361

田峰敏, 徐定杰, 李宁. Delaunay三角化中特征约束细分嵌入算法[J]. 武汉大学学报 ( 信息科学版), 2009, 34(3): 358-361.

引用本文:

田峰敏, 徐定杰, 李宁. Delaunay三角化中特征约束细分嵌入算法[J]. 武汉大学学报 ( 信息科学版), 2009, 34(3): 358-361.

TIAN Fengmin, XU Dingjie, LI Ning. A Node Refinement Algorithm for Inserting Feature Constraints in Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2009, 34(3): 358-361.

Citation:

TIAN Fengmin, XU Dingjie, LI Ning. A Node Refinement Algorithm for Inserting Feature Constraints in Delaunay Triangulation[J]. Geomatics and Information Science of Wuhan University, 2009, 34(3): 358-361.

Delaunay三角化中特征约束细分嵌入算法

¹哈尔滨工程大学自动化学院,哈尔滨市南通大街145号150001

基金项目: 船舶行业国防预研基金资助项目(06J3.8.6)；哈尔滨工程大学基础研究基金资助项目(HEUFP07002)

详细信息

作者简介:
田峰敏,博士生。研究方向为海洋GIS和水下地形辅助导航。

中图分类号: P208

A Node Refinement Algorithm for Inserting Feature Constraints in Delaunay Triangulation

¹College of Automation,Harbin Engineering University,145 Nantong Street,Harbin 150001,China

Funds: 船舶行业国防预研基金资助项目(06J3.8.6)；哈尔滨工程大学基础研究基金资助项目(HEUFP07002)

摘要: 在Delaunay三角化中,以在特征约束上插入附加点的方式对特征约束细分,可使剖分网格在表达特征约束的同时仍满足Delaunay三角网格特性。本文提出了一种改进的细分嵌入算法——端点外接圆法(ETCM),该算法具有线性时间复杂度。以剖分结果的稳定性、附加点个数、运算耗时和网格质量为评价标准,对ETCM和现有的细分嵌入算法进行了评估。实验结果表明,在运算耗时方面,ETCM受数据分布的影响最小,且耗时最少;在其他方面,与现有算法的最好表现持平。
- Delaunay三角化 /
- 特征约束 /
- 细分嵌入
Abstract: An improved algorithm of node refinement scheme called endpoint triangle's circumcircle method(ETCM) is proposed,which has a linear time complexity.Regarding stability,new nodes quantity,time costs and meshes quality as criterions,ETCM and several existing node refinement algorithms were evaluated by simulations.The results show that ETCM has the least time costs,and is more independent of data distribution.Moreover,the performances on other criterions of ETCM are almost the same as those of the best of existing algorithms.
- Delaunay triangulation /
- feature constrains /
- node refinement

[1]	任营营, 王解先, 王虎, 连丽珍, 侯阳飞, 王永哲. 基于局部无缝Delaunay三角网反距离加权法构建中国大陆速度场 . 武汉大学学报 ( 信息科学版), 2021, 46(7): 1071-1080. doi: 10.13203/j.whugis20190175
[2]	孙文潇, 王健, 梁周雁, 马伟丽, 陈喆. 法线特征约束的激光点云精确配准 . 武汉大学学报 ( 信息科学版), 2020, 45(7): 988-995. doi: 10.13203/j.whugis20180315
[3]	李靖涵, 武芳, 杜佳威, 巩现勇, 行瑞星. Delaunay三角网支持下的海图等深线化简 . 武汉大学学报 ( 信息科学版), 2019, 44(5): 778-783. doi: 10.13203/j.whugis20170223
[4]	杨伟, 艾廷华. 运用Delaunay三角网提取OpenStreetMap主干道多边形 . 武汉大学学报 ( 信息科学版), 2018, 43(11): 1725-1731. doi: 10.13203/j.whugis20160294
[5]	张春亢, 赵学胜, 王洪斌. 一种采用流计算的Delaunay三角网切块剖分算法 . 武汉大学学报 ( 信息科学版), 2017, 42(7): 931-936. doi: 10.13203/j.whugis20150375
[6]	李国俊, 李宗春, 孙元超, 李伟, 黄志勇. 利用Delaunay细分进行噪声点云曲面重建 . 武汉大学学报 ( 信息科学版), 2017, 42(1): 123-129. doi: 10.13203/j.whugis20140513
[7]	倪皓晨, 伍钟洁, 郏建, 徐地保, 芮一康, 王结臣. 一种基于Delaunay三角网的栅格线划矢量化方法 . 武汉大学学报 ( 信息科学版), 2016, 41(2): 184-189. doi: 10.13203/j.whugis20140582
[8]	石岩, 杨学习, 邓敏. 利用层次约束Delaunay三角网探测空间点事件离群模式 . 武汉大学学报 ( 信息科学版), 2016, 41(12): 1584-1592. doi: 10.13203/j.whugis20140831
[9]	王钊, 杨殿阁, 张照生, 连小珉. 绘制尺寸固定的网格化嵌入式地图数据结构研究 . 武汉大学学报 ( 信息科学版), 2013, 38(3): 365-369.
[10]	. 绘制尺寸固定的网格化嵌入式地图数据结构研究 . 武汉大学学报 ( 信息科学版), 2013, 38(3): 365-.
[11]	董箭, 彭认灿, 郑义东. 利用局部动态最优Delaunay三角网改进逐点内插算法 . 武汉大学学报 ( 信息科学版), 2013, 38(5): 613-617.
[12]	张云生, 朱庆, 吴波, 邹峥嵘. 一种基于三角网约束的立体影像线特征多级匹配方法 . 武汉大学学报 ( 信息科学版), 2013, 38(5): 522-527.
[13]	沈晶, 刘纪平, 林祥国, 赵荣. 集成距离变换和区域邻接图生成Delaunay三角网的方法研究 . 武汉大学学报 ( 信息科学版), 2012, 37(8): 1000-1003.
[14]	陈振学, 常发亮, 刘春生, 徐建光. 基于Adaboost算法和人脸特征三角形的姿态参数估计 . 武汉大学学报 ( 信息科学版), 2011, 36(10): 1164-1167.
[15]	李佳田, 李佳, 段平, 余莉. 球面Delaunay三角网的透视投影算法 . 武汉大学学报 ( 信息科学版), 2011, 36(9): 1116-1119.
[16]	王春, 汤国安, 刘学军, 陶旸. 特征嵌入式数字高程模型研究 . 武汉大学学报 ( 信息科学版), 2009, 34(10): 1149-1154.
[17]	郑春燕, 郭庆胜, 胡华科, 夏慧琼. 基于约束Delaunay三角网建立等高线层次结构的方法 . 武汉大学学报 ( 信息科学版), 2008, 33(5): 524-527.
[18]	谭兵, 郭建星, 邢帅, 张艳. 影像超分辨率重建中的动态数据更新算法 . 武汉大学学报 ( 信息科学版), 2005, 30(12): 1067-1070.
[19]	袁修孝, 陈小明. 无初始化的GPS辅助空中三角测量 . 武汉大学学报 ( 信息科学版), 2000, 25(6): 476-481.
[20]	艾廷华, 郭仁忠. 支持地图综合的面状目标约束Delaunay三角网剖分 . 武汉大学学报 ( 信息科学版), 2000, 25(1): 35-41.

点击查看大图

计量

文章访问数: 786
HTML全文浏览量: 47
PDF下载量: 323
被引次数: 0

Delaunay三角化中特征约束细分嵌入算法

¹哈尔滨工程大学自动化学院,哈尔滨市南通大街145号150001

基金项目: 船舶行业国防预研基金资助项目(06J3.8.6)；哈尔滨工程大学基础研究基金资助项目(HEUFP07002)

作者简介:
田峰敏,博士生。研究方向为海洋GIS和水下地形辅助导航。

收稿日期: 2009-01-16
修回日期: 2009-01-16
刊出日期: 2009-03-05

中图分类号: P208

关键词:

Delaunay三角化 /

特征约束 /

细分嵌入

摘要: 在Delaunay三角化中,以在特征约束上插入附加点的方式对特征约束细分,可使剖分网格在表达特征约束的同时仍满足Delaunay三角网格特性。本文提出了一种改进的细分嵌入算法——端点外接圆法(ETCM),该算法具有线性时间复杂度。以剖分结果的稳定性、附加点个数、运算耗时和网格质量为评价标准,对ETCM和现有的细分嵌入算法进行了评估。实验结果表明,在运算耗时方面,ETCM受数据分布的影响最小,且耗时最少;在其他方面,与现有算法的最好表现持平。