Spatial object/Geoobject: element to model real world data in geographic information system

Are described by spatial data (geodata)

Spatial information: custom-designed spatial data

The difference is?

1. Geometry
2. Topology

Exists everywhere, without boundaries

Complete

Collectable only on distinct points

Examples: ground level, temperature, precipitation, air pressure, accessibility

www.wetteronline.de

https://stackoverflow.com

Object-based

• Space is populated by discrete, identifiable entities each with a geospatial reference (point, line, surface)
• Particularly suitable for discrete objects

Field-based

• Geographic information is regarded as collections of field spatial distributions
• Each distribution may be formalized as a mathematical function from a spatial framework to an attribute domain
• Particularly suitable for continua

Continuous

Differentiable

Isotropic - Independent of direction

Anisotropic - Properties vary with direction

Geometry

• Describes the (absolute) spatial location of an object in a 2- or 3-dimensional (metric) space
• Information about the position and extent based on a spatial reference system
• Implemented by geometrical data types, based on
• Vector data model
• Raster data model

http://upload.wikimedia.org/

Topology

• This is spatial relations between spatial objects
• Geometry of the relative position
• Is independent of extent and shape

http://www.openstreetmap.de/

Topological transformations - Invertible, bijective, and continous (homeomorphism, elastic deformation)

• Translation • Rotation • Stretching • Reflection • Distortion

Focus on sets of points, the concepts of neighbourhood, nearness, and open set

All topological properties are definable in terms of the single concept of neighbourhood

A topological space is a collection of subsets of a given set of points S, called neighbourhoods, that satisfy the following conditions

• Every point in S is in some neighbourhood (N1)
• The intersection of any two neighbourhoods of any point p in S contains a neighbourhood of p (N2)

Formal description of binary topological relations: 9-intersection model

Intersections between interior, boundary and exterior of objects

512 possible, 8 reasonable matrices (for polygons)

Levels or scales of measurement

Level of measurement refers to the relationship among the values that are assigned to the attributes for a variable

Layer concept

• Different characteristics of spatial objects are separated in different layers
• Separation based on objects or single attributes
• No hierarchy
• Layers can be analysed and presented separately
• Aggregation and overlay of layers possible
• Deduced from the principle data of separating map layers for printing (classical cartography)

Class concept

• A class comprises objects belonging to the same theme
• Hierarchical classification with subset relation between classes

The entries of the matrix (numerical values representing the object identifier or attribute values) are interpreted as grey scale values

Euclidian distance is not defined

• City block metric (4 neighbours)
• Chessboard distance (8 neighbours)

Points can only be represented by approximation

• Lines - Connected sequence of pixels
• Areal objects - Connected area of pixels

Basic morphological operations: • Dilatation • Erosion

Particularly suited to describe continuous and areal themes

Refined raster: representation of objects is more accurate but also higher memory requirements and computing time

Guideline: raster width half as wide as the smallest element/distance which should be represented

Lossless compression techniques

• Chain code/Crack code - Stores the direction in which pixels with the same value are

• Run length encoding - Stores the number of adjacent pixels with the same value in a row

Lossless compression techniques

• Block code - Decomposition into squares which are as big as possible. Only the position and size of the squares has to be stored

• Block code - Three examples (Greedy approach)

Multiple elements as one geometry

Geometry classes

Particularly suited to represent discrete objects

Relatively little memory requirements

Potentially infinite amount of precision

Discretization

• Move intersection point to the nearest grid point
• Split lines so as to join at the moved intersection point
• Problem: Shift of the lines is not constricted

Loss of information

Point • Pixel whose center is closest to the original point

Line • Pixels intersecting the original line • Bresenham algorithm (1962)

Polygon

• Determine for every pixel if it is inside the polygon
• Polygon based fill algorithm

Point-in-polygon

Semi-line algorithm

• Draw a ray out from the point
• Count the number of times that the ray intersects with the boundary of the polygon

Winding number algorithm

• Consider the triangles which are defined by a line segment of the boundary and the point

