Design patterns in GIS
With the wide application of object-oriented technology, software reuse is adopted in more and more development processes. In the process of studying software reuse, the concept of design pattern (Design Pattern) is put forward. The so-called design pattern, simply understood, is a summary of some experience in designing object-oriented software. As Alexander said for the field of architecture, “each pattern describes a problem that happens again and again around us, and it tells you the key to the solution so that you can use the solution thousands of times without having to solve it again.” By using design patterns in the process of software development, we can use the existing design experience to guide software reuse.
A design pattern generally consists of the following four basic parts:
Pattern name: describes a design problem, its solution and consequences
Question: tell when to use the design pattern and explain the problem and its background
Solution: describe the basic elements of the design, their relationships, their respective tasks, and their cooperation with each other
Consequences: describe the results and tradeoffs after applying the design pattern.
E.Gamma提出了23个面向对象的设计模式，这些模式抽象层次较高，可以应用于所有软件的开发过程。在地理信息系统开发中，经常会遇到本领域的特定的一些问题，并且已经形成了有效的解决方案，对其进行归纳总结，形成相应的设计模式，对于GIS软件开发，有着重要的意义。下面遵循E.Gamma的格式给出了一个GIS设计模式范例。
名称：
Filtering and refinement (Filter and Refine)
内容：
The access interface to a spatial database with a large amount of data is defined.
另外的名称：
Spatial index and minimum enclosing rectangle
动机：
In spatial data, a common query operation is spatial retrieval, that is, to get the corresponding figure objects according to a given point or area. In these cases, the system must have fast response speed.
一个最简单的解决办法是依次得到每个地物A:sub:`i`，并计算A:sub:`i`和给定的点（或区域）的空间关系，如果符合条件，则返回该地物对象。这个方法的缺点是显而易见的，首先，它需要对空间数据库中的所有地物进行比较运算；其次，空间关系的计算需要大量浮点运算，直接进行给定点（或区域）和地物的空间关系，速度会很慢。
In order to improve the efficiency of spatial retrieval, there are two solutions. First of all, the minimum outer rectangle (MBR-Minimum Bounding Rectangle) of each figure can be calculated, so that when calculating the spatial relationship, we can first judge by the outer rectangle, and we can rule out the situation that it is impossible to have an intersection or inclusion relationship, and then calculate it according to the conventional algorithm (such as ray algorithm, etc.). Second, considering that after using MBR, every figure still has to be calculated. A:sub:`i` When there are a large number of features, it still takes a long time to find them. One solution to this problem is to divide the spatial range of the database into rectangles, and then calculate and record the features contained or intersected by each rectangle to form a spatial index. In spatial retrieval, the corresponding index block is obtained according to the given point (or region), so that only the features related to the index block can be judged, thus reducing the search time. Usually the first operation is called refinement, and the second operation is called filtering. The following is a brief description of the process based on the administrative division data of China (figure 16-18mura).
Figure 16-18: administrative divisions and corresponding MBR in China
（a） (b)
Figure 16: filtering by spatial index
As shown in figure 16-19, each index block records its corresponding figure, which looks like:
D5 Hubei, Jiangxi, Zhejiang, Taiwan, Hunan, Guangdong, Fujian
C4 Inner Mongolia, Gansu, Shaanxi, Shanxi, Henan, Hubei, Sichuan, Qinghai, Ningxia
Each figure records its minimum enclosing rectangle, as shown in figure 16-18 Mub.
When looking for the feature containing this point according to the given point P (Fig. 16-19mura), we first judge that P is located in the C4 index block, so that we can only judge the relationship between P and the corresponding figure of the C4 index block; then from the outer rectangle, we can get that P can only be in Sichuan Province or Shaanxi Province (Fig. 16-19murb), and then we can use the traditional spatial relation calculation method to get the exact result-Sichuan Province.
应用：
Filtering and refinement can be applied to base points or regions to retrieve spatial databases with large amounts of data (points, PAM-Point Access Method; regions, SAM-Spatial Access Method), and spatial databases are composed of lines or polygons.
结构：
Figure 16-20: filtering and refinement pattern structure diagram
Participants:
FeatureSet: defines a spatial database made up of geographic features.
Feture: implements the figure object.
SpatialIndex: manage and maintain the spatial index, get the corresponding figure of each index block, and provide filtering function.
The minimum outer rectangle of MBR:: figures, which can be refined through MBR.
Partition: corresponds to each rectangular region after spatial data segmentation.
Collaboration: FeatureSet uses SpatialIndex to get a set of figure objects that may meet the conditions, and then uses MBR to remove features that are absolutely impossible to meet the conditions. Any editing and modification involving spatial coordinates in the spatial database will recalculate the MBR and maintain the spatial index. In the case of low precision, the minimum outsourced rectangle can be used to establish the spatial index.
Consequence: obviously, filtering and refinement increases memory overhead because spatial indexes and minimum outsourced rectangles are to be recorded. The determination of index block is an important factor, if it is too small, there will be a large number of features across more than one index block, further increasing the amount of data; and if too large, the effect of filtering will not be very obvious. If the spatial distribution of ground features is uneven, it is generally necessary to use uneven segmentation strategies, such as quadtree and so on. In addition, in order to ensure the correctness of the query results, each editing and modification of the figure has to recalculate its minimum outer rectangle and maintain the spatial index, which requires additional time overhead and increases the complexity of the program. Taking into account the above factors, for the case of small amount of data, generally do not establish a spatial index. Because the structure of point geographic elements is simple, the amount of data is small, and the spatial relationship is easy to calculate, the spatial index is generally not established for the data composed of point objects, and for a single point, the minimum outsourced rectangle is also meaningless.
Change: in order to improve the search efficiency, spatial indexes based on tree data structures such as quadtree and balanced binary tree can be established. The minimum outer right-angle polygon can be used instead of the minimum outer rectangle, the former can better approach the shape of geometric entities and improve the efficiency of refinement, but it needs more storage space and has a large amount of computation.
Implementation: the following is a filtering and refined spatial retrieval process described in C++ language. For simplicity, only point-based access (PAM) is given, where the FeatureSetclass represents a spatial database composed of geographical elements, the member variable m_ SpatialIndex of FeatureSet is its spatial index, and the method GetObjectsUsingPAM of the FeatureSet class aims to get a list of qualified features based on a given point. The Feature class represents geographic features, and the member variable m_ rectMBR of the Feature class is its minimum enclosing rectangle.
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 iTunes 0; I < nFeaturesCount; iTunes +) {
PFeature = (Feature*) arRelativeFeatures.GetAt (I)
If (! pFeature- > m_ rectMBR.IsPointContained (ptPoint))
Continue
If (pFeature- > IsRelationshipFitted (ptPoint))
ArFeatures- > Add (pFeature)
}
}
In a broad sense, a design pattern can be an algorithm or a data structure, but in practice, a pattern is generally made up of a set of collaborative classes that can accomplish specific tasks. In the process of GIS software development, using formal and semi-formal language to record design patterns can better guide software reuse and improve software productivity.