Representation and algorithms

Discusses the representations of spatial data for field- and object-based models, and some algorithms that are usd to process data.

Computing with geospatial data

An algorithm is a specification of computational process required to perform some operation.

The efficiency of an algorithm is usually measured in terms of the time the algorithm uses, called time complexity or the amount of storage space required, called space complexity.

Use the big-oh notation to classify algorithms according to time complexity.

• O(1) very fast
• O(logn) Fast
• O(n) Moderate

The discrete Euclidean plane

line simplification reducing the level of detail in the representation of a polyline, while still retaining its essential geometric character.

The spatial object domain

• Spaghetti: represents a planar configuration of points, arcs, and areas. (a list of points)

  A: [1,2,3,4]

• Node arc area (NAA)
• Doubly connected edge list (DCEL)

Representations of field-based models

Regular tessellated representations

• Tessellations: a partition of the plane as the union of a set of disjoint area objects or the process of fitting shapes together in a pattern with no spaces in between
• Regular polygon
  • Vertex figure
• Regular tessellation: participating polygons are regular and equal
  • Square grid: it is most commonly used regular tessellation
• Irregular tessellation: participating polygons are not all regular and equal
  • Triangulated irregular tessellation(TIN): it is the most commonly used irregular tessellations
    • Delaunay triangulation
      • each circumcircle of a constituent triangle does not include any other triangulation point within it.
    • Proximal polygon
    • Voronoi diagram: A Voronoi diagram is a partitioning of a plane into regions based on distance to points in a specific subset of the plane.

Fundamental geometric algorithms

• Distance and angle between points
• Area of a simple polygon
• Point in polygon
  • Semi-line algorithm: checks for odd or even numbers of intersections of a semi-line with polygon
  • Winding algorithm: sums bearings from point to polygon vertices
• Point of intersection
• Segment intersection

Vectorization and rasterization

• Vectorization: converting data from raster to vector format

Network representation and algorithms

• Adjacency matrix
• Adjacency list(a: (b,20),(c:15)): good balance between storage efficiency and computational efficiency
• Depth first traversal: explores as far as possible along each branch before backtracking
  • In order: left->root->right
  • Pre order: root->left->right
  • Post order: left->right->root
• Breadth first traversal: begins at the root node and then visits all nodes level by level
• Shortest path
  • Dijikstraz
  • A*

Questions

• What are common representations in GIS?

object: spaghetti and node-arc-area field: tessellations of space

• What is an algorithm?

A specification of the computational processes required to perform an operation