约束Delaunay三角化在路线设计中的应用及其生成算法研究

综合分析了 CDT在路线设计中的应用 ,并提出了相应的解决方案。深入研究了适合各种应用的 CDT构建算法 ,即先不考虑约束条件构建初级标准 DT,再将约束边嵌入初始 DT中的两步法。标准 DT的构建采用改进和优化后的逐点插入算法 ,通过建立网格索引 ,实现数据的高效组织和管理 ,再结合方向搜索技术 ,研究出了三角形的快速定位算法。采用 WATSON的“数据相关三角形”算法优化构网 ,为减少优化时间 ,提出了按网格轮流取点的策略。实践证明 ,该算法具有速度快、网形优、精度高、用途广的特点。