基于三角形分解的三角网切割

doi:10.16182/j.issn1004731x.joss.201711009

系统仿真学报 ›› 2017, Vol. 29 ›› Issue (11): 2656-2662.doi: 10.16182/j.issn1004731x.joss.201711009

基于三角形分解的三角网切割

陈国军¹, 黄莹莹¹, 李华², 李金玲¹, 刘婧怡¹

1.中国石油大学(华东) 计算机与通信工程学院,青岛 266580;
2.中国石油天然气股份有限公司勘探开发研究院,北京 100083

收稿日期:2016-06-13 发布日期:2020-06-05
第一作者简介:陈国军(1968-),男,江苏如东,博士,副教授,研究方向为图形图像处理,虚拟现实。
基金资助:
国家863计划 (2015AA016403),虚拟现实技术与系统国家重点实验室(北京航空航天大学)开放基金(BUAA-VR-15KF-13),山东省教育厅高校科技计划(J15LN66)

Triangular Mesh Clipping Using Triangular Decomposition

Chen Guojun¹, Huang Yingying¹, Li Hua², Li Jinling¹, Liu Jingyi¹

1. College of Computer and Communication Engineering, China University of Petroleum, Qingdao 266580, China;
2. Exploration and Development Research Institute of PetroChina Co Ltd, Beijing 100083, China

Received:2016-06-13 Published:2020-06-05

摘要/Abstract

摘要： 三角网的切割广泛应用于网格重构、网格变形、地形融合与分析等领域,在地理信息系统应用中,三角网切割是实现地形表面模型与建筑物模型融合的关键算法。现有的多边形裁剪算法没有考虑相邻三角形的空间关系,直接用于切割三角网往往会出现T交叉点,形成不稳定三角网。为了解决这一问题,提出了一种基于三角形分解的三角网切割算法,根据三角形与裁剪线的位置关系,对三角形进行分解裁剪,分解时不引入非裁剪多边形边上的交点。实验结果表明分解裁剪算法能避免裁剪结果中出现T交叉点,有效生成稳定三角网。

关键词: 三角网切割, T交叉点, 分解裁剪, 多边形裁剪

Abstract: Triangular mesh clipping is widely used in grid reconstruction, grid deformation, terrain fusion and analysis, and many other fields. In the application of geographic information system (GIS), triangular mesh clipping is the key to the fusion of terrain surface model and building model. However, existing polygon clipping algorithms do not take the space relationship of adjacent triangles into account.If they were directly used in triangular mesh clipping, T-intersections would appear in the cutting results, leading tounstable triangular mesh. In order to solve this problem, a triangular mesh clipping algorithm based on triangular decomposition is proposed. Triangular decomposition is implemented according to the location relationship between the triangle and the cutting line, whichdoes not introduce other intersections that are not on the polygon line. Results of the experiments show that the decomposition algorithm can avoid T-intersections and effectively generate stable triangular mesh.

Key words: triangular mesh clipping, T-intersections, triangular decomposition, polygon clipping

中图分类号:

TP391.9

陈国军,黄莹莹,李华等 . 基于三角形分解的三角网切割[J]. 系统仿真学报, 2017, 29(11): 2656-2662.

Chen Guojun,Huang Yingying,Li Hua,et al . Triangular Mesh Clipping Using Triangular Decomposition[J]. Journal of System Simulation, 2017, 29(11): 2656-2662.

参考文献

[1] 张英慧, 陈琦, 唐勇. 一个可靠实用的多边形裁剪算法[J]. 燕山大学学报, 1999(1):79-81.
Zhang Yinghui, Chen Qi, Tang Yong.A reliable and useful polygon clipping algorithm[J]. Journal of Yanshan University, 1999 (1): 79-81.
[2] 鲍虎军, 彭群生. 一个有效的多边形裁剪算法[J]. 自动化学报, 1996(6):741-744.
BaoHujun, PengQunsheng. An efficient algorithm for polygon clipping[J]. ActaAutomaticaSinica, 1996 (6): 741-744.
[3] 李志涛, 李霖, 吴贤良,等. 任意多边形裁剪算法的研究及其实现[J]. 测绘信息与工程, 2004, 29(5):8-10.
Li Zhitao, Li Lin, Wu Xianliang, et al.Research and implementation of polygon clipping algorithm[J]. JournalofGeomatics, 2004, 29(5): 8-10.
[4] Vatti B R.A generic solution to polygon clipping[J]. Communications of the Acm(S0001-0782), 1992, 35(7): 56-63.
[5] Greiner G, Hormann K.Efficient clipping of arbitrary polygons[J]. Acm Transactions on Graphics (S0730-0301), 1998, 17(17):71-83.
[6] 刘勇奎, 高云, 黄有群. 一个有效的多边形裁剪算法[J]. 软件学报, 2003, 14(4):845-856.
Liu Yongkui, Gao Yun, Huang Youqun.An efficient algorithm for polygon clipping[J].Journal of Software, 2003, 14(4): 845-856.
[7] 付迎春, 袁修孝. 一种有效的任意多边形裁剪算法[J]. 计算机工程, 2006, 32(7):278-280.
Fu Yingchun, Yuan Yan.An efficient algorithm for polygon clipping[J]. Computer Engineering, 2006, 32(7): 278-280.
[8] Martínez F, Rueda A J, Feito F R.A new algorithm for computing Boolean operations on polygons[J]. Computers & Geosciences (S0098-3004), 2009, 35(35):1177-1185.
[9] 王结臣, 沈定涛, 陈焱明, 等. 一种有效的复杂多边形裁剪算法[J]. 武汉大学学报:信息科学版, 2010(3): 369-372.
Wang Jiechen, ShenDingtao, Chen Yanming, et al. An efficient algorithm for complex polygon clipping[J]. Journal of Wuhan University: Information Science Edition, 2010 (3): 369-372.
[10] 何陈棋, 陆国栋, 谭建荣. 基于编码与分类技术的任意多边形裁剪新算法[J]. 计算机工程与应用, 2003, 39(21): 56-58.
He Chen chess, Lu Guodong, Tan Jianrong. A high efficient polygon clipping algorithm against rectangular window based on encoding and classification technique[J]. Computer Engineering and Applications, 2003, 39(21): 56-58.
[11] 彭欢, 陆国栋, 谭建荣. 基于端点与交点编码的矩形窗口多边形裁剪新算法[J]. 图学学报, 2006, 27(4): 72-76.
PengHuan, Lu Guodong, Tan Jianrong. A new algorithm of polygon clipping against rectangular window based on the endpoint and intersection-point encoding[J]. Journal of Graphics, 2006, 27(4): 72-76.
[12] 范俊甫, 孔维华, 马廷,等. RaPC:一种基于栅格化思想的多边形裁剪算法及其误差分析[J]. 测绘学报, 2015(3): 338-345.
Fan Junfu, Kong Weihua, Ma Ting, et al.RaPC:ARasterization-based Polygon Clipping Algorithm and Its Error Analysis[J]. Acta Geodaeticaet Cartographica Sinica, 2015 (3): 338-345.
[13] Karinthi R, Srinivas K, Almasi G.A Parallel Algorithm for Computing Polygon Set Operations[J]. Journal of Parallel & Distributed Computing(S0743-7315), 1994, 26(26):115-119.
[14] Puri S, Prasad S K.Output-sensitive parallel algorithm for polygon clipping[C]//Parallel Processing (ICPP), 2014 43rd International Conference on. IEEE, 2014: 241-250.
[15] 李金玲. 三角网的并行切割算法及应用[D].青岛: 中国石油大学(华东), 2015.
Li Jinling.A parallel cutting algorithm of triangular mesh and its application [D]. Qingdao: China University of Petroleum (Hua Dong), 2015.

