Geografic-Information-System/lib/vector/vectorlib.dox

/*! \page vectorlib GRASS Vector Library

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

<b>Table of contents</b>

- \subpage background
- \subpage intro
 - \subpage vector_map
  - \subpage directory_structure
  - \subpage head_file_format
 - \subpage categories_layers
 - \subpage attributes
  - \subpage dbln_file_format
- \subpage vlibs
- \subpage vlib_structures
 - \subpage Map_info
 - \subpage Plus_head
 - \subpage dig_head
- \subpage feature_geom
 - \subpage ftypes
 - \subpage coor_file_format
  - \subpage coor_file_head
  - \subpage coor_file_body 
- \subpage topology_management
 - \subpage topo_file_format
  - \subpage topo_file_header
  - \subpage topo_file_body
 - \subpage topo_levels
 - \subpage topo_examples
 - \subpage topo_memory
- \subpage spidx
 - \subpage sidx_file_format
- \subpage cidx
 - \subpage cidx_file_format
  - \subpage cidx_file_head
- \subpage tin
- \subpage ogr_iface
 - \subpage frmt_file_format
 - \subpage fidx_file_format
- \subpage grassdglib
- \subpage ascii

- \subpage vlibfunc

- \subpage authors

- \subpage references

- \subpage seealso


\section background Background

Generally, the vector data model is used to describe geographic
phenomena which may be represented by geometric entities like points,
lines, and areas. The GRASS vector data model includes the description
of topology, where besides the coordinates describing the location of
the primitives (points, lines, boundaries, centroids, faces, and
kernels), their spatial relations are also stored. In general,
topological GIS requires a data structure where the common boundary
between two adjacent areas is stored as a single line, simplifying the
vector data maintenance.


\section intro Introduction

The GRASS 6/7 vector format is very similar to the previous GRASS 4.x
(5.0/5.3) vector format.

This description covers the new GRASS 6 vector library architecture.
This new architecture overcomes the vector limitations of GRASS
4.x-5.4.x by extending the vector support with attributes stored in
the external relational databases, and by new 3D capabilities. Besides
internal file based storage the geometry may alternatively be stored
in a PostGIS database (accessible via OGR interface). This enables
users to maintain large data sets with simultaneous write
access. External GIS formats such as SHAPE-files may be used directly,
without requiring format conversion.

The current implementation includes:   

- <b>multi-layer</b>: features in one vector map may represent more
    layers and may be linked to more external tables (see \ref
    categories_layers);
- 2D and 3D vector geometry with full topology support for 2D and
  partial topology support for 3D (see \ref topology_management);
- <b>multi-format</b>: external data formats supported (SHAPE-file,
  OGR sources etc.);
- <b>portability</b>: platform independent internal format, read- and
      writable on 32bit, 64bit etc. computer architectures;
- integrated \ref dglib - support for vector network analysis;
- <b>spatial index</b>: based on R-tree method for fast vector
  geometry access (see \ref spidx);
- <b>multi-attribute</b>: attributes saved in external Relational
      Database Management System (RDBMS) connected through DBMI
      library and drivers (\ref attributes);


\subsection vector_map Vector map

GRASS vector maps are stored in an <em>arc-node</em> representation,
consisting of curves called arcs. An arc is stored as a series of
x,y,z coordinate pairs. The two endpoints of an arc are called
<em>nodes</em>. Two consecutive x,y,z pairs define an arc segment. The
user specifies the type of input to GRASS; GRASS doesn't decide. GRASS
allows for the feature definition which allows for multiple types to
co-exist in the same map. Centroid are assigned to area it is
within/inside (geometrically). An area is identified by an x,y,z
centroid point geometrically inside with a category number (ID). This
identifies the area. Such centroids are stored in the same binary
'coor' file with other primitives. Each element may have none, one or
more categories (cats). More cats are distinguished by field number
(field, called "layer" at user level).  Single and multi-category
support on modules level are implemented. Z-coordinate is optional and
both 2D and 3D files may be written.

The following vector features are defined (see \ref ftypes):

- point: a point;
- line: a directed sequence of connected vertices with two endpoints called nodes;
- boundary: the border line to describe an area;
- centroid: a point within a closed boundary;
- area: the topological composition of centroid and boundary;
- face: a 3D area;
- kernel: a 3D centroid in a volume;
- volume: a 3D corpus, the topological composition of faces and kernel.

Note that all lines and boundaries can consist of multiple segments.

Topology also holds information about isles. Isles are located within an area, not
touching the boundaries of the outer area. Isles consist of one or more areas
and are used internally by the vector libraries to maintain correct topology of areas.

\subsubsection directory_structure Directory structure

Vector map is stored in a number of data files. Vector map directory
structure and file names were changed in GRASS 6 with respect to
previous GRASS versions. All vector files for one vector map are
stored in one directory:

\verbatim
$MAPSET/vector/vector_name/
\endverbatim

This directory contains these files:

- <b>coor</b> - binary file, coordinates [former dig/ file] (see \ref coor_file_format)
- <b>topo</b> - binary file, topology [former dig_plus/ file] (see \ref topo_file_format)
- <b>sidx</b> - binary file, spatial index (see \ref sidx_file_format)
- <b>cidx</b> - binary file, category index (see \ref cidx_file_format)
- <b>head</b> - text file, header information [former part of dig/ file] (see \ref head_file_format)
- <b>dbln</b> - text file, link(s) to attribute table(s) (see \ref dbln_file_format)
- <b>hist</b> - text file, vector map change history
- <b>frmt</b> - text file, format description (external format only)
- <b>fidx</b> - binary file, feature index (OGR format only)

\subsubsection head_file_format Head file format specification

The header contains historical information, a description of the
vector map and many other information. The file is an unordered list
of key/value entries. The <i>key</i> is a string separated from
<i>value</i> by a colon and optional whitespace. Keywords are:

<table border="1" style="border-collapse: collapse">
<tr><td>ORGANIZATION</td><td>organization that digitized the data</td></tr>
<tr><td>DIGIT DATE</td><td>date the data was digitized</td></tr>
<tr><td>DIGIT NAME</td><td>person who digitized the data</td></tr>
<tr><td>MAP NAME</td><td>title of the original source map</td></tr>
<tr><td>MAP DATE</td><td>date of the original source map</td></tr>
<tr><td>MAP SCALE</td><td>scale of the original source map</td></tr>
<tr><td>OTHER INFO</td><td>other comments about the map</td></tr>
<tr><td>ZONE</td><td>zone of the map (e.g., UTM zone)</td></tr>
<tr><td>MAP THRESH</td><td>digitizing threshold</td></tr>
</table>

\subsection categories_layers Categories and layers

<i>Note: "layer" was called "field" in earlier version.</i>

In GRASS, a "category" or "category number" is a vector feature ID
used to link geometry to attributes which are stored in one or several
(external) database table(s). This category number is stored into the
vector geometry as well as a "cat" column (integer type) in each
attribute database table. The category number is used to lookup an
attribute assigned to a vector object. At user level, category numbers
can be assigned to vector objects with the <tt>v.category</tt> command.

In order to assign multiple attributes in different tables to vector
objects, each map can hold multiple category numbers. This is achieved
by assigning more than one "layer" to the map (<tt>v.db.connect</tt>
command). The layer number determines which table to be used for
attribute queries. For example, a cadastrial vector area map can be
assigned on layer 1 to an attribute table containing landuse
descriptions which are maintained by department A while layer 2 is
assigned to an attribute table containing owner descriptions which are
maintained by department B.

Each vector feature inside a vector map has zero, one or more
&lt;layer,category&gt; tuple(s). A user can (but not must) create
attribute tables which are referenced by the layer, and rows which are
essentially referenced by the &lt;layer,category&gt; pair.

Categories start with 1 (category '0' is allowed for OGR
layers). Categories do not have to be continuous.

\subsection attributes Attributes

The old GRASS 4.x 'dig_cats' files are not used any more and vectors'
attributes are stored in external database. Connection with the
database is done through drivers based on \ref dbmilib. Records in a
table are linked to vector entities by layer and category number. The
layer identifies table and the category identifies record.  I.e., for
any unique combination

\verbatim
map+mapset+layer+category
\endverbatim

there exists one unique combination

\verbatim
driver+database+table+row
\endverbatim

Information about database links holds <tt>dblinks</tt> structure.

\code
struct dblinks
{
    struct field_info *field;   /* pointer to the first field_info structure */
    int alloc_fields;           /* number of allocated slots */
    int n_fields;               /* number of available fields */
};
\endcode

