UNIT II

Vector data structure

Geographic entities encoded using the vector data model, are often called features. The features
can be divided into two classes:

a. Simple features
These are easy to create, store and are rendered on screen very quickly. They lack connectivity
relationships and so are inefficient for modeling phenomena conceptualized as fields.

b. Topological features
A topology is a mathematical procedure that describes how features are spatially related and
ensures data quality of the spatial relationships. Topological relationships include following three
basic elements:

I. Connectivity: Information about linkages among spatial objects

II. Contiguity: Information about neighboring spatial object

III. Containment: Information about inclusion of one spatial object within another spatial object

Connectivity

Arc node topology defines connectivity - arcs are connected to each other if they share a
common node. This is the basis for many network tracing and path finding operations.

Arcs represent linear features and the borders of area features. Every arc has a from-node which
is the first vertex in the arc and a to-node which is the last vertex. These two nodes define the
direction of the arc. Nodes indicate the endpoints and intersections of arcs. They do not exist
independently and therefore cannot be added or deleted except by adding and deleting arcs.
Nodes can, however, be used to represent point features which connect segments of a linear
feature (e.g., intersections connecting street segments, valves connecting pipe segments).

Figure 4: Node showing intersection

Arc-node topology is supported through an arc-node list. For each arc in the list there is a from
node and a to node. Connected arcs are determined by common node numbers.

Contiguity

Polygon topology defines contiguity. The polygons are said to be contiguous if they share a
common arc. Contiguity allows the vector data model to determine adjacency.
The from node and to node of an arc indicate its direction, and it helps determining the polygons
on its left and right side. Left-right topology refers to the polygons on the left and right sides of
an arc. In the illustration above, polygon B is on the left and polygon C is on the right of the arc
4.

Polygon A is outside the boundary of the area covered by polygons B, C and D. It is called the
external or universe polygon, and represents the world outside the study area. The universe
polygon ensures that each arc always has a left and right side defined.

Containment

Geographic features cover distinguishable area on the surface of the earth. An area is represented
by one or more boundaries defining a polygon. The polygons can be simple or they can be
complex with a hole or island in the middle. In the illustration given below assume a lake with an
island in the middle. The lake actually has two boundaries, one which defines its outer edge and
the other (island) which defines its inner edge. An island defines the inner boundary of a
polygon. The polygon D is made up of arc 5, 6 and 7. The 0 before the 7 indicates that the arc 7
creates an island in the polygon.
Polygons are represented as an ordered list of arcs and not in terms of X, Y coordinates. This is
called Polygon-Arc topology. Since arcs define the boundary of polygon, arc coordinates are
stored only once, thereby reducing the amount of data and ensuring no overlap of boundaries of
the adjacent polygons.

Simple Features

Point entities: These represent all geographical entities that are positioned by a single XY
coordinate pair. Along with the XY coordinates the point must store other information such as
what does the point represent etc.

Line entities: Linear features made by tracing two or more XY coordinate pair.

 Simple line: It requires a start and an end point.

 Arc: A set of XY coordinate pairs describing a continuous complex line. The shorter the
line segment and the higher the number of coordinate pairs, the closer the chain
approximates a complex curve.

Simple Polygons: Enclosed structures formed by joining set of XY coordinate pairs. The
structure is simple but it carries few disadvantages which are mentioned below:

 Lines between adjacent polygons must be digitized and stored twice, improper
digitization give rise to slivers and gaps

 Convey no information about neighbor

 Creating islands is not possible

Topologic Features

Networks: A network is a topologic feature model which is defined as a line graph composed of
links representing linear channels of flow and nodes representing their connections. The
topologic relationship between the features is maintained in a connectivity table. By consulting
connectivity table, it is possible to trace the information flowing in the network

Polygons with explicit topological structures: Introducing explicit topological relationships

takes care of islands as well as neighbors. The topological structures are built either by creating
topological links during data input or using software. Dual Independent Map Encoding (DIME)
system of US Bureau of the Census is one of the first attempts to create topology in geographic
data.
  Polygons are formed using the lines and their nodes.

 Once formed, polygons are individually identified by a unique identification number.

 The topological information among the polygons is computed and stored using the
adjacency information (the nodes of a line, and identifiers of the polygons to the left and
right of the line) stored with the lines.

Fully topological polygon network structure

A fully topological polygon network structure is built using boundary chains that are digitized in
any direction. It takes care of islands and lakes and allows automatic checks for improper
polygons. Neighborhood searches are fully supported. These structures are edited by moving the
coordinates of individual points and nodes, by changing polygon attributes and by cutting out or
adding sections of lines or whole polygons. Changing coordinates require no modification to the
topology but cutting out or adding lines and polygons requires recalculation of topology and
rebuilding the database.

Triangular Irregular Network (TIN)

TIN represents surface as contiguous non-overlapping triangles created by performing Delaunay
triangulation. These triangles have a unique property that the circumcircle that passes through the
vertices of a triangle contains no other point inside it. TIN is created from a set of mass points
with x, y and z coordinate values. This topologic data structure manages information about the
nodes that form each triangle and the neighbors of each triangle.

Advantages of Delaunay triangulation

 The triangles are as equiangular as possible, thus reducing potential numerical precision
problems created by long skinny triangles

 The triangulation is independent of the order the points are processed

 Ensures that any point on the surface is as close as possible to a node

Because points can be placed irregularly over a surface a TIN can have higher resolution in areas
where surface is highly variable. The model incorporates original sample points providing a
check on the accuracy of the model. The information related to TIN is stored in a file or a
database table. Calculation of elevation, slope, and aspect is easy with TIN but these are less
widely available than raster surface models and more time consuming in term of construction
and processing.

The TIN model is a vector data model which is stored using the relational attribute tables. A TIN
dataset contains three basic attribute tables: Arc attribute table that contains length, from node
and to node of all the edges of all the triangles.

 Node attribute table that contains x, y coordinates and z (elevation) of the vertices
  Polygon attribute table that contains the areas of the triangles, the identification number
of the edges and the identifier of the adjacent polygons.

Storing data in this manner eliminated redundancy as all the vertices and edges are stored only
once even if they are used for more than one triangle. As TIN stores topological relationships, the
datasets can be applied to vector based geoprocessing such as automatic contouring, 3D
landscape visualization, volumetric design, surface characterization etc.

Raster Data Structure

In a simple raster data structure the geographical entities are stored in a matrix of rectangular
cells. A code is given to each cell which informs users which entity is present in which cell. The

(a) Entity model: It represents the whole raster data. Let us assume that the raster data belongs to an area where land is
surrounded by water. Here a particular entity (land) is shown in green color and the area where land is not present is
shown by white.
(b) Pixel values: The pixel value for the full image is shown. Cells having a part of the land are encoded as 1 and
others where land is not present are encoded as 0.
simplest way of encoding a raster data into computers can be understood as follows:

(c) File structure: It demonstrates the method of coding raster data. The first row of the file
structure data tells that there are 5 rows and 5 columns in the image, and 1 is the maximum
pixel value. The subsequent rows have cells with value as either 0 or 1 (similar to pixel values).

Run length encoding

 Reduction of data on a row by row basis

 Stores a single value for a group of cells rather than storing values for individual cells
 First line represents the dimension of the matrix (5×5) and the number of entities (1) present. In second and
subsequent lines, the first number in the pair represents absence (0) or presence (1) of the entity and the second
number indicates the number of cells referenced.
Block encoding

 Data is stored in blocks in the raster matrix.

 The entity is subdivided into hierarchical blocks and the blocks are located using coordinates.
 The first cell at top left hand is used as the origin for locating the blocks

Chain encoding

 Works by defining boundary of the entity i.e. sequence of cells starting from and returning to the given origin

 Direction of travel is specified using numbers. (0 = North, 1 = East, 2 = South, 3 = West)

 The first line tells that the coding started at cell (4, 2) and there is only one chain. In the second line the first
number in the pair tells the direction and the second number represents the number of cells lying in this direction.

Quadtree
 A raster is divided into a hierarchy of quadrants that are subdivided based on similar value pixels.

 The division of the raster stops when a quadrant is made entirely from cells of the same value.

 A quadrant that cannot be subdivided is called a leaf node.

Raster vs Vector Models

vector data model: [data models] A representation of the world using points, lines, and polygons.
Vector models are useful for storing data that has discrete boundaries, such as country borders,
land parcels, and streets.
raster data model: [data models] A representation of the world as a surface divided into a regular
grid of cells. Raster models are useful for storing data that varies continuously, as in an aerial
photograph, a satellite image, a surface of chemical concentrations, or an elevation surface.

Data Quality

Data quality is the degree of data excellence that satisfies the given objective. In other words,
completeness of attributes in order to achieve the given task can be termed as Data Spatial Data
quality can be categorized into Data completeness, Data Precision, Data accuracy and Data
Consistency.

 Data Completeness: It is basically the measure of totality of features. A data set with
minimal amount of missing features can be termed as Complete-Data.
 Data Precision: Precision can be termed as the degree of details that are displayed on a
uniform space. Data Accuracy: This can be termed as the discrepancy between the actual
attributes value and coded attribute value.

 Data Consistency: Data consistency can be termed as the absence of conflicts in a

particular database.