随着卫星通信与遥感技术的飞速发展,人们获取的空间数据量日益增多。如何高效地从大量的空间数据中提取出有用的信息,对空间数据挖掘技术提出了挑战。空间聚类作为是空间数据挖掘的一种重要方法被广泛应用于空间知识的发现。传统的空间聚类算法通常忽略了障碍物等约束条件,而在现实世界中,地形地貌错综复杂、自然条件各异,为空间聚类带来了困难。研究基于障碍约束的空间聚类算法成为当今空间数据挖掘研究的热点之一。 本文对国内外现有的空间聚类算法和障碍约束的空间聚类算法进行了研究与分析。目前基于障碍约束的空间聚类算法大多数是在原有空间聚类算法基础上进行改进而形成的,由于要考虑障碍约束,有些算法受障碍物的大小、形状、数量影响比较大,使聚类精度下降；有些算法则使程序的计算量急剧增加。基于Delaunay三角网的聚类算法具有聚类精度高、用户输入参数少、能发现任意形状簇等优点,代表性的算法是基于Delaunay三角网的AUTOCLUST+障碍聚类算法。但是该算法不能识别密度渐变的簇,且对障碍约束的处理不够灵活,运算量大等缺点。本文针对这些不足,基于Delaunay三角网与AUTOCLUST+的先进思想,提出了一种新的障碍聚类算法-CBDTO算法。该算法将障碍物用一系列障碍三角形表示,这种表示方法不会破坏原三角网的结构,对障碍约束的添加、删除、修改具有较好的灵活性。同时,该算法将Delaunay三角网剖分得到的三角形划分为小三角形、狭长三角形和大三角形,将其作为聚类模型,通过扩展三角形的策略实现空间聚类,使程序的计算量大大减少。经仿真实验,验证了CBDTO算法的有效性。总之,CBDTO算法不但能识别AUTOCLUST+所能识别的簇,而且也能识别AUTOCLUST+不能识别的密度渐变的抽象簇,并且克服了AUTOCLUST+处理障碍约束不灵活、计算量大的缺点。CBDTO算法的研究将为基于空间地形分析的公路选线系统提供有力的算法支持。