The general DBMI settings are defined in the '$MAPSET/VAR' text file
(maintained with <tt>db.connect</tt> command at user level).

\subsection dbln_file_format Dbln file format specification

Each vector maps has its own DBMI settings stored in the
'$MAPSET/vector/vector_name/dbln' text file. For each pair <b>vector map +
layer</b>, all of <b>table, key column, database, driver</b> must be
defined in a new row. This definition must be written to
'$MAPSET/vector/vector_name/dbln' text file. Each row in the 'dbln'
file contains names separated by spaces in following order ([ ] -
optional):

\verbatim
map[@mapset] layer table [key [database [driver]]]
\endverbatim

If key, database or driver are omitted (on second and higher row only)
the last definition is used. When reading a vector map from another
mapset (if mapset is specified along with map name), definitions in
the related "dbln" file may overwrite the DBMI definition in the
current mapset. This means that the map-wise definition is always
"stronger".

Wild cards <b>*</b> and <b>?</b> may be used in map and mapset names.

Variables $GISDBASE, $LOCATION_NAME, $MAPSET, and $MAP may be used in
table, key, database and driver names (function
Vect_subst_var()). Note that $MAPSET is not the current mapset but
mapset of the map the rule is defined for.

Note that vector features in GRASS vector maps may have attributes in
different tables or may be without attributes. Boundaries form areas
but it may happen that some boundaries are not closed (such boundaries
would not appear in polygon layer).  Boundaries may have
attributes. All types may be mixed in one vector map.

The link to the table is permanent and it is stored in 'dbln' file in
vector directory. Tables are considered to be a part of the vector and
the command <tt>g.remove</tt>, for example, deletes linked tables of
the vector. Attributes must be joined with geometry.

<b>Examples:</b>

Examples are written mostly for the DBF driver, where database is full
path to the directory with dbf files and table name is the name of dbf
file without .dbf extension:

\verbatim
* 1 mytable id $GISDBASE/$LOCATION_NAME/$MAPSET/vector/$MAP dbf
\endverbatim

This definition says that entities with category of layer 1 are linked
to dbf tables with names "mytable.dbf" saved in vector directories of
each map. The attribute column containing the category numbers is
called "id".

\verbatim
* 1 $MAP id $GISDBASE/$LOCATION_NAME/$MAPSET/dbf dbf
\endverbatim 

Similar as above but all dbf files are in one directory dbf/ in mapset
and names of dbf files are $MAP.dbf

\verbatim
water* 1 rivers id /home/grass/dbf dbf
water* 2 lakes lakeid /home/guser/mydb
trans* 1 roads key basedb odbc
trans* 5 rails
\endverbatim

These definitions define more layers (called "field" in the API) for
one vector map i.e. in one vector map may be more features linked to
more attribute tables. Definitions on first 2 rows are applied for
example on maps water1, water2, ... so that more maps may share one
table.

\verbatim
water@PERMANENT 1 myrivers id /home/guser/mydbf dbf
\endverbatim

This definion overwrites the definition saved in PERMANENT/VAR and
links the water map from PERMANENT mapset to the user's table.

Modules should be written so that connections to databases for each
vector layer are independent. It should be possible to read attributes
of an input vector map from one database and write to some other and
even with some other driver (should not be a problem).

There are open questions, however. For one, how does one distinguish when
new tables should be written and when not? For example, definitions:

\verbatim
river 1 river id water odbc
river.backup* 1 NONE
\endverbatim

could be used to say that tables should not be copied for backups of
map river because table is stored in a reliable RDBMS.

\section vlibs Vector libraries

Besides internal library functions there are two main libraries:

- Vlib (Vector library), see \ref vlib
- DGLib (Directed Graph Library), see \ref dglib

For historical reasons, there are two internal libraries:

- diglib (with dig_*() functions), GRASS 3.x/4.x
- Vlib (with V1_*(), V2_*() and Vect_*() functions), GRASS 4.x/5.x
  (except for the 5.7 interim version)

The vector library was introduced in GRASS 4.0 to hide internal vector
files' formats and structures.  In GRASS 6/7, everything is accessed via
Vect_*() functions, for example:

Old 4.x code:

\code
    xx = Map.Att[Map.Area[area_num].att].x;
\endcode

New 6.x/7.x functions:

\code
    centroid = Vect_get_area_centroid(Map, area_num);
    Vect_read_line(Map, line_p, NULL, centroid);
    Vect_line_get_point(line_p, 0, &xx, NULL, NULL);
\endcode

In GRASS 6/7, all internal, mostly non-topological vector functions are
hidden from the modules' API (mainly dig_*(), V1_*() and V2_*()
functions). All available Vect_*() functions are topological vector
functions.


The following include file contains definitions and structures
required by some of the routines in this library. The programmer
should therefore include this file in any code that uses the vector
library:

\code
#include <grass/vector.h>
\endcode

<i>Note: For details please read Blazek et al. 2002 (see below) as
well as the references in this document.</i>

\section vlib_structures Vector library structures

\subsection Map_info Map_info structure

<tt>Map_info</tt> structure holds basic information about open vector map.

\code
struct Map_info
{
    /* common info for all formats */
    int format;			/* format (native, ogr) */
    int temporary;		/* temporary file flag, not yet used */

    struct dblinks *dblnk;	/* info about db links */

    struct Plus_head plus;	/* topo file head info */

    /* graph-related section */
    int graph_line_type;	/* line type used to build the graph */
    dglGraph_s graph;		/* graph structure */
    dglSPCache_s spCache;	/* shortest path cache */
    double *edge_fcosts;	/* costs used for graph, (dglGetEdge()
    	   			   is not supported for _DGL_V1) */
    double *edge_bcosts;
    double *node_costs;		/* node costs */
    int cost_multip;		/* edge and node costs
				   multiplicator */

    /* All of these apply only to runtime, and none get written out
       to the dig_plus file 
    */
    int open;			/* should be 0x5522AA22 if opened correctly
				   or        0x22AA2255 if closed          
				   anything else implies that structure has
				   never been initialized
				*/
    int mode;			/* Open mode - read, write, rw */
    int level;			/* Topology level - 1, 2, (3) */
    int head_only;		/* only header is opened */
    int support_updated;	/* support files were updated */
    plus_t next_line;		/* for level 2 sequential reads */

    char *name;			/* for 4.0  just name, and mapset */
    char *mapset;               /* mapset name */
    /* location and gisdbase is usefull if changed (v.proj or external apps) */
    char *location;		/* location name */
    char *gisdbase;		/* gisdbase path */

    /* constraints for reading in lines  (not polys yet) */
    int Constraint_region_flag;
    int Constraint_type_flag;
    double Constraint_N;
    double Constraint_S;
    double Constraint_E;
    double Constraint_W;
    double Constraint_T;
    double Constraint_B;
    int Constraint_type;
    int proj;

    /* format specific */
    /* native */
    struct gvfile dig_fp;	/* dig file pointer */
    struct dig_head head;	/* coor file head */

    /* non native */
    struct Format_info fInfo;	/* format information */

    /* history file */
    FILE *hist_fp;

    /* temporary solution for sites */
    struct site_att *site_att;	/* array of attributes loaded from db */
    int n_site_att;		/* number of attributes in site_att array */
    int n_site_dbl;		/* number of double attributes for one site */
    int n_site_str;		/* number of string attributes for one site */
};
\endcode

\subsection Plus_head Plus_head structure

<tt>Plus_head</tt> holds basic topology-related information about vector map.

\code
struct Plus_head
{
    int Version_Major;		 /* version codes */
    int Version_Minor;
    int Back_Major;		 /* earliest version that can use this data format */
    int Back_Minor;

    int spidx_Version_Major;	 /* version codes for spatial index */
    int spidx_Version_Minor;
    int spidx_Back_Major;	 /* earliest version that can use this data format */
    int spidx_Back_Minor;

