Topology

Table of Contents

• Vector library topology management
  • Topo file format specification
    • Header
    • Body (nodes, lines, areas, isles)
  • Topology levels
  • Topology examples
  • Topology memory management

by GRASS Development Team (https://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.

Name	Type	Number	Description
plus->Version_Major	C	1	file version (major)
plus->Version_Minor	C	1	file version (minor)
plus->Back_Major	C	1	supported from GRASS version (major)
plus->Back_Minor	C	1	supported from GRASS version (minor)
plus->port->byte_order	C	1	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_size	L	1	header size
plus->with_z	C	1	2D or 3D flag; zero for 2D
plus->box	D	6	Bounding box coordinates (N,S,E,W,T,B)
plus->n_nodes, plus->n_lines, etc.	I	7	Number of nodes, edges, lines, areas, isles, volumes and holes
plus->n_plines, plus->n_llines, etc.	I	7	Number of points, lines, boundaries, centroids, faces and kernels
plus->Node_offset, plus->Edge_offset, etc.	L	7	Offset value for nodes, edges, lines, areas, isles, volumes and holes
plus->coor_size	L	1	File size

Body (nodes, lines, areas, isles)

Nodes

For each node (plus->n_nodes):

Name	Type	Number	Description
n_lines	I	1	Number of lines (0 for dead node)
lines	I	n_lines	Line ids (negative id for line which ends at the node)
angles	D	n_lines	Angle value
n_edges	I	1	Reserved for edges (only for with_z)
x,y	D	2	Coordinate pair (2D)
z	D	1	Only for with_z (3D)

See P_node data structure.

Lines

For each line (plus->n_lines):

Name	Type	Number	Description
feature type	C	1	0 for dead line
offset	L	1	Line offset
N1	I	1	Start node id (only if feature type is GV_LINE or GV_BOUNDARY)
N2	I	1	End node id (only if feature type is GV_LINE or GV_BOUNDARY)
left	I	1	Left area id for feature type GV_BOUNDARY / Area id for feature type GV_CENTROID
right	I	1	Right area id (for feature type GV_BOUNDARY)
vol	I	1	Reserved for kernel (volume number, for feature type GV_KERNEL)

See P_line data structure.

Areas

For each area (plus->n_areas):

Name	Type	Number	Description
n_lines	I	1	number of boundaries
lines	I	n_lines	Line ids forming exterior boundary (clockwise order, negative id for backward direction)
n_isles	I	1	Number of isles
isles	I	n_isles	Isle ids
centroid	I	1	Centroid id

See P_area data structure.

Isles

For each isle (plus->n_isle):

Name	Type	Number	Description
n_lines	I	1	number of boundaries
lines	I	n_lines	Line ids forming exterior boundary (counter-clockwise order, negative id for backward direction)
area	I	1	Outer 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.