Polygon based fill algorithm

For each grid row

• Calculate the intersection points between the row and the edges of the polygon
• Sort the intersection points with respect to the x-axis
• All pixel between an intersection point with odd position and his successor belong to the polygon

Ambiguous, manually control necessary

Input: binary image

Outline extraction for polygons

• Determine all edge pixels
• Line following over the edge pixels and transformation of their center into a cartesian coordinate system

Classification of basic patterns results in 6 classes

• Isolated point: no black neighbour
• Inner point: all neighbours sharing an edge with the pixel are black
• Insignificant: all black neighbours are adjacent

Centerline extraction for lines

• Determine the distance between the pixels which belong to the line and the closest pixel which does not
• Topological thinning:
• Classify all pixels ordered by this distance (pixel close to the border first), delete insignificant pixel immediately
• Classify remaining pixels again
• Extraction of nodes: calculate the center of gravity for connected nodes
• Line following (chessboard metric)

Raster topology

• Implicit contained, easy to calculate
• Problems occurring when using chessboard metric
• Lines can intersect without having an intersection point
• Polygons can overlap, although their boundaries do not intersect

Metric space implies topological space, i.e. it is possible to determine the topological relations between objects if their geometries are known

Access and computations are normally more efficient if the topology is given explicitly

Basic elements of topological data models:

• Vertex (V)
• Edge (E)
• Face (F)

Relations

• Same kind of elements: Adjacency

• Different kind of elements: Incidence

Spaghetti data structure

• Set of lists of points
• Redundant duplication of data
• Inefficient in space utilization
• Difficult to guarantee consistency
• Improvement: list of nodes

http://www.ikg.uni-hannover.de/lehre/katalog/gis/gisII_uebung

Spaghetti data structure

http://www.ikg.uni-hannover.de/lehre/katalog/gis/gisII_uebung

Edge list

• Topological relations between points and lines are stored explicitly

http://www.ikg.uni-hannover.de/lehre/katalog/gis/gisII_uebung

Winged edge (doubly connected edge list)

• For every edge the successor and predecessor w.r.t the right and left face are added
• Topological relations between lines are stored explicitly

• The sequence of arcs that bound an area is easily determined

Network represented as weighted graph

• Set of edges: {(ab,20), (ag,15), (bc,8), (bd,9), (cd,6), (ce,15), (ch,10), (de,7), (ef,22), (eg,18)}

• Adjacency matrix

Adjacency list

Field-based models

• Raw data: measurements, often irregularly distributed

Primary models

• Original data
• Usually vector data

Derivative models

• Interpolated values
• Regular grid
• Usually raster data

www.daserste.de/wetter/wetterstationen.asp

Isoline

• Lines connecting points with the same numerical values or the same properties
• Are neither borders nor edges

• Are closed
• Do not intersect or touch each other
• Areas are often filled
• Examples: isobar, contour line, isochron

http://www.bbc.co.uk

Interpolation

Nearest neighbour

• Every point gets the value of the nearest measurement
• Properties; • Exact • Local • Deterministic • Abrupt • Suitable for nominal attributes

http://skagit.meas.ncsu.edu/~helena/gmslab/interp/F1a.gif

Surface constructed of triangular faces

• Triangulation of reading points
• Rendering of the triangles

Properties

• Exact
• Local
• Deterministic (depends on the triangulation)
• Gradual

http://skagit.meas.ncsu.edu/~helena/gmslab/interp/F1b.gif

Discuss voronoi diagram?. 1page

Queries about this Session, please send them to: jmwaura@jkuat.ac.ke

*References*

• Geographic Information System Basics, 2012 J.E.Campbell & M. Shin
• Fundamentals of GIS, 2017 Girmay Kindaya
• GIS Applications for Water, Wastewater, and Stormwater Systems, 2005 U.M. Shamsi
• Analytical and Computer Cartography, 2nd ed. Keith C. Claike
• Geographic Information Systems: The Microcomputer and Modern Cartography, 1st ed. Fraser Taylor