建立结点上弧－弧拓扑关系的Qi算法

建立结点上弧－弧拓扑关系的Ｑｉ算法齐华，刘文熙（成都西南交通大学，６１００３１）１引言在地理信息系统中，“自动生成多边形拓扑关系”是一个使用频率很高的过程。如何优化算法来提高这个过程的时间效率是一个十分有意义的问题。对于这个过程的研究引起了学者们的关...

基于Qi算法的Delaunay三角网逐点插入法

Delaunay三角网在很多领域都有着广泛的应用,快速高效地生成Delaunay三角网十分重要。逐点插入法是构建Delaunay三角网中使用最广泛的方法之一。本文深入研究了使用逐点插入法构建不带约束条件Delaunay三角网的过程。在使用该方法生成Delaunay三角网中建立结点拓扑关系这一影响构网效率的关键步骤中引入了Qi算法,简化了该方法生成Delaunay三角网的复杂度。然后在向Delaunay三角网内插入约束边的过程中,再次引入Qi算法,从而提高了构网的效率。为了验证上述模型,我们在Microsoft Visual Studio 2005开发环境下,以C#为开发工具,采用底层开发模式实现了改进的逐点插入法,实验证明引入Qi算法能够提高逐点插入法Delaunay三角网构建及插入约束边的效率。

确定射线空间相邻关系的两个非角度算法的时间复杂度分析

以建立节点上弧段之间的拓扑关系为例 ,对比分析了两个非角度算法在确定射线的空间相邻关系时的时间复杂度 ,探讨了进一步将应用范围拓展到确定点集的空间关系时两种算法的有效性。研究表明 ,在这一类空间分析中基于Qi(xi,yi)函数的Qi 算法是一个时间复杂度低。

快速插入排序法

设法用减少插入序列长度的办法,提出一种快速插入的排序方法。给出了算法思想、算法描述、算法分析和实验结果。其理论意义是改进了插入排序法的时间复杂度,其实用价值是该排序法的排序效率比直接插入排序法提高43％左右。

拓扑自动生成系统的设计与实现

本文阐述了拓扑自动生成的基本原理和采用左转算法和ＱＩ算法相结合追踪连通边界的方法，简要介绍了系统的基本功能。