基于合成算法的Delaunay三角网生成改进算法

摘要

基于对Delaunay三角网生成算法的研究,在目前较为优秀的合成算法的基础上进行改进,首先改进了凸壳的生成算法,通过利用坐标的最大(小)值所构成的4个点来构建凸壳,达到简化凸壳的生成过程的效果;其次改进了三角形快速定位算法,利用向量间的位置关系来判断点与三角形的位置关系.改进后的算法不仅继承原算法兼顾空间和时间的性能,且执行效率有明显提高,有效的缓解了计算机处理能力无法满足复杂的地形表示之间的矛盾.