    int cidx_Version_Major;	 /* version codes for category index */
    int cidx_Version_Minor;
    int cidx_Back_Major;	 /* earliest version that can use this data format */
    int cidx_Back_Minor;

    int with_z;                  /* 2D/3D vector data */
    int spidx_with_z;            /* 2D/3D spatial index */

    int off_t_size;              /* offset size here because Plus_head
				    is available to all releveant
				    functions */

    long head_size;		 /* topo header size */
    long spidx_head_size;	 /* spatial index header size */
    long cidx_head_size;	 /* category index header size */

    int release_support;	 /* release memory occupied by support
				    (topo, spatial, category) */

    struct Port_info port;	 /* portability information */
    struct Port_info spidx_port; /* portability information for
				    spatial index */
    struct Port_info cidx_port;	 /* portability information for
				    category index */
    int mode;			 /* read, write, RW */

    int built;			 /* the highest level of topology
				    currently available
				    (GV_BUILD_*) */

    struct bound_box box;	 /* vector map bounding box */

    /* topology info */
    struct P_node **Node;	 /* struct P_node array of pointers 
				    1st item is 1 for  */
    struct P_line **Line;	 /* struct P_line array of pointers 
				    all these (not 0) */
    struct P_area **Area;
    struct P_isle **Isle;
                                 /* add here P_FACE, P_VOLUME, P_HOLE */

    plus_t n_nodes;		 /* current number of nodes */
    plus_t n_edges;		 /* current number of edges */
    plus_t n_lines;	 	 /* current number of lines */
    plus_t n_areas;		 /* current number of areas */
    plus_t n_isles;		 /* current number of isles */
    plus_t n_faces;		 /* current number of faces */
    plus_t n_volumes;	         /* current number of volumes */
    plus_t n_holes;		 /* current number of holes */

    plus_t n_plines;		 /* current number of points */
    plus_t n_llines;		 /* current number of lines */
    plus_t n_blines;		 /* current number of boundaries */
    plus_t n_clines;		 /* current number of centroids */
    plus_t n_flines;		 /* current number of faces */
    plus_t n_klines;		 /* current number of kernels*/
    plus_t n_vfaces;		 /* current number of volumes */
    plus_t n_hfaces;		 /* current number of hole faces */

    plus_t alloc_nodes;		 /* number of nodes we have alloc'ed
				    space for i.e. array size - 1 */
    plus_t alloc_edges;          /* number of edges we have alloc'ed space for */
    plus_t alloc_lines;		 /* number of lines we have alloc'ed space for */
    plus_t alloc_areas;		 /* number of areas we have alloc'ed space for */
    plus_t alloc_isles;		 /* number of isles we have alloc'ed space for */
    plus_t alloc_faces;		 /* number of faces we have alloc'ed space for */
    plus_t alloc_volumes;	 /* number of volumes we have alloc'ed space for */
    plus_t alloc_holes;		 /* number of holes we have alloc'ed space for */

    off_t Node_offset;		 /* offset of array of nodes in topo file */
    off_t Edge_offset;           /* offset of array of edges in topo file */
    off_t Line_offset;           /* offset of array of lines in topo file */
    off_t Area_offset;           /* offset of array of areas in topo file */
    off_t Isle_offset;           /* offset of array of isles in topo file */
    off_t Volume_offset;         /* offset of array of volumes in topo file */
    off_t Hole_offset;           /* offset of array of holes in topo file */

    int Spidx_built;		 /* set to 1 if spatial index is available */
    int Spidx_new;               /* set to 1 if new spatial index will be generated */

    struct gvfile spidx_fp;	 /* spatial index file pointer */
    
    char *spidx_node_fname;      /* node spatial index file name */

    off_t Node_spidx_offset;	 /* offset of nodes in sidx file */
    off_t Line_spidx_offset;     /* offset of lines in sidx file */
    off_t Area_spidx_offset;     /* offset of areas in sidx file */
    off_t Isle_spidx_offset;     /* offset of isles in sidx file */
    off_t Face_spidx_offset;     /* offset of faces in sidx file */
    off_t Volume_spidx_offset;   /* offset of volumes in sidx file */
    off_t Hole_spidx_offset;     /* offset of holes in sidx file */

    struct RTree *Node_spidx;     /* node spatial index */
    struct RTree *Line_spidx;     /* line spatial index */
    struct RTree *Area_spidx;     /* area spatial index */
    struct RTree *Isle_spidx;     /* isle spatial index */
    struct RTree *Face_spidx;     /* face spatial index */
    struct RTree *Volume_spidx;   /* volume spatial index */
    struct RTree *Hole_spidx;     /* hole spatial index */

    /* Category index
       By default, category index is not updated */
    int update_cidx;		  /* update category index if vector is modified */

    int n_cidx;			  /* number of cat indexes (one for each field) */
    int a_cidx;			  /* allocated space for cat indexes */
    struct Cat_index *cidx;	  /* array of category indexes */
    int cidx_up_to_date;	  /* set to 1 when cidx is created and reset to 0 whenever any line is changed */

    off_t coor_size;		  /* size of coor file */
    long coor_mtime;		  /* time of last coor modification */

    /* Level2 update: list of lines and nodes updated (topo info for
       the line was changed) by last write/rewrite/delete operation.
       Lines/nodes in the list may be deleted (e.g. delete boundary:
       first added for delete area and then delete */
    int do_uplist;		  /* used internaly in diglib to know if list is maintained */

    int *uplines;		  /* array of updated lines */
    int alloc_uplines;		  /* allocated array */
    int n_uplines;		  /* number of updated lines */
    int *upnodes;		  /* array of updated nodes */
    int alloc_upnodes;		  /* allocated array */
    int n_upnodes;		  /* number of updated nodes */
};
\endcode

\subsection dig_head dig_head structure

<tt>dig_head</tt> holds header data of vector map (see \ref Map_info).

\code
struct dig_head
{
    /* elements */
    char *organization;         /* orgranization name */
    char *date;                 /* map date */
    char *your_name;            /* user name */
    char *map_name;             /* map name */
    char *source_date;          /* source date */
    long orig_scale;            /* original scale */
    char *line_3;               /* comments */
    int plani_zone;             /* zone */
    double digit_thresh;        /* threshold for digitization */

    /* Programmers should NOT touch any thing below here */
    /* Library takes care of everything for you          */

    /* coor elements */
    int Version_Major;          /* backward compatibility info */
    int Version_Minor;
    int Back_Major;
    int Back_Minor;
    int with_z;                 /* 2D/3D vector data */

    off_t size;			/* coor file size */
    long head_size;		/* coor header size */

    struct Port_info port;	/* portability information */

    off_t last_offset;		/* offset of last read line */

    struct recycle *recycle;    /* recycle dead line, not implemented yet */

    struct Map_info *Map;	/* X-ref to Map_info struct (needed?) */
};
\endcode

\section feature_geom Vector library feature geometry

\subsection ftypes Feature types

\code
#define GV_POINT      0x01
#define GV_LINE	      0x02
#define GV_BOUNDARY   0x04
#define GV_CENTROID   0x08
#define GV_FACE       0x10
#define GV_KERNEL     0x20
#define GV_AREA	      0x40
#define GV_VOLUME     0x80

#define GV_POINTS (GV_POINT | GV_CENTROID )
#define GV_LINES (GV_LINE | GV_BOUNDARY )
\endcode

Face and kernel are 3D equivalents of boundary and centroid, but there
is no support (yet) for 3D topology (volumes). Faces are used in a
couple of modules including NVIZ to visualize 3D buildings and other
volumetric figures.

\subsection coor_file_format Coor file format specification

In the coor file the following is stored: 'line' (element) type,
number of attributes and layer number for each category. Coordinates
in binary file are stored as double (8 bytes).

\subsubsection coor_file_head Header

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>

<tr><td>Version_Major </td><td>C</td><td>1</td><td>file version (major)</td></tr>
<tr><td>Version_Minor </td><td>C</td><td>1</td><td>file version (minor)</td></tr>
<tr><td>Back_Major</td><td>C</td><td>1</td><td>supported from GRASS version (major)</td></tr>
<tr><td>Back_Minor</td><td>C</td><td>1</td><td>supported from GRASS version (minor)</td></tr>

