GIS中的设计模式

随着面向对象技术的广泛应用,软件复用在越来越多的开发过程中被采用。在研究软件复用的过程中,设计模式(Design Pattern)的概念被提了出来。所谓设计模式,简单地理解,是一些设计面向对象的软件的经验总结。正如Alexander针对建筑领域所说的:“每个模式描述了一个在我们身边一再发生的问题,它告诉你这个问题的解的关键,以使你可以成千上万次的利用这个解,而不需要再一次去解它。”,在软件开发过程中使用设计模式,可以利用已有的设计经验,指导软件复用。

一个设计模式,一般包括以下四个基本部分:

1)模式名称:描述一个设计问题、它的解法和后果;

2)问题:告诉什么时候要使用该设计模式,解释问题及其背景;

3)解决方案:描述设计的基本要素、它们的关系、各自的任务以及相互之间的合作;

4)后果:描述应用设计模式之后的结果和权衡。

E.Gamma提出了23个面向对象的设计模式,这些模式抽象层次较高,可以应用于所有软件的开发过程。在地理信息系统开发中,经常会遇到本领域的特定的一些问题,并且已经形成了有效的解决方案,对其进行归纳总结,形成相应的设计模式,对于GIS软件开发,有着重要的意义。下面遵循E.Gamma的格式给出了一个GIS设计模式范例。

名称:

过滤和精化(Filter and Refine)

内容:

定义了对一个大数据量的空间数据库的访问接口

另外的名称:

空间索引和最小外包矩形

动机:

在空间数据中,一个通常的查询操作是空间检索,即根据给定的点或者区域得到相应的地物对象,在这些情形中,系统必须要有快的响应速度。

一个最简单的解决办法是依次得到每个地物A:sub:`i`,并计算A:sub:`i`和给定的点(或区域)的空间关系,如果符合条件,则返回该地物对象。这个方法的缺点是显而易见的,首先,它需要对空间数据库中的所有地物进行比较运算;其次,空间关系的计算需要大量浮点运算,直接进行给定点(或区域)和地物的空间关系,速度会很慢。

为了提高空间检索效率,有两个解决的途径。首先,可以计算每个地物的最小外包矩形(MBR-Minimum Bounding Rectangle),这样进行空间关系计算时,可以先通过外包矩形来判断,可以排除掉根本不可能具有相交或者包含关系的情形,然后再按照常规的算法(如射线算法等等)进行计算。其次,考虑到采用MBR之后,仍旧要计算每一个地物A:sub:`i`,当地物数目很多时,依然需要较长的查找时间。解决该问题的一个方案是将数据库的空间范围进行分割,一般是划分成为矩形,然后计算并记录每个矩形包含或者相交的地物,形成空间索引。在进行空间检索时,根据给定的点(或区域)得到其对应的索引块,这样就可以只判断与索引块相关的地物,从而减少了查找时间。通常前一个操作称为精化,后一个操作叫做过滤。下面以中国行政区划数据(图16-18-a)简单描述该过程。

../../_images/img_116.png

图16-18:中国行政区划和对应的MBR

(a) (b)

../../_images/img_27.png

图16:通过空间索引进行过滤

如图16-19-a所示,每一索引块都记录了其相应的地物,形如:

D5湖北,江西,浙江,台湾,湖南,广东,福建

C4内蒙古,甘肃,陕西,山西,河南,湖北,四川,青海,宁夏

而每个地物都记录其最小外包矩形,如图16-18-b所示。

当根据给定点P(图16-19-a)查找包含该点的地物时,首先判断P位于C4索引块,这样就可以只判断P与C4索引块对应地物的关系;再由外包矩形,可以得到P只可能在四川省或陕西省内(图16-19-b),然后就可以采用传统的空间关系计算方法,得到确切的结果——四川省。

应用:

过滤和精化可以应用于根据点或者区域对大数据量的空间数据库的检索(点,PAM-Point Access Method;区域,SAM-Spatial Access Method),而空间数据库由线或多边形地物组成。

结构:

../../_images/img_35.png

图16-20:过滤和精化模式结构图

参与者:

  • FeatureSet:

——定义由地理要素组成空间数据库。

  • Feture:

——实现了地物对象。

  • SpatialIndex:

——管理和维护空间索引,可以得到每一索引块对应的地物,提供过滤功能。

  • MBR:

——地物的最小外包矩形,通过MBR可以实现精化功能。

  • Partition:

——对应于空间数据分割后的每一块矩形区域。

协作:

FeatureSet利用SpatialIndex得到可能符合条件的地物对象集合,然后利用MBR去除绝对不可能满足条件的地物。

对空间数据库的任何涉及空间坐标的编辑修改都要重新计算MBR和维护空间索引,在要求精度较低的情况下,可以利用最小外包矩形建立空间索引。

后果:

很明显,因为要记录空间索引和最小外包矩形,采用过滤和精化增加了内存开销。索引块的确定是一个重要的因素,如果太小,会有大量地物跨越多于一个的索引块,进一步增加了数据量;而如果太大,过滤的效果不会很明显。如果地物的空间分布不均匀,一般要采用不均匀的分割策略,如四叉树等等。此外,为了保证查询结果的正确性,对地物的每一次编辑修改,都要重新计算其最小外包矩形,并维护空间索引,这需要额外的时间开销,并增加了程序的复杂度。考虑到上述因素,对于数据量较小的情形,一般不建立空间索引。因为点地理要素结构简单,并且数据量小,并且容易计算空间关系,所以对于由点地物对象构成的数据,一般不建立空间索引,并且对于单个点而言,最小外包矩形也是没有意义的。

变化:

为了提高查找效率,可以建立基于四叉树、平衡二叉树等基于树数据结构的空间索引。

可以使用最小外包直角多边形代替最小外包矩形,前者更好地逼近几何实体的形状,提高了精化的效率,但是需要更多的存储空间,并且计算直角多边形运算量较大。

实现:

下面是采用C++语言描述的采用过滤和精化的空间检索过程,为了简便起见,只是给出了基于点的访问(PAM),其中FeatureSet类表示由地理要素组成的空间数据库,FeatureSet的成员变量m_SpatialIndex为其空间索引,FeatureSet类的方法GetObjectsUsingPAM目的是根据给定的点得到符合条件地物的列表;Feature类表示地理要素,Feature类的成员变量m_rectMBR为其最小外包矩形。

void FeatureSet::GetObjectsUsingPAM(Point ptPoint,Array *arFeatures) const {

Partition *pPartition = GetRelativePartition(ptPoint);

Array arRelativeFeatures;

int nFeaturesCount =

m_SpatialIndex->FindFeatures(pPartition,&arRelativeFeatures);

Feature *pFeature;

for(int i=0 ; i<nFeaturesCount; i++) {

pFeature = (Feature *)arRelativeFeatures.GetAt(i);

if(!pFeature->m_rectMBR.IsPointContained(ptPoint))

continue;

if(pFeature->IsRelationshipFitted(ptPoint))

arFeatures->Add(pFeature);

}

}

广义上讲,一个设计模式可以是一个算法、一种数据结构,但是在实践中,模式一般由一组协作的类构成,可以完成特定的任务。在地理信息系统软件开发过程中,利用形式化、半形式化的语言来记录设计模式,可以较好地指导软件复用,提高软件生产率。