GRASS GIS 7 Programmer's Manual  7.5.svn(2017)-r71942
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Topology

by GRASS Development Team (http://grass.osgeo.org)

Vector library topology management

Topology general characteristics:

  • geometry and attributes are stored separately (don't read both if it is not necessary - usually it is not)
  • the format is topological (areas build from boundaries)
  • currently only 2D topology is supported

Topology is written for native GRASS vector format; in case of linked OGR sources (see v.external module), only pseudo-topology (boundaries constructed from polygons) is written.

The following rules apply to the vector data:

  • Boundaries should not cross each other (i.e., boundaries which would cross must be split at their intersection to form distict boundaries). On the contrary, lines can cross each other, e.g. bridges over rivers.
  • Lines and boundaries share nodes only if their endpoints are identical. Lines or boundaries can be forced to share a common node by snapping them together. This is particularly important since nodes are not represented in the coor file, but only implicitly as endpoints of lines and boundaries.
  • Common area boundaries should appear only once (i.e., should not be double digitized).
  • Areas must be explicitly closed. This means that it must be possible to complete each area by following one or more boundaries that are connected by common nodes, and that such tracings result in closed areas.
  • It is recommended that area features and linear features be placed in separate layers. However if area features and linear features must appear in one layer, common boundaries should be digitized only once. For example, a boundary that is also a line (e.g., a road which is also a field boundary), should be digitized as a boundary to complete the area(s), and a boundary which is functionally also a line should be labeled as a line by a distinct category number.

Vector map topology can be cleaned at user level by v.clean command.

Topo file format specification

Topo file is read by Vect_open_topo().

Header

Note: plus is an instance of Plus_head data structure.

NameTypeNumber

Description

plus->Version_Major C1file version (major)
plus->Version_Minor C1file version (minor)
plus->Back_MajorC1supported from GRASS version (major)
plus->Back_MinorC1

supported from GRASS version (minor)

plus->port->byte_orderC1

little or big endian flag; files are written in machine native order but files in both little and big endian order may be readl; zero for little endian

plus->head_sizeL1

header size

plus->with_zC1

2D or 3D flag; zero for 2D

plus->boxD6

Bounding box coordinates (N,S,E,W,T,B)

plus->n_nodes, plus->n_lines, etc.I7

Number of nodes, edges, lines, areas, isles, volumes and holes

plus->n_plines, plus->n_llines, etc.I7

Number of points, lines, boundaries, centroids, faces and kernels

plus->Node_offset, plus->Edge_offset, etc.L7

Offset value for nodes, edges, lines, areas, isles, volumes and holes

plus->coor_sizeL1File size

Body (nodes, lines, areas, isles)

Nodes

For each node (plus->n_nodes):

NameTypeNumberDescription
n_linesI1Number of lines (0 for dead node)
linesIn_linesLine ids (negative id for line which ends at the node)
anglesDn_linesAngle value
n_edgesI1Reserved for edges (only for with_z)
x,yD2Coordinate pair (2D)
zD1Only for with_z (3D)

See P_node data structure.

Lines

For each line (plus->n_lines):

NameTypeNumberDescription
feature typeC10 for dead line
offsetL1Line offset
N1I1Start node id (only if feature type is GV_LINE or GV_BOUNDARY)
N2I1End node id (only if feature type is GV_LINE or GV_BOUNDARY)
leftI1Left area id for feature type GV_BOUNDARY / Area id for feature type GV_CENTROID
rightI1Right area id (for feature type GV_BOUNDARY)
volI1Reserved for kernel (volume number, for feature type GV_KERNEL)

See P_line data structure.

Areas

For each area (plus->n_areas):

NameTypeNumberDescription
n_linesI1number of boundaries
linesIn_linesLine ids forming exterior boundary (clockwise order, negative id for backward direction)
n_islesI1Number of isles
islesIn_islesIsle ids
centroidI1Centroid id

See P_area data structure.

Isles

For each isle (plus->n_isle):

NameTypeNumberDescription
n_linesI1number of boundaries
linesIn_linesLine ids forming exterior boundary (counter-clockwise order, negative id for backward direction)
areaI1Outer area id

See P_isle data structure.

Topology levels

The vector library defines more topology levels (only for level of access 2):

  • GV_BUILD_NONE
  • GV_BUILD_BASE
  • GV_BUILD_AREAS
  • GV_BUILD_ATTACH_ISLES
  • GV_BUILD_CENTROIDS
  • GV_BUILD_ALL

Note: Only the geometry type GV_BOUNDARY is used to build areas. The geometry type GV_LINE cannot form an area.

Topology examples

Points

One point (nodes: 0, lines: 1, areas: 0, isles: 0)

    + L1

Line L1 (see P_line)

line = 1, type = 1 (GV_POINT)

Lines

One line (nodes: 2, lines: 1, areas: 0, isles: 0)


   +----L1----+
   N1         N2

Node N1 (see P_node)

node = 1, n_lines = 1, xyz = 634624.746450, 223557.302231, 0.000000
  line =   1, type = 2 (GV_LINE), angle = -0.436257

Node N2 (see P_node)

node = 2, n_lines = 1, xyz = 638677.484787, 221667.849899, 0.000000
  line =  -1, type = 2 (GV_LINE), angle = 2.705335

Line L1 (see P_line)

line = 1, type = 2 (GV_LINE), n1 = 1, n2 = 2

Areas without holes

Two lines (nodes: 1, lines: 2, areas: 1, isles: 1)

          +N1
         /   \
        /     \
       /       \
      /   +L2   \
     /           \
    -------L1------

Node N1 (see P_node)

node = 1, n_lines = 2, xyz = 635720.081136, 225063.387424, 0.000000
  line =   1, type = 4 (GV_BOUNDARY), angle = -2.245537
  line =  -1, type = 4 (GV_BOUNDARY), angle = -0.842926

Line L1 (see P_line)

line = 1, type = 4 (GV_BOUNDARY), n1 = 1, n2 = 1, left = 1, right = -1

Line L2 (see P_line)

line = 2, type = 8 (GV_CENTROID), area = 1

Area A1 (see P_area)

area = 1, n_lines = 1, n_isles = 0 centroid = 2
  line =  -1

Isle I1 (see P_isle)

isle = 1, n_lines = 1 area = 0
  line =   1

Areas with holes

Three lines (nodes: 2, lines: 3, areas: 2, isles: 2)

             +N1
            / \
           /   \
          /     \
         /       \
        /    +L2  \
       /           \
      /   +N2       \
     /   /\          \
    /   /  \          \
   /   /    \          \
  /    ---L3--          \
 /                       \
------------L1-------------

Node N1 (see P_node)

node = 1, n_lines = 2, xyz = 635720.081136, 225063.387424, 0.000000
  line =   1, type = 4 (GV_BOUNDARY), angle = -2.245537
  line =  -1, type = 4 (GV_BOUNDARY), angle = -0.842926

Node N2 (see P_node)

node = 2, n_lines = 2, xyz = 636788.032454, 223173.935091, 0.000000
  line =   3, type = 4 (GV_BOUNDARY), angle = -2.245537
  line =  -3, type = 4 (GV_BOUNDARY), angle = -0.866302

Line L1 (see P_line)

line = 1, type = 4 (GV_BOUNDARY), n1 = 1, n2 = 1, left = 1, right = -1

Line L2 (see P_line)

line = 2, type = 8 (GV_CENTROID), area = 1

Line L3 (see P_line)

line = 3, type = 4 (GV_BOUNDARY), n1 = 3, n2 = 3, left = 2, right = -2

Area A1 (see P_area)

area = 1, n_lines = 1, n_isles = 1 centroid = 2
  line =  -1
  isle =   2

Area A2 (see P_area)

area = 2, n_lines = 1, n_isles = 0 centroid = 0
  line =  -3

Isle I1 (see P_isle)

isle = 1, n_lines = 1 area = 0
  line =   1

Isle I2 (see P_isle)

isle = 2, n_lines = 1 area = 1
  line =   3

Example 1

A polygon may be formed by many boundaries (several connected primitives). One boundary is shared by adjacent areas.

+--1--+--5--+
|     |     |
2  A  4  B  6
|     |     |
+--3--+--7--+

1,2,3,4,5,6,7 = 7 boundaries (primitives)
A,B = 2 areas
A+B = 1 isle

Example 2

This is handled correctly in GRASS: A can be filled, B filled differently.

+---------+
|    A    |
+-----+   |
|  B  |   |
+-----+   |
|         |
+---------+

A, B = 2 areas
A+B  = 1 isle

In GRASS, whenever an 'inner' ring touches the boundary of an outside area, even in one point, it is no longer an 'inner' ring (isle in GRASS topology), it is simply another area. A, B above can never be exported from GRASS as polygon A with inner ring B because there are only 2 areas A and B and one island formed by A and B together.

Example 3

This is handled correctly in GRASS: Areas A1, A2, and A3 can be filled differently.

+---------------------+
|  A1                 |
+   +------+------+   |
|   |  A2  |  A3  |   |
+   +------+------+   |
|          I1         |
+---------------------+

A1,A2,A3 = 3 areas
A1,A2+A3 = 2 isles

In GRASS, whenever an 'inner' ring does not touch the boundary of an outside area, also not in one point, it is an 'inner' ring (isle). The areas A2 and A3 form a single isle I1 located within area A1. The size of isle I1 is subtracted from the size of area A1 when calculating the size of area A1. Any centroids falling into isle I1 are excluded when searching for a centroid that can be attached to area A1. A1 above can be exported from GRASS as polygon A1 with inner ring I1.

Example 4

v.in.ogr/v.clean can identify dangles and change the type from boundary to line (in TIGER data for example). Distinction between line and boundary isn't important only for dangles. Example:

+-----+-----+
|     .     |
|     .     |
+.....+.....+
|     .     |
|  x  .     |
+-----+-----+

----  road + boundary of one parcel => type boundary
....  road => type line
x     parcel centroid (identifies whole area)

Because lines are not used to build areas, we have only one area/centroid, instead of 4 which would be necessary in TIGER.

Topology memory management

Topology is generated for all kinds of vector types. Memory is not released by default. The programmer can force the library to release the memory by using Vect_set_release_support(). But: The programmer cannot run Vect_set_release_support() in mid process because all vectors are needed in the spatial index, which is needed to build topology.

Topology is also necessary for points in case of a vector network because the graph is built using topology information about lines and points.

The topology structure does not only store the topology but also the 'line' bounding box and line offset in coor file (index). The existing spatial index is using line ID in 'topology' structure to identify lines in 'coor' file. Currently it is not possible to build spatial index without topology.