<tr><td>byte_order</td><td>C</td><td>1</td><td>little or big endian
                  flag; files are written in machine native order but
                  files in both little and big endian order may be
                  read; zero for little endian</td></tr>

<tr><td>size</td><td>L</td><td>1</td><td>coor file size</td></tr>

<tr><td>with_z</td><td>C</td><td>1</td><td>2D or 3D flag; zero for 2D</td></tr>

<tr><td>reserved</td><td>C</td><td>10</td><td>not used</td></tr>

</table>

\subsubsection coor_file_body Body

The body consists of line records:

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>
<tr><td>record header</td><td>C</td><td>1</td><td>
<UL>
  <LI><B>0. bit</B> : 1 - alive, 0 - dead line
  <LI><B>1. bit</B> : 1 - categories, 0 - no categories
  <LI><B>2.-3. bit</B> : type - one of: GV_POINT, GV_LINE, 
                              GV_BOUNDARY, GV_CENTROID
  <LI><B>4.-7. bit</B> : reserved, not used 
</UL>
</td></tr>

<tr><td>ncats</td><td>I</td><td>1</td><td>number of categories 
    (written only if categories exist) </td></tr>

<tr><td>field</td><td>I</td><td>ncats</td><td>field identifier,
    distinguishes between more categories append to one feature (written
    only if categories exist; field is called "layer" at user
    level)</td></tr>

<tr><td>cat</td><td>I</td><td>ncats</td><td>category value (written
    only if categories exist)</td></tr>

<tr><td>ncoor</td><td>I</td><td>1</td><td>written for GV_LINES and GV_BOUNDARIES 
    only</td></tr>

<tr><td>x</td><td>D</td><td>ncoor</td><td>x coordinate</td></tr>

<tr><td>y</td><td>D</td><td>ncoor</td><td>y coordinate</td></tr>

<tr><td>z</td><td>D</td><td>ncoor</td><td>z coordinate; present if
    with_z in head is set to 1</td></tr> </table>

<B>Types used in coor file</B>
<table border="1" style="border-collapse: collapse">
<tr><td>Type</td><td>Name</td><td>Size in Bytes</td></tr>
<tr><td>D</td><td>Double</td><td>8</td></tr>
<tr><td>L</td><td>Long  </td><td>4</td></tr>
<tr><td>I</td><td>Int   </td><td>4</td></tr>
<tr><td>S</td><td>Short </td><td>4</td></tr>
<tr><td>C</td><td>Char  </td><td>1</td></tr>
</table>

\section topology_management 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))</li>
- the format is topological (areas build from boundaries)</li>
- currently only 2D topology is supported

Topology is written for native format while pseudo-topology is written
for OGR sources, SHAPE-link.

The following rules apply to the vector data:

- Lines should not cross each other (i.e., lines which would cross must
  be split at their intersection to form distict lines).
- Linear primitives which share nodes at exactly same points (i.e.,
  must be snapped together). This is particulary important since nodes
  are not exactly represented in the coor file, but only implicitly as
  endpoints of lines.
- 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 is 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. 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. The area feature should be labeled by a centroid as an
  area. Additionally, the common boundary itself (i.e., the boundary
  which is also a line) should be labeled as a line by a distict
  category number.

Vector map topology can be cleaned at user level by <tt>v.clean</tt>
command.

\subsection topo_file_format Topo file format specification

Topo file is read by Vect_open_topo().

\subsubsection topo_file_header Header

Note: <tt>plus</tt> is instance of <tt>Plus_head</tt> structure.

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>

<tr><td>plus->Version_Major </td><td>C</td><td>1</td><td>file version (major)</td></tr>
<tr><td>plus->Version_Minor </td><td>C</td><td>1</td><td>file version (minor)</td></tr>
<tr><td>plus->Back_Major</td><td>C</td><td>1</td><td>supported from GRASS version (major)</td></tr>
<tr><td>plus->Back_Minor</td><td>C</td><td>1</td><td>supported from GRASS version (minor)</td></tr>

<tr><td>plus->port->byte_order</td><td>C</td><td>1</td><td>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</td></tr>

<tr><td>plus->head_size</td><td>L</td><td>1</td><td>header size</td></tr>

<tr><td>plus->with_z</td><td>C</td><td>1</td><td>2D or 3D flag; zero for 2D</td></tr>

<tr><td>plus->box</td><td>D</td><td>6</td><td>Bounding box coordinates (N,S,E,W,T,B)</td></tr>

<tr><td>plus->n_nodes, plus->n_lines, etc.</td><td>I</td><td>7</td><td>Number of
nodes, edges, lines, areas, isles, volumes and holes</td></tr>

<tr><td>plus->n_plines, plus->n_llines, etc.</td><td>I</td><td>7</td><td>Number of
points, lines, boundaries, centroids, faces and kernels</td></tr>

<tr><td>plus->Node_offset, plus->Edge_offset,
etc.</td><td>L</td><td>7</td><td>Offset value for nodes, edges, lines,
areas, isles, volumes and holes</td></tr>

<tr><td>plus->coor_size</td><td>L</td><td>1</td><td>File size</td></tr>
</table>

\subsubsection topo_file_body Body (nodes, lines, areas, isles)

<b>Nodes</b>

For each node (n_nodes):

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>
<tr><td>n_lines</td><td>I</td><td>1</td><td>Number of lines (0 for dead node)</td></tr>
<tr><td>lines</td><td>I</td><td>n_lines</td><td>Line ids</td></tr>
<tr><td>angles</td><td>D</td><td>n_lines</td><td>Angle value</td></tr>
<tr><td>n_edges</td><td>I</td><td>1</td><td>Reserved for edges (only for with_z)</td></tr>
<tr><td>x,y</td><td>D</td><td>2</td><td>Coordinate pair</td></tr>
<tr><td>z</td><td>D</td><td>1</td><td>Only for with_z</td></tr>
</table>

\code
struct P_node
{
    double x;			/* X coordinate */
    double y;			/* Y coordinate */
    double z;			/* Z coordinate */
    plus_t alloc_lines;         /* allocated space for lines */
    plus_t n_lines;		/* number of attached lines (size of
				   lines, angle). If 0, then is
				   degenerate node, for snappingi ???
				*/
    plus_t *lines;		/* list of connected lines */
    float *angles;		/* respected angles; angles for
				   lines/boundaries are in radians
				   between -PI and PI. Value for
				   points or lines with identical
				   points (degenerated) is set to
				   -9. */
};
\endcode

<b>Lines</b>

For each line (n_lines):

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>
<tr><td>feature type</td><td>C</td><td>1</td><td>0 for dead</td></tr>
<tr><td>offset</td><td>L</td><td>1</td><td>Line offset</td></tr>
<tr><td>N1</td><td>I</td><td>1</td><td>First node id (only if feature type is GV_POINTS, GV_LINES or GV_KERNEL)</td></tr>
<tr><td>N2</td><td>I</td><td>1</td><td>Second node id (only if feature type is GV_LINE or GV_BOUNDARY)</td></tr>
<tr><td>left</td><td>I</td><td>1</td><td>Left area id for feature type GV_BOUNDARY / Area id for feature type GV_CENTROID</td></tr>
<tr><td>right</td><td>I</td><td>1</td><td>Right area id (for feature type GV_BOUNDARY)</td></tr>
<tr><td>vol</td><td>I</td><td>1</td><td>Reserved for kernel (volume number, for feature type GV_KERNEL)</td></tr>
<tr><td>N,S,E,W</td><td>D</td><td>4</td><td>Line bounding box (for feature type GV_LINE, GV_BOUNDARY or GV_FACE)</td></tr>
<tr><td>T,B</td><td>D</td><td>2</td><td>Line bounding box for 3D (only if with_z=1)</td></tr>
</table>

\code
struct P_line
{
    plus_t N1;			/* start node */
    plus_t N2;			/* end node   */
    plus_t left;		/* area/isle number to left, negative
				   for isle area number for centroid,
				   negative for duplicate centroid 
				*/
    plus_t right;		/* area/isle number to right, negative
				 * for isle */

    double N;			/* line bounding Box */
    double S;
    double E;
    double W;
    double T;			/* top */
    double B;			/* bottom */

    off_t offset;		/* offset in coor file for line */
    int type;                   /* line type */
};
\endcode

<b>Areas</b>

For each area (n_areas):

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>
<tr><td>n_lines</td><td>I</td><td>1</td><td>number of boundaries</td></tr>
<tr><td>lines</td><td>I</td><td>n_lines</td><td>Line ids</td></tr>
<tr><td>n_isles</td><td>I</td><td>1</td><td>Number of isles</td></tr>
<tr><td>isles</td><td>I</td><td>n_isles</td><td>Isle ids</td></tr>
<tr><td>centroid</td><td>I</td><td>1</td><td>Centroid id</td></tr>
<tr><td>N,S,E,W</td><td>D</td><td>4</td><td>Area bounding box</td></tr>
<tr><td>T,B</td><td>D</td><td>2</td><td>Area bounding box for 3D (only if with_z=1)</td></tr>
</table>

\code
struct P_area
{
    double N;			/* area bounding Box */
    double S;
    double E;
    double W;
    double T;			/* top */
    double B;			/* bottom */
    plus_t n_lines;		/* number of boundary lines */
    plus_t alloc_lines;         /* allocated space */
    plus_t *lines;		/* list of boundary lines, negative
				   means direction N2 to N1, lines are
				   in clockwise order */

    /*********  Above this line is compatible with P_isle **********/
    plus_t centroid;		/* number of first centroid within area */

    plus_t n_isles;		/* number of islands inside */
    plus_t alloc_isles;
    plus_t *isles;		/* 1st generation interior islands */
};
\endcode

<b>Isles</b>

For each isle (n_isle):

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>
<tr><td>n_lines</td><td>I</td><td>1</td><td>number of boundaries</td></tr>
<tr><td>lines</td><td>I</td><td>n_lines</td><td>Line ids</td></tr>
<tr><td>area</td><td>I</td><td>1</td><td>Outer area id</td></tr>
<tr><td>N,S,E,W</td><td>D</td><td>4</td><td>Isle bounding box</td></tr>
<tr><td>T,B</td><td>D</td><td>2</td><td>Isle bounding box for 3D (only if with_z=1)</td></tr>
</table>

\code
struct P_isle
{
    double N;			/* isle bounding Box */
    double S;
    double E;
    double W;
    double T;			/* top */
    double B;			/* bottom */
    plus_t n_lines;		/* number of boundary lines */
    plus_t alloc_lines;
    plus_t *lines;		/* list of boundary lines, negative
				   means direction N2 to N1, lines are
				   in counter clockwise order */

    /*********  Above this line is compatible with P_area **********/
    plus_t area;		/* area it exists w/in, if any */
};
\endcode

\subsection topo_levels Topology levels

\code
#define GV_BUILD_NONE         0
#define GV_BUILD_BASE         1
#define GV_BUILD_AREAS        2
#define GV_BUILD_ATTACH_ISLES 3
#define GV_BUILD_CENTROIDS    4
#define GV_BUILD_ALL          GV_BUILD_CENTROIDS
\endcode

GV_BOUNDARY contains geometry and it is used to build areas.
GV_LINE cannot form an area.

\subsection topo_examples Topology examples

\subsubsection Topology_Example_1 Topology Example 1

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

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

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


\subsubsection Topology_Example_2 Topology Example 2

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

\verbatim
+---------+
|    A    |
+-----+   |
|  B  |   |
+-----+   |
|         |
+---------+
\endverbatim

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 no island.


\subsubsection Topology_Example_3 Topology Example 3

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

\verbatim
+---------------------+
|  A1                 |
+   +------+------+   |
|   |  A2  |  A3  |   |
+   +------+------+   |
|          I1         |
+---------------------+
\endverbatim

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


\subsubsection Topology_Example_4 Topology 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:

\verbatim
+-----+-----+
|     .     |
|     .     |
+.....+.....+
|     .     |
|  x  .     |
+-----+-----+

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

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


\subsection topo_memory 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.


\section spidx Vector library spatial index management

Spatial index (based on R-tree) is created with topology.

Spatial index occupies a lot of memory but it is necessary for 
topology building. Also, it takes a long time to release the memory
occupied by spatial index (dig_spidx_free()). 

The function building topology (Vect_build()) is usually called 
at the end of modules (before Vect_close()) so it is faster to call
exit() and operating system releases all the memory much faster.
By default the memory is not released.

It is possible to call Vect_set_release_support() before Vect_close()
to enforce memory release, but it takes a long time on large files.

The spatial index is stored in file and not loaded for old vectors that
are not updated, saving a lot of memory. Spatial queries are done in 
file.

Currently most of the modules do not release the memory occupied for
spatial index and work like this (pseudocode):

\code
int main
{
     Vect_open_new();
     /* writing new vector */

     Vect_build();
     Vect_close();  /* memory is not released */
}
\endcode

In general it is possible to free the memory with Vect_set_release_support()
such as:

\code
int main
{
     Vect_open_new();
     /* writing new vector */

     Vect_build();
     Vect_set_release_support();
     Vect_close();  /* memory is released */
}
\endcode

but it takes longer. 

It makes sense to release the spatial index if it is used only at the beginning
of a module or in permanently running programs like QGIS. Note that this
applies only when creating a new vector or updating an old vector.
For example:

\code
int main
{
     Vect_open_update();
     /* select features using spatial index, e.g.  Vect_select_lines_by_box() */
     Vect_set_release_support();
     Vect_close();  /* memory is released */

     /* do some processing which needs memory */
}
\endcode

\subsection sidx_file_format Sidx file format specification

Spatial index file ('sidx') is read by Vect_open_sidx().

\subsubsection sidx_file_header Header

Note: <tt>plus</tt> is instance of <tt>Plus_head</tt> structure.

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>

<tr><td>plus->spidx_Version_Major </td><td>C</td><td>1</td><td>file version (major)</td></tr>
<tr><td>plus->spidx_Version_Minor </td><td>C</td><td>1</td><td>file version (minor)</td></tr>
<tr><td>plus->spidx_Back_Major</td><td>C</td><td>1</td><td>supported from GRASS version (major)</td></tr>
<tr><td>plus->spidx_Back_Minor</td><td>C</td><td>1</td><td>supported from GRASS version (minor)</td></tr>

<tr><td>plus->spidx_port->byte_order</td><td>C</td><td>1</td><td>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</td></tr>

<tr><td>plus->spidx_port.off_t_size</td><td>C</td><td>1</td><td>off_t size (LFS)</td></tr>

<tr><td>plus->spidx_head_size</td><td>L</td><td>1</td><td>header size</td></tr>

<tr><td>plus->spidx_with_z</td><td>C</td><td>1</td><td>2D/3D vector data</td></tr>

<tr><td>ndims</td><td>C</td><td>1</td><td>Number of dimensions</td></tr>

<tr><td>nsides</td><td>C</td><td>1</td><td>Number of sides</td></tr>

<tr><td>nodesize</td><td>I</td><td>1</td><td>Node size</td></tr>

<tr><td>nodecard</td><td>I</td><td>1</td><td>Node card (?)</td></tr>

<tr><td>leafcard</td><td>I</td><td>1</td><td>Leaf card (?)</td></tr>

<tr><td>min_node_fill</td><td>I</td><td>1</td><td>Minimum node fill (?)</td></tr>

<tr><td>min_leaf_fill</td><td>I</td><td>1</td><td>Minimum leaf fill (?)</td></tr>

<tr><td>plus->Node_spidx->n_nodes</td><td>I</td><td>1</td><td>Number of nodes</td></tr>

<tr><td>plus->Node_spidx->n_leafs</td><td>I</td><td>1</td><td>Number of leafs</td></tr>

<tr><td>plus->Node_spidx->n_levels</td><td>I</td><td>1</td><td>Number of levels</td></tr>

<tr><td>plus->Node_spidx_offset</td><td>O</td><td>1</td><td>Node offset</td></tr>

<tr><td>plus->Line_spidx->n_nodes</td><td>I</td><td>1</td><td>Number of nodes</td></tr>

<tr><td>plus->Line_spidx->n_leafs</td><td>I</td><td>1</td><td>Number of leafs</td></tr>

