-
摘要: 针对大规模数据处理时Delaunay三角剖分过于耗时的问题, 本文提出了一种基于边指针搜索及区域划分的三角剖分算法.基于边指针设计了一种能够反映三角形之间位置关系的数据结构, 并优化了目标三角形的搜索路径.基于该数据结构, 利用区域划分进一步降低目标三角形的搜索深度.超级三角形所在的正方形被划分成具有相同尺寸的区域, 目标三角形的搜索从插入点所在的区域的入口三角形开始, 这大大缩小了目标三角形的搜索范围.实验证明, 与传统的Delaunay三角剖分算法相比, 该算法的效率显著提升.
-
关键词:
- Delaunay三角剖分 /
- 三维重建 /
- 边指针 /
- 区域划分
Abstract: To solve the problem of taking too much time when dealing with large-scale data, a triangulation algorithm based on edge-pointer search and region-division is proposed. A data structure based on the edge-pointer is designed to reflect the positional relationship between triangles, and the search path of the target triangle is also optimized. Moreover, region-division is utilized to reduce the search depth. The square which contains the super triangle is divided into some regions of the equal size. The search for the target triangle begins with the entry triangle of the region where the insertion point is located. As a result, the search scope of the target triangle is narrowed. Experiment results show that the algorithm is much more efficient than the traditional Delaunay triangulation algorithm.-
Key words:
- Delaunay triangulation /
- 3D reconstruction /
- edge-pointer /
- region-division
1) 本文责任编委 刘艳军 -
表 1 基于边指针及区域划分的算法数据结构
Table 1 Data structure of algorithm based on edge-pointer and region-division
Structure POINT $ x $ $ y $ entry_flag EDGE $ V_1 $ $ V_2 $ TRIANGLE $ V_1 $, $ V_2 $, $ V_3 $ *$ p_1 $, *$ p_2 $, *$ p_3 $ entry $ X, Y $ REGION valid *entrytri 
下载: 导出CSV
表 2 算法的执行时间(s)
Table 2 Running time of algorithms (s)
散点数量 2万 3.5万 5万 7万 10万 TD 113.515 298.687 756.656 1 943.39 3 972.81 CGAL 1.719 3.074 4.281 6.265 8.594 EPD 0.563 1.547 2.562 3.218 6.172 EPRDD 0.117 0.234 0.325 0.531 0.813
下载: 导出CSV
表 3 算法的平均搜索深度
Table 3 Average search depth of algorithms
散点数量 2万 3.5万 5万 7万 10万 TD 10 003 17 543 24 989 34 893 49 854 EPD 108 229 233 247 278 EPRDD 8 11 13 15 18
下载: 导出CSV
-
[1] 陈加, 张玉麒, 宋鹏, 魏艳涛, 王煜.深度学习在基于单幅图像的物体三维重建中的应用.自动化学报, 2019, 45(4): 657-668 doi: 10.16383/j.aas.2018.c180236Chen Jia, Zhang Yu-Qi, Song Peng, Wei Yan-Tao, Wang Yu. Application of deep learning to 3D object reconstruction from a single image. Acta Automatica Sinica, 2019, 45(4): 657-668 doi: 10.16383/j.aas.2018.c180236 [2] 薛俊诗, 易辉, 吴止锾, 陈向宁.一种基于场景图分割的混合式多视图三维重建方法.自动化学报, 2020, 46(4): 782-795 doi: 10.16383/j.aas.c180155Xue Jun-Shi, Yi Hui, Wu Zhi-Huan, Chen Xiang-Ning. A hybrid multi-View 3D reconstruction method based on scene graph partition. Acta Automatica Sinica, 2020, 46(4): 782-795 doi: 10.16383/j.aas.c180155 [3] 刘剑, 白迪.基于特征匹配的三维点云配准算法.光学学报, 2018, 38(12): 240-247 https://www.cnki.com.cn/Article/CJFDTOTAL-GXXB201812029.htmLiu Jian, Bai Di. 3D point cloud registration algorithm based on feature matching. Acta Optica Sinica, 2018, 38(12): 240-247 https://www.cnki.com.cn/Article/CJFDTOTAL-GXXB201812029.htm [4] 刘海强, 余建波.二维局部均值分解算法.计算机辅助设计与图形学学报, 2018, 30(10): 1859-1869 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201810010.htmLiu Hai-Qiang, Yu Jian-Bo. A bidimensional local mean decomposition algorithm. Journal of Computer-Aided Design & Computer Graphics, 2018, 30(10): 1859-1869 https://www.cnki.com.cn/Article/CJFDTOTAL-JSJF201810010.htm [5] 闫自庚, 蒋建国, 郭丹.基于SURF特征和Delaunay三角网格的图像匹配.自动化学报, 2014, 40(6): 1216-1222 doi: 10.3724/SP.J.1004.2014.01216Yan Zi-Geng, Jiang Jian-Guo, Guo Dan. Image matching based on SURF feature and Delaunay triangular meshes. Acta Automatica Sinica, 2014, 40(6): 1216-1222 doi: 10.3724/SP.J.1004.2014.01216 [6] 刘琴琴.平面域Delaunay三角网点定位算法研究综述.电子设计工程, 2017, 25(1): 47-51 https://www.cnki.com.cn/Article/CJFDTOTAL-GWDZ201701012.htmLiu Qin-Qin. Overview of point location algorithm of Delaunay triangulation on plane domain. Electronic Design Engineering, 2017, 25(1): 47-51 https://www.cnki.com.cn/Article/CJFDTOTAL-GWDZ201701012.htm [7] Lin J, Chen R, Yang C, Shu Z, Wang C, Lin Y, et al. Distributed and parallel Delaunay triangulation construction with balanced binary-tree model in cloud. In: Proceedings of 15th International Symposium on Parallel and Distributed Computing. Fuzhou, China: IEEE, 2017. 107-113 [8] Lin J, Chen R, Wu L, Shu Z, Yang C. Adaptive parallel Delaunay triangulation construction with dynamic pruned binary tree model in Cloud. Concurrency & Computation Practice & Experience, 2017, 29(8): e4175 [9] Bowyer A. Computing Dirichlet tessellations. The Computer Journal, 1981, 24(2): 162-166 doi: 10.1093/comjnl/24.2.162 [10] Watson D F. Computing the N-Dimensional Delaunay tessellation with application to Voronoi polytopes. The Computer Journal, 1981, 24(2): 167-172 doi: 10.1093/comjnl/24.2.167 [11] Lawson C L. Software for $C^1$ surface interpolation. Mathematical Software, 1977: 161-194 [12] Liu J F, Yan J H, Lo S H. A new insertion sequence for incremental Delaunay triangulation. Acta Mechanica Sinica, 2013, 29(1): 99-109 doi: 10.1007/s10409-013-0001-x [13] Lo S H. Delaunay triangulation of non-uniform point distributions by means of multi-grid insertion. Finite Elements in Analysis & Design, 2013, 63(4): 8-22 [14] Su T, Wang W, Lv Z, Wu W, Li X. Rapid Delaunay triangulation for randomly distributed point cloud data using adaptive Hilbert curve. Computers & Graphics, 2016, 54: 65-74 [15] Zalik B, Kolingerova I. An incremental construction algorithm for Delaunay triangulation using the nearest-point paradigm. International Journal of Geographical Information Science, 2003, 17(2): 119-138 doi: 10.1080/713811749 [16] Zadravec M, Zalik B. An almost distribution-independent incremental Delaunay triangulation algorithm. Visual Computer, 2005, 21(6): 384-396 doi: 10.1007/s00371-005-0293-3 [17] Xi J H, Zuo S C. An improved algorithm based on incremental insertion in delaunay triangulation. Applied Mechanics and Materials, 2013, 397-400: 1691-1694 doi: 10.4028/www.scientific.net/AMM.397-400.1691 [18] Kohout J, Kolingerova I. Parallel Delaunay triangulation based on circum-circle criterion. In: Proceedings of the 19th Spring Conference on Computer Graphics. Slovakia: ACM, 2003. 73-81 [19] Rong G, Tan T S, Cao T T, Stephanus. Computing two-dimensional Delaunay triangulation using graphics hardware. In: Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games. California, USA: ACM, 2008. 89-97 [20] Cuong N, Philip J R. TIPP: Parallel delaunay triangulation for large-scale datasets. In: Proceedings of the 30th International Conference on Scientific and Statistical Database Management. Bolzano, Italy: ACM, 2018. 1-12 [21] Lo S H. Parallel Delaunay triangulation——application to two dimensions. Finite Elements in Analysis & Design, 2012, 62: 37-48 [22] 杨昊禹, 刘利, 张诚, 于灏.面向并行的动态增量式Delaunay三角剖分算法.计算机科学与探索, 即将出版Yang Haoyu, Liu Li, Zhang Cheng, Yu Hao. Parallelism-oriented dynamic incremental Delaunay triangulation algorithm. Journal of Frontiers of Computer Science and Technology, to be published [23] 李国庆, 马凤山, 邓清海.基于凸多边形的Delaunay三角剖分.工程地质计算机应用, 2007(2): 8-10 https://www.cnki.com.cn/Article/CJFDTOTAL-GCDJ200702002.htmLi Guo-Qing, Ma Feng-Shan, Deng Qing-Hai. Delaunay triangulation based on convex polygons. Engineering Geology Computer Application, 2007(2): 8-10 https://www.cnki.com.cn/Article/CJFDTOTAL-GCDJ200702002.htm [24] Graham R L. An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1972, 1(4): 132-133 doi: 10.1016/0020-0190(72)90045-2 [25] 崔国华, 洪帆, 余祥宣.确定平面点集凸包的一类最优算法.计算机学报, 1997, 20(4): 330-334 doi: 10.3321/j.issn:0254-4164.1997.04.006Cui Guo-Hua, Hong Fan, Yu Xiang-Xuan. A class of optimal algorithms for determining the convex hull of a set of nodes in a plane. Chinese Journal of Computers, 1997, 20(4): 330-334 doi: 10.3321/j.issn:0254-4164.1997.04.006 [26] 刘斌, 王涛.一种高效的平面点集凸包递归算法.自动化学报, 2012, 38(8): 1375-1379 doi: 10.3724/SP.J.1004.2012.01375Liu Bin, Wang Tao. An efficient convex hull algorithm for pPlanar point set based on recursive method. Acta Automatica Sinica, 2012, 38(8): 1375-1379 doi: 10.3724/SP.J.1004.2012.01375 [27] 贾晓林, 吴立新, 王彦兵.二维Delaunay三角网局部更新:点插入与点删除.地理与地理信息科学, 2004, 20(5): 28-31 doi: 10.3969/j.issn.1672-0504.2004.05.007Jia Xiao-Lin, Wu Li-Xin, Wang Yan-Bing. Two dimensional local updating for Delaunay TIN: point insertion and point deletion. Geography and Geo-Information Science, 2004, 20(5): 28-31 doi: 10.3969/j.issn.1672-0504.2004.05.007 -
图(7) / 表(3)
计量
- 文章访问数: 921
- HTML全文浏览量: 168
- PDF下载量: 123
- 被引次数: 0
