In this chapter a topological data structure will be shown, which describes the polygon topology. Due to the structure of it, adjacency can be handled and stored.

To make the self-test successfully

As described, topological storage consists of points, arcs and polygons. The major question is how we can store objects with their relative relational information with each other such as neighbourhood integrated into the data structure. By using the relational model, the correctness of topological structure is not self-maintained (using software that enforces the topological correctness from users and avoids topological errors).

A topological data structure must contain the following steps:

- storing the topological relationship of geometrical elements
- enforcing correctness on data, such as avoiding gaps between polygons (exception can be city borders, intersection, etc.)
- storing embedded polygon relations, which may occur quite frequently on maps (e.g. an island in a lake)
- storing additional information on geometry data (colour of a polygon, linestring represented as dashed lines, etc.)
- able to answer topological queries like the location of a point, which objects are intersected by a polyline, neighbours of a polygon, embedded polygons, etc.

Geometry types are points, linestrings and polygons; therefore, layers can be defined according to their type. As mentioned above, it is sufficient to store a unique identifier and coordinates of a point. A point may represent a standalone entity of an information system, not only representing an element of a compound geometrical object. In the case of independent entities, the graphical representation of points is carrying thematic content. Graphical representations are usually described by a predefined graphical symbol, which is selected from a table of symbols or a collection of representations (legend).

It is practical to describe polylines with graphs, where the vertices are points forming linestrings, and the arcs are representing connection between each node. Graphical styles can be assigned to each linestring (bold, dashed, multi-parallel lines), although the graphical representation does not touch the position of nodes forming linestrings.

Polygons are represented by compound structured graphs, namely simple graphs. A simple graph consists of three element types: area, edge and junction point. An area represents the actual area of a polygon, edges are representing the borderlines between polygons, while junction points are representing the crossing points of polylines (see described by relational tables in Figure 31).

Planar structures are stored in two graphs. One of the graphs stores the junction points, and the edges between junction points are represented by polylines. Edges are also storing which areas are on the right and left hand sides relatively. Let us call it a simple graph (Figure 32.)

Figure 32. An example of simple graph. On the left hand side polygons are displayed, on the right hand side areas defined by a simple graph.

Figure 33. Dual graph of the simple graph displayed in Figure 32 and extended by inclusion areas for the dual graph.

The other graph is the dual of the simple graph, where the nodes are vertices, and the edges are representing neighbour relation of an area. An area contains its surrounding polylines; namely, the polygon itself is representing the area. One of the purposes of a dual graph along with a simple graph is to represent the topological relation between polygons and their geometries. Neighbourhood questions can be easily answered (however, with current structure, we cannot store embedded areas).

Let us define beside real areas a new type, the inclusion areas. These areas, however, cannot be represented as separate polygons in reality. It is an inclusion area, a contour for a set of polygons, where every element can be reached with a simple graph on its dual graph (Figure 33). The outermost inclusion area is the contour of a polygon-structure, namely, the uppermost level of an area, whereas a hole with a real polygon inside on other levels.

Real and inclusion graphs can be ordered in hierarchy and represented with graphs. A root element is the image's contour denoted by a bounding box, and its children are those polygons that can be reached by the root element in a dual graph. Hence, for each real area we have defined a bounding box; on the other hand, beside the image's bounding box, every bounding box contains at least a real area.

Figure 34. A real and bounding area with contour style. Real areas are denoted by letters, while inclusion areas are denoted by numbers. An inclusion graph is represented on the right hand side of the figure.

Within an inclusion tree the contour of the whole area is represented in the root node. On even ordinality levels the inclusion contours are displayed, whereas on odd ordinality levels the real areas are displayed. An inclusion area may have many children, which can be reached by dual graph traversal algorithms. An inclusion graph is not stored on a separate data structure: it has been extended by a dual graph, where spatial relations are stored. Let us look at Figure 34, where the polygon area C contains subpolygons, which are areas (D and E); therefore, contour C is the inclusion area corresponding to polygons D and E. An inclusion area is represented in the dual graph in such a way that each of its neighbour polygons are located on the edge of the included set of polygons. For each area, we also store whether it is an inclusion area or real area.

In the case of real areas, they also store the list of edges with negative direction of traversal. In the case of an inclusion area, directed border edges with positive traverse order and the list of included areas are stored. In a simple graph, there were areas only at one side of the edge, however, data related to the included areas will be set to the other side too. An edge in a simple graph and in a dual graph are identical in the way that the edges of a simple graph are representing a border between two different areas in a dual graph.

Since edges are identical in simple and dual graphs, the duplication is not allowed. In a dual graph, edges are inserted in the way that only its left and right neighbour areas are stored. This method leads to simple usage when changing from simple to dual graph; on the other hand, changes made on a linestring are presented on both graphs, which leads to the correctness of the topological order, and the errors are naturally avoided. Dual graph representations are resulting topological data structure.

On a simple graph, edges are non-directed, although both directions are stored over edges because it is easier to build a polygon when both directions are present. The points are represented by coordinates and the outgoing edges in clockwise order. By default, edges do not store their direction; however, we can add directions to them, where the start and end point identifiers as well as the identifiers of the left and right areas are stored. If the left or right areas are missing, the identifier of the contour area is used. In addition, the polyline related to the edge is stored as well.

The advantage of this data structure is that it supports all the major functionalities and is topologically correct. In the next section we will discuss the preparation of this data structure.

A Társadalominformatika: moduláris tananyagok, interdiszciplináris tartalom- és tudásmenedzsment rendszerek fejlesztése az Európai Unió támogatásával, az Európai Szociális Alap társfinanszírozásával, az ELTE TÁMOP 4.1.2.A/1-11/1-2011-0056 projekt keretében valósult meg.

Generated with ELTESCORM framework