Design patterns in GIS

Release date:2023-08-21 Update date:2023-08-23 Editor:admin View counts:303


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:

  1. Pattern name: describes a design problem, its solution and consequences

  2. Question: tell when to use the design pattern and explain the problem and its background

  3. Solution: describe the basic elements of the design, their relationships, their respective tasks, and their cooperation with each other

  4. Consequences: describe the results and tradeoffs after applying the design pattern.



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.


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

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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))


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.

  • 1. Geographical Cognition of the Real World
  • 2. The abstraction of the real world
  • 3. Bit world
  • 1. Data meaning and data type
  • 2. Measurement scale of data
  • 3. GIS data quality
  • 1. Map digitization
  • 2. Processing of spatial data entry
  • 1. Computer network technology
  • 2. Distributed geographic information system
  • 3. WebGIS - World Wide Web Geographic Information System
  • 1. Socialization of GIS
  • 2. Other problems of GIS socialization
  • 3. The impact of society on the development of GIS

Powered by TorCMS (