点与三角形位置关系对三角网格拓扑的影响

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (14): 189-192.

• 图形、图像、模式识别 • 上一篇下一篇

点与三角形位置关系对三角网格拓扑的影响

徐永安，武杰，梁卫松，陈崚

扬州大学信息工程学院，江苏扬州 225009

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-05-11 发布日期:2011-05-11

Relationship of point and triangle’s influence on topology of Delaunay triangulation

XU Yong’an，WU Jie，LIANG Weisong，CHEN Ling

Information Engineering College，Yangzhou University，Yangzhou，Jiangsu 225009，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-05-11 Published:2011-05-11

摘要/Abstract

摘要： 逐点添加、局部优化的Watson算法和局部变换法是生成大规模离散点集Delaunay三角网格的常用方法。点与三角形位置关系判别和三角形外接圆包含点的测试分别是局部变换法和Watson算法正确生成Delaunay三角网格的重要环节。计算误差会导致点与三角形位置关系以及三角形外接圆包含点的错误判别，从而生成几何拓扑关系不正确的三角网格。采用相对位置坐标可以提高面积坐标和外接圆圆心、半径的计算精度。以等高线地图采集的地形数据为例，用改进的算法生成了包含393 252个离散点的Delaunay三角网格。

关键词: 离散数据, 三角剖分, 网格

Abstract: Watson and local transformation methods which add point by point and local optimization are the popular algorithms of large-scale scattered data Delaunay triangulation.The situation of the new point in a triangle and whether the point is contained in triangle’s circumcircle are important factors of creating correct Delaunay triangulation.Calculation error can lead to the wrong discrimination of the location relationship between point and triangle，the containing relationship of point and triangle’s circumcircles，and then wrong geometric topology triangular mesh is created.A new method is presented that improves the calculation precision of area coordinates and the centre and radius of circumcircle with relative coordinates.Delaunay triangulation of 393，252 points of terrain data which are extracted from contour map is created.

Key words: scattered data, triangulation, mesh

徐永安，武杰，梁卫松，陈崚. 点与三角形位置关系对三角网格拓扑的影响[J]. 计算机工程与应用, 2011, 47(14): 189-192.

XU Yong’an，WU Jie，LIANG Weisong，CHEN Ling. Relationship of point and triangle’s influence on topology of Delaunay triangulation[J]. Computer Engineering and Applications, 2011, 47(14): 189-192.

[1]	夏丹，周睿. 视差图像配准技术研究综述[J]. 计算机工程与应用, 2021, 57(2): 18-27.
[2]	李雨鑫，李悦悦. 面向JIT采购的多目标车辆调度[J]. 计算机工程与应用, 2021, 57(12): 263-272.
[3]	刘文芬，穆晓东，黄月华. 基于多分辨率网格的异常检测方法[J]. 计算机工程与应用, 2020, 56(17): 78-85.
[4]	赵云成，王琳，盛步云，赵飞宇. 综合曲率约束的在线网格模型分割方法研究[J]. 计算机工程与应用, 2020, 56(16): 176-182.
[5]	陈胜发，贾瑞玉. 基于残差和密度网格的簇心自确认聚类算法[J]. 计算机工程与应用, 2020, 56(12): 149-155.
[6]	周琴，程立正. 层适应网格上求解奇异摄动问题的粒子群算法[J]. 计算机工程与应用, 2020, 56(11): 46-50.
[7]	杜丽美，连玮. 高斯投影下的人机交互式物体仿真算法研究[J]. 计算机工程与应用, 2020, 56(11): 185-191.
[8]	杨冬升，凌静. 二维多域弹性问题虚边界无网格伽辽金法分析[J]. 计算机工程与应用, 2019, 55(5): 51-54.
[9]	傅敏，张江龙，刘培刚. 三维环境下交互式点云对象提取方法[J]. 计算机工程与应用, 2019, 55(24): 265-270.
[10]	宋雪雯，吕鑫，王鑫元. 混合式结构下基于网格的位置隐私保护方法[J]. 计算机工程与应用, 2019, 55(23): 92-98.
[11]	王燕，郭元凯. 改进的XGBoost模型在股票预测中的应用[J]. 计算机工程与应用, 2019, 55(20): 202-207.
[12]	牛少章，欧毓毅，凌捷，顾国生. 利用区域划分的多密度快速聚类算法[J]. 计算机工程与应用, 2019, 55(18): 61-66.
[13]	牛少章，欧毓毅，凌捷，顾国生. 基于网格查询的局部离群点检测算法[J]. 计算机工程与应用, 2019, 55(17): 89-94.
[14]	焦越，王慧青，吴煜豪，杨哲. 结合面积度量和误差校正的网格简化算法[J]. 计算机工程与应用, 2019, 55(17): 221-226.
[15]	崔磊1，2，唐丽玉1，2，孙梅1，2，杨怡斐1，2. 面向辐射模拟的叶片模型的网格简化方法[J]. 计算机工程与应用, 2018, 54(8): 183-188.

点与三角形位置关系对三角网格拓扑的影响

Relationship of point and triangle’s influence on topology of Delaunay triangulation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics