BSysE552 – Data Structures and Algorithms for Geographic Information Systems

 

Instructor:

Manoj Karkee (manoj.karkee@wsu.edu)

Text:

Algorithmic Foundations of Geographic Information Systems, Marc van Kreveld, Juig Nievergelt et. el, editors.

References:

• GIS: A computing perspective. Worboys and Dukham. Second edition.
• Computational geometry. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkoph.

Syllabus:        

Week 1 and 2 (May 7 to May 20):

• Spatial Data Structures
  • Vector and Raster Representation
  • Voronoi Diagrams and Delaunay Triangulations
  • DCEL Data Structure
  • Quad-edge data structure

Week 3  and 4 (May 21 to June 3):

• Digital Elevation Models and TIN algorithms
  • Flow direction and Flow accumulation
• Graphs and Search Algorithms; Dijkastra’s Algorithm

Week 5 and 6 (June 4 to June 17):

• Geometric Algorithms
  • Divide and conquer, line sweep and incremental construction
  • Area of triangle, area of a convex and non-convex polygon
  • Orientation test, collinearity, betweenness, segment intersection test
  • Point-in-polygon, Convex hulls, Closest pair points

Week 7 and 8 (June 18 to July 1st):

• Line and Terrain simplification Algorithms
• Visibility; Visibility of Terrains

Week 8 and 9 (July 2nd to July 15th):

• Visualization and Virtual Reality
  • Visualization of TIN
  • Hidden Surface Removal
  • Level of Details
  • Virtual reality hardware and software; Cluster Computing, CAVE

Week 10 (July 16th to July 22):

Final Project