<tr><td>plus->Line_spidx->n_levels</td><td>I</td><td>1</td><td>Number of levels</td></tr>

<tr><td>plus->Line_spidx_offset</td><td>O</td><td>1</td><td>Line offset</td></tr>

<tr><td>plus->Area_spidx->n_nodes</td><td>I</td><td>1</td><td>Number of nodes</td></tr>

<tr><td>plus->Area_spidx->n_leafs</td><td>I</td><td>1</td><td>Number of leafs</td></tr>

<tr><td>plus->Area_spidx->n_levels</td><td>I</td><td>1</td><td>Number of levels</td></tr>

<tr><td>plus->Area_spidx_offset</td><td>O</td><td>1</td><td>Area offset</td></tr>

<tr><td>plus->Isle_spidx->n_nodes</td><td>I</td><td>1</td><td>Number of nodes</td></tr>

<tr><td>plus->Isle_spidx->n_leafs</td><td>I</td><td>1</td><td>Number of leafs</td></tr>

<tr><td>plus->Isle_spidx->n_levels</td><td>I</td><td>1</td><td>Number of levels</td></tr>

<tr><td>plus->Isle_spidx_offset</td><td>O</td><td>1</td><td>Isle offset</td></tr>

<tr><td>plus->Face_spidx_offset</td><td>O</td><td>1</td><td>Face offset</td></tr>

<tr><td>plus->Volume_spidx_offset</td><td>O</td><td>1</td><td>Volume offset</td></tr>

<tr><td>plus->Hole_spidx_offset</td><td>O</td><td>1</td><td>Hole offset</td></tr>

<tr><td>plus->coor_size</td><td>O</td><td>1</td><td>Coor file size</td></tr>

</table>


\section cidx Vector library category index management

The category index (stored in the cidx file) improves the performance of all
selections by cats/attributes (SQL, e.g. 'd.vect cats=27591', 'v.extract list=20000-21000').
This avoids that all selections have to be made by looping through all vector lines.
Category index is also essential for simple feature representation of GRASS vectors.

Category index is created for each field. In memory, it is stored in

\code
struct Cat_index
{
    int field;			/* field number */
    int n_cats;			/* number of items in cat array */
    int a_cats;			/* allocated space in cat array */
    int (*cat)[3];		/* array of cats (cat, type, lines/area) */
    int n_ucats;		/* number of unique cats (not updated) */
    int n_types;		/* number of types in type */
    int type[7][2];		/* number of elements for each type
				 * (point, line, boundary, centroid,
				 * area, face, kernel) */
    off_t offset;		/* offset of the beginning of this
				 * index in cidx file */
};
\endcode

Category index is built with topology, but it is <b>not updated</b> if vector is edited on level 2.
Category index is stored in 'cidx' file, 'cat' array is written/read by one call of
dig__fwrite_port_I( (int *)ci->cat, 3 * ci->n_cats, fp) or
dig__fread_port_I( (int *)ci->cat, 3 * ci->n_cats, fp).

Stored values can be retrieved either by index in 'cat' array 
(if all features of given field are required) or by category value
(one or few features), always by Vect_cidx_*() functions.

To create category index, it will be necessary to rebuild topology for all existing vectors.
This is an opportunity to make (hopefully) last changes in 'topo', 'cidx' formats.

\subsection cidx_file_format Cidx file format specification

Category index file ('cidx') is read by Vect_cidx_open().

\subsubsection cidx_file_head Header

Note: <tt>plus</tt> is instance of <tt>Plus_head</tt> structure.

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>

<tr><td>plus->cpidx_Version_Major </td><td>C</td><td>1</td><td>file version (major)</td></tr>
<tr><td>plus->cpidx_Version_Minor </td><td>C</td><td>1</td><td>file version (minor)</td></tr>
<tr><td>plus->cpidx_Back_Major</td><td>C</td><td>1</td><td>supported from GRASS version (major)</td></tr>
<tr><td>plus->cpidx_Back_Minor</td><td>C</td><td>1</td><td>supported from GRASS version (minor)</td></tr>

<tr><td>plus->cidx_port->byte_order</td><td>C</td><td>1</td><td>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</td></tr>

<tr><td>plus->cidx_head_size</td><td>L</td><td>1</td><td>cidx head size</td></tr>

<tr><td>plus->n_cidx</td><td>I</td><td>1</td><td>number of fields</td></tr>

<tr><td>field</td><td>I</td><td>n_cidx</td><td>field number</td></tr>

<tr><td>n_cats</td><td>I</td><td>n_cidx</td><td>number of categories</td></tr>

<tr><td>n_ucats</td><td>I</td><td>n_cidx</td><td>number of unique categories</td></tr>

<tr><td>n_types</td><td>I</td><td>n_cidx</td><td>number of feature types</td></tr>

<tr><td>rtype</td><td>I</td><td>n_cidx * n_types</td><td>Feature type</td></tr>

<tr><td>type[t]</td><td>I</td><td>n_cidx * n_types</td><td>Number of items</td></tr>

</table>

\section tin Vector TINs

TINs are simply created as 2D/3D vector polygons consisting of 
3 vertices. See Vect_tin_get_z().


\section ogr_iface OGR interface

\subsection frmt_file_format Frmt file format specification

Frmt is a plain text file which contains basic information about
external format of linked vector map. Each line contains key, value
pairs separated by comma.

OGR specific format is described by:

 - FORMAT - ogr
 - DSN - datasource name
 - LAYER - OGR layer name

Example:

\verbatim
FORMAT: ogr
DSN: /home/martin/src/grass_trunk
LAYER: p
\endverbatim

OGR layer can be linked via <tt>v.external</tt> command. When linking
OGR layer pseudo-topology ('topo') is built including spatial index
file ('sidx') and category index file ('cidx'). Additionally also
feature index file (see \ref fidx_file_format) is created.

\subsection fidx_file_format Fidx file format specification

Note: <tt>finfo</tt> is an instance of <tt>Format_info</tt> structure.

<table border="1" style="border-collapse: collapse">
<tr><td>Name</td><td>Type</td><td>Number</td><td>Description</td></tr>

<tr><td>Version_Major </td><td>C</td><td>1</td><td>file version (major)</td></tr>
<tr><td>Version_Minor </td><td>C</td><td>1</td><td>file version (minor)</td></tr>
<tr><td>Back_Major</td><td>C</td><td>1</td><td>supported from GRASS version (major)</td></tr>
<tr><td>Back_Minor</td><td>C</td><td>1</td><td>supported from GRASS version (minor)</td></tr>

<tr><td>byte_order</td><td>C</td><td>1</td><td>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</td></tr>

<tr><td>length</td><td>L</td><td>1</td><td>header size</td></tr>

<tr><td>fInfo.ogr.offset_num</td><td>I</td><td>1</td><td>number of records</td></tr>

<tr><td>fInfo.ogr.offset</td><td>I</td><td>offset_num</td><td>offsets</td></tr>

</table>

\section grassdglib DGLib (Directed Graph Library)

