地形可视性分析是运用计算机几何原理和计算机图形学技术解决地形上观察点集合和目标点集合之间的可视性问题,是地理空间分析的一个重要组成部分。多点可视域问题是地形可视性分析中的一类重要问题,在军事、城市规划、濒危动物保护等领域有着广泛的应用。观察点设置问题又是多点可视域问题的一种,该问题一般抽象为在一个给定地形上选择最少数量的视点使得它们所覆盖的联合视域最大。因此,观察点设置问题是一个组合优化问题,对其求解也是一个NP问题。而且,随着计算机技术和遥感技术的快速发展,获得的地形数据的精度越来越高,地形特征点的数量自然越来越大,即使采用这些地形特征点作为候选视点的数量也是相当多的。因此,如何有效和快速求解观察点设置问题是一个难点和热点问题。本文基于此,开展以下研究工作。1、提出了分别针对山顶点、山脊点和平地点的地形特征点提取方法提取地形特征点作为候选视点是观察点设置问题的基础,地形特征点提取效果的好坏直接影响最后保留的观察点的覆盖率。本文分别针对山顶点、山脊点和平地点,提出了相应的特征点提取方法及算法。对于山顶点,本文在反地形上利用地表水流模拟方法来提取,在反地形的洼地区域中积水量最多或者高程最小的点即为原始地形中的山顶点。对于山脊点,本文在反地形上利用地表水流模拟法获得汇水线,然后可以得到原始地形上的分水线,在分水线上的地形点就是山脊点。对于平地点,本文对判断为平地的区域进行区域划分,然后在在划分的每个子区域内选取中心点作为候选点。实验表明,将该方法提取的地形特征点作为候选视点,最后保留的观察点的联合视域覆盖率更高。2、提出了一种基于聚类的多点可视域候选视点快速过滤方法首先,本文将挑选的地形特征点作为候选视点,然后对这些地形特征点用kmeans算法进行聚类,接着把属于每个簇类中的视点按照一定的视域贡献率进行排序,最后利用过滤算法去除视域贡献率低的视点。通过逐步过滤,视域贡献率高的视点会被保留,直到满足要求的视点数目为止。实验结果表明,与RPF(Region Partitioning for Filtering)算法和模拟退火算法相比,本文所提出的快速过滤算法在计算效率和覆盖率方面都有很大的提高。3、提出了视点过滤算法的并行化设计方法在视点过滤算法中,视点过滤前需要先将候选视点进行k-means聚类,并依次在每个簇内对视点按其视域贡献率进行排序等处理过程,需要花费较多的时间。因此,本文采用MPI并行化程序框架将k-means算法进行并行化设计,并用Open MP对候选视点排序过程进行并行化设计。在地形点过滤操作中,当某一视点被移动到另一簇中时,需要重新计算视点视域贡献率且计算量相对较大,考虑将各个视点的视域用Open MP并行化计算,能够提高计算效率。实验结果表明,视点过滤的并行化设计方法能够很大程度减少计算时间。