Grid Cutting Method of 3D Stratum and Its Application to Engineering
-
摘要: 针对三维地层表示中散乱点的三角化问题, 提出了一种新的剖分算法——环形三角剖分算法.该算法首先在散乱点中心构造初始三角形, 并将其3条边作为初始环形路径; 然后对环形路径上的每条线段, 都在其外围寻找与两端点所成夹角最大的点构造新三角形, 并将其纳入环形路径, 从而使环形路径不断向外围扩展; 重复此扩展过程直到所有散乱点都处于路径范围内.对上述剖分中遗漏的小块区域形成的“空洞”, 利用简单多边形的三角剖分方法实现三角化.此算法时间复杂性介于Ο(n)与Ο(n2)之间, 其效率体现在: 只搜索外围散乱点, 减少了夹角计算过程; 只对已扩展点进行“空洞”判断, 节省了处理时间.将此环形三角剖分算法应用于广东省东深供水改造工程的三维地层构造与分析中, 取得了良好的剖分效果和执行效率, 对地层的任意剖切和开挖分析均具有良好的支持.Abstract: In order to form triangles with discrete points which distributed in a plane in the research of 3D stratum, this paper presents a new algorithm called automatic annular triangular cutting arithmetic (AATCA) which expands from the center to the periphery. It constructs a triangle by searching for reasonable points in the periphery place around a polygon path from the beginning of the central part of these discrete points, and updates the polygon with time. There will be hollows during the expanding, as some small areas may be skipped. But they can be divided into triangles by an existing method. Then the memory structure of data in the grid cutting process is discussed; The basic procedure and steps of AATCA are given; The time complexity of AATCA we concerning about, is between O(n) and O(n2). Efficiency is embodied in two aspects: to reduce the steps of angle calculation by only considering some polygons distributed on the periphery or on the nearside of present side; and to save time by only giving an estimation of the hollows for the expanded points. The AATCA algorithm is then applied to the Water Supply Reconstruction Project from Dongjiang to Shenzhen, which is the largest water conservancy construction project in Guangdong Province at present. The results show that the algorithm not only gives a reasonable triangular division for the polygon points but also performs efficiently.
-
Key words:
- 3D stratum /
- grid cutting algorithm /
- discrete points /
- triangulation /
- application to engineering.
-
图 2 中心三角形与初始多边形(a)以及新三角形的形成(b)与多边形的扩展(c)
Fig. 2. Initial triangle and polygon (a), new triangles (b) and expanded polygons (c)
图 6 平面任意散乱点三角剖分示例
Fig. 6. Example for triangles formed with discrete points in a plane
-
Li, S. S., Zhu, Z. X., Qin, L., et al., 2000. Automatic triangulation of arbitrary planar domain. Journal of Tianjin University, 33 (5): 592-598 (in Chinese with English abstract). Liu, Z. Q., Zhou, C. Y., Zhao, X. S., et al., 2003. Research on three-dimensiona Istratum model and its visual technology. Acta Scientiarum Naturalium Universitatis Sunyatseni, 42 (4): 21-23 (in Chinese with English abstract). Lu, Z. Y., Wu, C. K., Zhou, X. N., 1997. Overall Delaunay triangulation of 2D scattered data with characteristic constraints. Chinese J. of Computers, 20 (2): 118-124 (in Chinese with English abstract). Sun, G. Q., Shi, M. J., Lei, Y. H., et al., 2001. Research on 3D engineering geological model and its visualization. Geotechnical Investigation & Surveying, (5): 8-10 (in Chinese with English abstract). Wright, R S., Sweet, Jr. M., 2000. Open GL superbible. 2nd Edition. Translated by Xiaoxiang Studio. People's Posts & Telecom Press, Beijing, 3-215(in Chinese). Yang, Q., Xu, Y. A., Chen, Q. M., et al., 1998. Triangulation algorithm of scattered data on arbitrary planar domain. Journal of Software, 9 (4): 241-245 (in Chnese with English abstract). Zhou, P. D., 1999. Computational geometry—Analysis and design of algorithmic. Tsinghua University Press, Beijing, 53-54 (in Chinese). Zhou, P. D., 1996. The algorithm for triangulation of the point-set in the plane. China J. CAD & CG, 8 (4): 259-264 (in Chinese with English abstract). Zhou, X. Y., He, D. Z., Zhu, X. X., 1994. An algorithm of triangulation for scattered data in none-convex region. China J. CAD & CG, 6 (4): 256-259 (in Chinese with English abstract). 李世森, 朱志夏, 秦岭, 等, 2000. 任意平面区域的自动三角剖分. 天津大学学报, 33 (5): 597. https://www.cnki.com.cn/Article/CJFDTOTAL-TJDX200005010.htm 刘祚秋, 周翠英, 赵旭升, 等, 2003. 三维地层模型及可视化技术研究. 中山大学学报(自然科学版), 42 (4): 21-23. doi: 10.3321/j.issn:0529-6579.2003.04.007 卢朝阳, 吴成柯, 周幸妮, 1997. 满足全局Delaunay特性的带特征约束的散乱数据最优三角剖分. 计算机学报, 20 (2): 118-124. doi: 10.3321/j.issn:0254-4164.1997.02.004 孙国庆, 施木俊, 雷永红, 等, 2001. 三维工程地质模型与可视化研究. 工程勘察, (5): 8-10. https://www.cnki.com.cn/Article/CJFDTOTAL-GCKC200105002.htm Wright, R. S., Sweet, Jr. M., 2000. OpenGL超级宝典(第二版). 潇湘工作室译. 北京: 人民邮电出版社, 3-215. 杨钦, 徐永安, 陈其明, 等, 1998. 任意平面域上离散点集的三角化方法. 软件学报, 9 (4): 241-245. https://www.cnki.com.cn/Article/CJFDTOTAL-RJXB804.000.htm 周培德, 1999. 计算几何——算法分析与设计. 北京: 清华大学出版, 53-54. 周培德, 1996. 平面点集三角剖分的算法. 计算机辅助设计与图形学学报, 8 (4): 259-264. doi: 10.3321/j.issn:1003-9775.1996.04.004 周晓云, 何大曾, 朱心雄, 1994. 实现平面上散乱数据点三角剖分的算法. 计算机辅助设计与图形学学报, 6 (4): 256-259. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJF404.002.htm -
下载:
点击查看大图
图(7)
计量
- 文章访问数: 3591
- HTML全文浏览量: 623
- PDF下载量: 19
- 被引次数: 0