基于三角形分解的三角网切割

Triangular Mesh Clipping Using Triangular Decomposition

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	董志明, 胡忠奇, 戴浩然, 高建成. 基于大语言模型的作战仿真想定自动化生成方法[J]. 系统仿真学报, 2026, 38(5): 1129-1145.
[2]	李校男, 晁涛, 马萍, 杨明, 王玉轩. 基于期望最大化方法的非线性SSM黑箱鲁棒辨识[J]. 系统仿真学报, 2026, 38(5): 1146-1158.
[3]	刘银钢, 马明, 张荣华. 基于大语言模型的兵棋推演动态任务规划[J]. 系统仿真学报, 2026, 38(5): 1187-1204.
[4]	苏泓嘉, 张成, 刘飞. 基于模糊功能依赖网分析的体系效能评估方法[J]. 系统仿真学报, 2026, 38(5): 1224-1238.
[5]	梅华威, 杨鹏慧, 余洋. 计及数据漂移改进PatchTST的超短期光伏功率预测[J]. 系统仿真学报, 2026, 38(5): 1239-1254.
[6]	李权, 苏鹏, 万海英, 张承玺, 何志坚, 倪艺洋, 赵忠盖, 刘飞. 基于多阶段LHS-EPRCC方法的青霉素发酵过程建模[J]. 系统仿真学报, 2026, 38(5): 1255-1276.
[7]	周子聪, 曾俊杰, 胡越, 朱正秋, 尹全军. 基于次优示例引导的兵棋推演多智能体强化学习方法[J]. 系统仿真学报, 2026, 38(5): 1277-1289.
[8]	石敏, 郭诗盛, 王素琴, 李兆歆, 朱登明. 融合物理与几何先验的无抓取标注6-DoF抓取检测方法[J]. 系统仿真学报, 2026, 38(5): 1290-1302.
[9]	姜彦吉, 肖星佚, 董浩, 于淼, 黄金山, 刘大千, 费博雯. 融合点线特征的图关系优化3D车道线检测方法[J]. 系统仿真学报, 2026, 38(5): 1303-1319.
[10]	张鑫, 张平, 张琛, 刘威, 韩博阳. 非均质土壤条件下挖掘阻力计算模型研究[J]. 系统仿真学报, 2026, 38(5): 1320-1332.
[11]	王伟, 刘东, 崔新豪, 李博, 肖依永, 任羿. 复杂项目多级动态挣值管理数字化模型及应用[J]. 系统仿真学报, 2026, 38(5): 1350-1364.
[12]	彭莉峻, 苏庭琪, 刘沛津, 何林, 周协武, 张闽心. 融合人体关键点的实验室PPE规范穿戴检测方法[J]. 系统仿真学报, 2026, 38(5): 1365-1382.
[13]	滕靖, 童文聪, 张中杰, 姚幸, 李君羡. 有轨电车交叉口速度自动引导方法及仿真评价[J]. 系统仿真学报, 2026, 38(5): 1426-1439.
[14]	蒋圣超, 裴云庆, 翟宏营, 吴国键, 高放. 基于块编码绝热量子牛顿‒拉夫逊法的潮流计算[J]. 系统仿真学报, 2026, 38(5): 1453-1465.
[15]	秦浪, 谢嘉成, 乔晓军, 王学文, 肖智杰. 执行器位姿异常的机器人轨迹规划调整方法[J]. 系统仿真学报, 2026, 38(5): 1466-1483.