二维Delaunay三角网的任意点删除算法研究.pdfVIP

第 24 卷 　第 6 期 地 理 与 地 理 信 息 科 学 Vol . 24 　No . 6 2008 年 11 月 Geo grap hy and Geo - Information Science November 2008 二维 Delaunay 三角网的任意点删除算法研究 1 ,2 1 1 3 张 　咏 ,刘 长 星 ,董 汉 军 ,赵 奋 军 ( 1. 西安科技大学测绘科学与技术学院 ,陕西 西安 7 10054 ;2 . 中冶成工上海五冶建设有限公司 ,上海 20 1900 ; 3 . 浙江省第七地质大队 ,浙江 丽水 323000) 摘要 :针对 目前基于影响域多边形剖分的点删除算法缺陷 ,提出一种二维 Delaunay 三角网点删除算法 。首先利用 具有拓扑关系的三角网有哪些信誉好的足球投注网站影响多边形 ,并以三角形矢量面积为工具三角剖分影响域多边形 ,最后通过镶嵌优化 后的剖分三角网完成点的删除 ,且满足 Delaunay 法则 。通过测试证明了算法的可靠性和高效性 。 关键词 :不规则三角网;多边形三角剖分 ;点删除;唯一性 中图分类号 :P208 　　文献标识码 :A 　　文章编号 :1672 - 0504 (2008) 06 - 0050 - 04 0 　引言 1 　三角形矢量面积 ( ( ) ( ) 目前国内外有 4 种二维 Delaunay 三角网 Delau 设有向线段 P1 P2 坐标为 x1 ,y1 和 x2 ,y2 , 点 nay Triangular Irregular Network ,DTIN) 的点删除算 P0 (x0 ,y0 ) 为任意点 , P1 P2 与 P0 组成的三角形矢量 ) [ 1 - 3 ] 法 :1 基于凸耳权值的点删除方法 需要计算每个 面积 S 如下 : 凸耳权值 ,挑选具有最小凸耳权值的凸耳 ,交换被删 1 S = ( (y2 - y1 ) (x0 - x1 ) - (y0 - y1 ) (x2 - x1 ) ) ( 1) 2 除点与凸耳所形成四边形的对角线 ,更新多边形的 S 0 ,则 P0 位于有向线段左侧 ; S = 0 ,则 P0 位 凸耳权值 ,直至以被删除点为顶点的三角形个数减 于有向线段或其延长线上 ; S 0 ,则 P0 位于有向线 至 3 个 ,最后合并剩余的 3 个三角形 。文献[2 ,3 ] 以 段右侧 。在应用中只考虑 S 的正负 ,所以简化后的 特征三角形取代凸耳 ,但在特征三角形矢量面积非 三角