<b>The Directed Graph Library</b> or DGLib (Micarelli 2002, \ref dglib ,
http://grass.osgeo.org/dglib/) provides functionality for vector network
analysis. This library released under GPL is hosted by the GRASS
project (within the GRASS source code). As a stand-alone library it
may also be used by other software projects.

The Directed Graph Library library provides functionality to assign costs to
lines and/or nodes. That means that costs can be accumulated while traveling
along polylines. The user can assign individual costs to all lines and/or
nodes of a vector map and later calculate shortest path connections based on
the accumulated costs. Applications are transport analysis, connectivity and
more. Implemented applications cover shortest path, traveling salesman (round trip),
allocation of sources (creation of subnetworks), minimum Steiner trees 
(star-like connections), and iso-distances (from centers).

For details, please read Blazek et al. 2002 (see below).

Related vector functions are:
 Vect_graph_add_edge(),
 Vect_graph_init(),
 Vect_graph_set_node_costs(),
 Vect_graph_shortest_path(),
 Vect_net_build_graph(),
 Vect_net_nearest_nodes(),
 Vect_net_shortest_path(), and
 Vect_net_shortest_path_coor().


\section ascii Vector ASCII Format Specifications

The GRASS ASCII vector map format may contain a mix of primitives
including points, lines, boundaries, centroids, faces, and
kernels. The format may also contain a header with various metadata
(see example below).

Vector map can be converted to the ASCII representation at user level
by <tt>v.out.ascii format=standard</tt> command.


The header is similar as the head file of vector binary format (see
\ref head_file_format) but contains bounding box also. Keywords are:

\verbatim
ORGANIZATION
DIGIT DATE
DIGIT NAME
MAP NAME
MAP DATE
MAP SCALE
OTHER INFO
ZONE
WEST EDGE
EAST EDGE
SOUTH EDGE
NORTH EDGE
MAP THRESH
\endverbatim

Example:

\verbatim
ORGANIZATION: NC OneMap
DIGIT DATE:   
DIGIT NAME:   helena
MAP NAME:     North Carolina selected bridges (points map)
MAP DATE:     Mon Nov  6 15:32:39 2006
MAP SCALE:    1
OTHER INFO:   
ZONE:         0
MAP THRESH:   0.000000
\endverbatim

The body begins with the row:

\verbatim
VERTI:
\endverbatim

followed by records of primitives:

\verbatim
TYPE NUMBER_OF_COORDINATES [NUMBER_OF_CATEGORIES]
 X Y [Z]
....
 X Y [Z]
[ LAYER CATEGORY]
....
[ LAYER CATEGORY]
\endverbatim

Everything above in <tt>[]</tt> is optional. 

The primitive codes are as follows:

- 'P': point
- 'L': line
- 'B': boundary
- 'C': centroid
- 'F': face (3D boundary)
- 'K': kernel (3D centroid)
- 'A': area (boundary) - better use 'B'; kept only for backward
compatibility

The coordinates are listed following the initial line containing the
primitive code, the total number of vectors in the series, and (optionally)
the number of categories (1 for a single layer, higher for multiple layers).
Below that 1 or several lines follow to indicate the layer number and
the category number (ID).

The order of coordinates is
\verbatim
  X Y [Z]
\endverbatim

Note: The points are stored as y, x (i.e., east, north), which is the
reserve of the way GRASS usually represents geographic coordinates.

Example:

\verbatim
P  1 1
 375171.4992779 317756.72097616
 1     1 
B  5
 637740       219580      
 639530       219580      
 639530       221230      
 637740       221230      
 637740       219580      
C  1 1
 638635       220405      
 1     2
\endverbatim

In this example, the first vector feature is a point with category
number 1. The second vector feature is a boundary composed by 5
points. The third feature is a centroid with category number 2. The
boundary and the centroid form an area with category number 2. All
vector feature mentioned above are located in layer 1.

\section vlibfunc List of vector library functions

The vector library provides the GRASS programmer with routines to
process vector data. The routines in the vector library are presented
in functional groupings, rather than in alphabetical order. The order
of presentation will, it is hoped, provide better understanding of how
the library is to be used, as well as show the interrelationships
among the various routines. Note that a good way to understand how to
use these routines is to look at the source code for GRASS modules
which use them.

Note: All routines start with one of following prefixes Vect_, V1_,
V2_ or dig_. To avoid name conficts, programmers should not create
variables or routines in their own modules which use this prefix.

The Vect_*() functions are the programmer's API for GRASS vector
programming. The programmer should use only routines with this prefix.

- \subpage area
- \subpage array
- \subpage box
- \subpage break_lines
- \subpage break_polygons
- \subpage bridges
- \subpage buffer
- \subpage build
- \subpage build_nat
- \subpage build_ogr
- \subpage cats
- \subpage cindex
- \subpage clean_nodes
- \subpage close
- \subpage constraint
- \subpage dangles
- \subpage dbcolumns
- \subpage error
- \subpage field
- \subpage find
- \subpage graph
- \subpage header
- \subpage hist
- \subpage init_head
- \subpage intersect
- \subpage legal_vname
- \subpage level
- \subpage level_two
- \subpage line
- \subpage list
- \subpage map
- \subpage net
- \subpage open
- \subpage overlay
- \subpage vpoly
- \subpage read
- \subpage remove_areas
- \subpage remove_duplicates
- \subpage rewind
- \subpage select
- \subpage sindex
- \subpage snap
- \subpage tin
- \subpage type
- \subpage delete
- \subpage write


\section area Vector area functions

 - Vect_get_area_area()

 - Vect_get_area_boundaries()

 - Vect_get_area_centroid()

 - Vect_get_area_isle()

 - Vect_get_area_num_isles()

 - Vect_area_perimeter()

 - Vect_get_area_points()

 - Vect_get_isle_area()

 - Vect_get_isle_boundaries()

 - Vect_get_isle_points()

 - Vect_point_in_area()


\section array Vector array functions

 - Vect_new_varray()

 - Vect_set_varray_from_cat_list()

 - Vect_set_varray_from_cat_string()

 - Vect_set_varray_from_db()


\section box Vector bounding box functions

 - Vect_box_copy()

 - Vect_box_clip()

 - Vect_box_extend()

 - Vect_box_overlap()

 - Vect_get_area_box()

 - Vect_get_isle_box()

 - Vect_get_line_box()

 - Vect_get_map_box()

 - Vect_point_in_box()

 - Vect_region_box()


\section break_lines Vector break lines functions

 - Vect_break_lines()

 - Vect_break_lines_list()


\section break_polygons Vector break polygons functions

 - Vect_break_polygons()


\section bridges Vector bridges functions

 - Vect_chtype_bridges()

 - Vect_remove_bridges()


\section buffer Vector buffer functions

 - Vect_line_buffer()

 - Vect_line_parallel()


\section build Vector build functions

 - Vect_build()

 - Vect_build_partial()

 - Vect_get_built()

 - Vect_build_sidx_from_topo()

 - Vect_build_sidx()

 - Vect_save_sidx()

 - Vect_save_topo()

 - Vect_sidx_dump()

 - Vect_topo_dump()


\subsection build_nat Vector build (native) functions

 - Vect_attach_centroids()

 - Vect_attach_isle()

 - Vect_attach_isles()

 - Vect_build_line_area()

 - Vect_build_nat()

 - Vect_isle_find_area()


\subsection build_ogr Vector build (OGR) functions

 - Vect_build_ogr()


\section cats Vector categories functions

 - Vect_array_to_cat_list()

 - Vect_cat_del()

 - Vect_cat_get()

 - Vect_cat_in_array()

 - Vect_cat_in_cat_list()

 - Vect_cat_set()

 - Vect_destroy_cat_list()

 - Vect_destroy_cats_struct()

 - Vect_field_cat_del()

 - Vect_get_area_cats()

 - Vect_get_area_cat()

 - Vect_get_line_cat()

 - Vect_new_cat_list()

 - Vect_new_cats_struct()

 - Vect_reset_cats()

 - Vect_str_to_cat_list()


\section cindex Vector category index functions

(note: vector layer is historically called "field")

 - Vect_cidx_dump()

 - Vect_cidx_find_next()

 - Vect_cidx_find_all()

 - Vect_cidx_get_cat_by_index()

 - Vect_cidx_get_field_index()

 - Vect_cidx_get_field_number()

 - Vect_cidx_get_num_cats_by_index()

 - Vect_cidx_get_num_fields()

 - Vect_cidx_get_num_types_by_index()

 - Vect_cidx_get_num_unique_cats_by_index()

 - Vect_cidx_get_type_count()

 - Vect_cidx_get_type_count_by_index()

 - Vect_cidx_open()

 - Vect_cidx_save()

 - Vect_set_category_index_update()


\section clean_nodes Vector clean nodes functions

 - Vect_clean_small_angles_at_nodes()


\section close Vector close functions

 - Vect_close()


\section constraint Vector constraint functions

 - Vect_get_constraint_box()

 - Vect_remove_constraints()

 - Vect_set_constraint_region()

 - Vect_set_constraint_type()


\section dangles Vector dangles functions

 - Vect_chtype_dangles()

 - Vect_remove_dangles()

 - Vect_select_dangles()


\section dbcolumns Vector dbcolumns functions

 - Vect_get_column_names()

 - Vect_get_column_names_types()

 - Vect_get_column_types()


\section error Vector error functions

 - Vect_get_fatal_error()

 - Vect_set_fatal_error()


\section field Vector field functions

(note: vector layer is historically called "field")

 - Vect_add_dblink()

 - Vect_check_dblink()

 - Vect_default_field_info()

 - Vect_get_dblink()

 - Vect_get_field()

 - Vect_get_field_by_name()

 - Vect_map_add_dblink()

 - Vect_map_check_dblink()

 - Vect_map_del_dblink()

 - Vect_new_dblinks_struct()

 - Vect_read_dblinks()

 - Vect_reset_dblinks()

 - Vect_set_db_updated()

 - Vect_subst_var()

 - Vect_write_dblinks()


\section find Vector find functions

 - Vect_find_area()

 - Vect_find_island()

 - Vect_find_line()

 - Vect_find_line_list()

 - Vect_find_node()


\section graph Vector graph functions

 - Vect_graph_add_edge()

 - Vect_graph_build()

 - Vect_graph_init()

 - Vect_graph_set_node_costs()

 - Vect_graph_shortest_path()


\section header Vector header functions

 - Vect_get_comment()

 - Vect_get_constraint_box()

 - Vect_get_date()

 - Vect_get_full_name()

 - Vect_get_map_date()

 - Vect_get_map_name()

 - Vect_get_mapset()

 - Vect_get_name()

 - Vect_get_organization()

 - Vect_get_person()

 - Vect_get_proj()

 - Vect_get_proj_name()

 - Vect_get_scale()

 - Vect_get_thresh()

 - Vect_get_zone()

 - Vect_is_3d()

 - Vect_print_header()

 - Vect_read_header()

 - Vect_set_comment()

 - Vect_set_date()

 - Vect_set_map_date()

 - Vect_set_map_name()

 - Vect_set_organization()

 - Vect_set_person()

 - Vect_set_scale()

 - Vect_set_thresh()

 - Vect_set_zone()

 - Vect_write_header()


\section hist Vector history functions

 - Vect_hist_command()

 - Vect_hist_copy()

 - Vect_hist_read()

 - Vect_hist_rewind()

 - Vect_hist_write()


\section init_head Vector header functions

 - Vect_copy_head_data()


\section intersect Vector intersection functions

 - Vect_line_check_intersection()

 - Vect_line_intersection()

 - Vect_segment_intersection()


\section legal_vname Vector valid map name functions

 - Vect_check_input_output_name()

 - Vect_legal_filename()


\section level Vector level functions

 - Vect_level()


\section level_two Vector topological (level 2) functions

 - Vect_get_centroid_area()

 - Vect_get_line_areas()

 - Vect_get_line_nodes()

 - Vect_get_node_coor()

 - Vect_get_node_line()

 - Vect_get_node_line_angle()

 - Vect_get_node_n_lines()

 - Vect_get_num_areas()

 - Vect_get_num_dblinks()

 - Vect_get_num_faces()

 - Vect_get_num_islands()

 - Vect_get_num_lines()

 - Vect_get_num_nodes()

 - Vect_get_num_primitives()

 - Vect_get_num_updated_lines()

 - Vect_get_num_updated_nodes()

 - Vect_get_updated_line()

 - Vect_get_updated_node()

 - Vect_set_release_support()


\section line Vector feature functions

 - Vect_append_point()

 - Vect_append_points()

 - Vect_copy_pnts_to_xyz()

 - Vect_copy_xyz_to_pnts()

 - Vect_destroy_line_struct()

 - Vect_get_num_line_points()

 - Vect_line_box()

 - Vect_line_delete_point()

 - Vect_line_distance()

 - Vect_line_geodesic_length()

 - Vect_line_get_point()

 - Vect_line_insert_point()

 - Vect_line_length()

 - Vect_line_prune()

 - Vect_line_prune_thresh()

 - Vect_line_reverse()

 - Vect_line_segment()

 - Vect_new_line_struct()

 - Vect_point_on_line()

 - Vect_points_distance()

 - Vect_reset_line()


\section list Vector list functions

 - Vect_destroy_list()

 - Vect_list_append()

 - Vect_list_append_list()

 - Vect_list_delete()

 - Vect_list_delete_list()

 - Vect_new_list()

 - Vect_reset_list()

 - Vect_val_in_list()


\section map Vector map functions

 - Vect_copy()

 - Vect_copy_map_lines()

 - Vect_copy_table()

 - Vect_copy_table_by_cats()

 - Vect_copy_tables()

 - Vect_delete()

 - Vect_rename()


\section net Vector network functions

 - Vect_net_build_graph()

 - Vect_net_get_line_cost()

 - Vect_net_get_node_cost()

 - Vect_net_nearest_nodes()

 - Vect_net_shortest_path()

 - Vect_net_shortest_path_coor()


\section open Vector open functions

 - Vect_coor_info()

 - Vect_maptype_info()

 - Vect_open_new()

 - Vect__open_old()

 - Vect_open_old()

 - Vect_open_old_head()

 - Vect_open_sidx()

 - Vect_open_topo()

 - Vect_open_update()

 - Vect_open_update_head()

 - Vect_set_open_level()



\section overlay Vector overlay functions

 - Vect_overlay()

 - Vect_overlay_str_to_operator()


\section vpoly Vector polygon functions

 - Vect_find_poly_centroid()

 - Vect_get_point_in_area()

 - Vect_point_in_area_outer_ring()

 - Vect_point_in_island()

 - Vect_get_point_in_poly()

 - Vect_get_point_in_poly_isl()


\section read Vector read functions

\subsection read1_2 Level 1 and 2

 - Vect_read_next_line()

\subsection read2 Level 2 only

 - Vect_area_alive()

 - Vect_isle_alive()

 - Vect_line_alive()

 - Vect_node_alive()

 - Vect_read_line()


\section remove_areas Vector remove areas functions

 - Vect_remove_small_areas()


\section remove_duplicates Vector remove duplicates functions

 - Vect_line_check_duplicate()

 - Vect_remove_duplicates()


\section rewind Vector rewind functions

 - Vect_rewind()


\section sindex Vector spatial index functions

 - Vect_select_areas_by_box()

 - Vect_select_areas_by_polygon()

 - Vect_select_isles_by_box()

 - Vect_select_lines_by_box()

 - Vect_select_lines_by_polygon()

 - Vect_select_nodes_by_box()


\section select custom spatial index functions

 - Vect_spatial_index_add_item()

 - Vect_spatial_index_del_item()

 - Vect_spatial_index_destroy()

 - Vect_spatial_index_init()

 - Vect_spatial_index_select()


\section snap Vector snap functions

 - Vect_snap_lines()

 - Vect_snap_lines_list()


\section tin Vector TIN functions

 - Vect_tin_get_z()


\section type Vector type option functions

 - Vect_option_to_types()


\section delete Vector delete functions

\subsection delete2 Level 2 only

 - Vect_delete_line()

\section write Vector write functions

\subsection write1_2 Level 1 and 2

 - Vect_write_line()

\subsection write2 Level 2 only

 - Vect_rewrite_line()

\section geos GEOS support

Note: The functions are available only if GRASS is compiled with
<tt>--with-geos</tt> switch.

 - Vect_read_line_geos()

 - Vect_read_area_geos()

 - Vect_line_to_geos()

 - Vect_get_area_points_geos()

 - Vect_get_isle_points_geos()


\section authors Authors

 Radim Blazek (vector architecture) <radim.blazek gmail.com>

 Roberto Micarelli (DGLib) <mi.ro iol.it>


\section references References

Text based on: R. Blazek, M. Neteler, and R. Micarelli. The new GRASS 5.1
 vector architecture. In Open source GIS - GRASS users conference 2002,
 Trento, Italy, 11-13 September 2002. University of Trento, Italy, 2002.
 <a href="http://www.ing.unitn.it/~grass/conferences/GRASS2002/proceedings/proceedings/pdfs/Blazek_Radim.pdf">http://www.ing.unitn.it/~grass/conferences/GRASS2002/proceedings/proceedings/pdfs/Blazek_Radim.pdf</a>
 
\section seealso See Also

 - \ref dglib
 
 - \ref dbmilib
 
 - \ref veditlib

Last change: $Date$
*/