Homework 02: Terrain simplification

Deadline is 2018-12-21 13:00.

Late submission? 10% will be removed for each day that you are late.

You’re allowed for this assignment to work in a group of 2 (and thus submit only one report for both of you). If you prefer to work alone it’s also fine (but we don’t recommend it).

Overview

In this assignment you will convert a 2D regular grid to a TIN. In order to smartly decide which vertices to use for the TIN, and how many vertices are needed in the TIN, you will implement a TIN simplifcation algorithm based on refinement. It should minimise the number of vertices, given a user-defined maximum error-threshold. The resulting TIN should not exceed this error-threshold anywhere. However, in order to check if this is really the case, the last part of the assignment is to compare the TIN that you generate with the original grid by computing the elevation difference at each pixel location of the grid.

In short, for this assignment you will

  1. convert an input grid file to a set of points, ie one point for each pixel (except the nodata pixels),
  2. construct a triangulation from this point set using a TIN simplification algorithm based on refinement, ie with the greedy insertion algorithm and the vertical importance measure that are introduced in Lesson 08, and
  3. create a new grid that contains for each pixel the elevation difference between the corresponding pixel in the input grid (its centre) and the generated TIN.

Everything should be implemented in Python, and the only external modules that you are allowed to use are rasterio, numpy and scipy.

What you are given to start

code_hw02.zip

We give you the skeleton of the Python program and an input file:

  1. geo1015_hw02.py is the main(). You are not allowed to modify this file!
  2. mycode_hw02.py is where all your code should go. The functions defined there must be written, and you are not allowed to change the input parameters. You are of course allowed to add any other functions you want. You are only allowed to import modules from the Python standard library (anything you installed through pip is thus not allowed, except rasterio, scipy and numpy).
  3. params.json: a very simple JSON file that defines the error-threshold, what the input file is, and where to write the output files. You may assume that this is a valid file.
  4. el_capitan.tif: our input grid, a piece of the SRTM dataset. The coordinates are in meters.
  5. el_capitan_full.obj: example OBJ file of the full (non-simplified) triangulation of el_capitan.tif

The geo1015_hw02.py script will automatically convert your TINs to the OBJ format. These OBJ files can be visualised with a 3D viewer like Meshlab so that you can quickly see if your triangulation is correct.

Specifications of the output files

You’ll have to deliver two types of output files:

  1. OBJ files with the simplified TIN. Provided that you deliver a list of TIN vertices, these files are written for you by the geo1015_hw02.py script as stated above.
  2. a grid with the elevation differences between the TIN and the input grid, computed by subtracting the grid elevation from the TIN elevation. There should only be one band that stores for each pixel an elevation difference as a float32. The width, height, transform, crs, and nodata values should be the same as the input grid.

Some pointers on how to use SciPy Delaunay

You may use SciPy Delaunay for the implementation of the TIN refinement algorithm. However, this library has some caveats and if you are not careful it may crash.

Caveat 1: 32-bit floating point arithmetic

SciPy Delaunay works with 32-bit floating points, a number type that is limited in the number of significant figures it can represent. Consequently, it has poor precision with very large numbers, such as the UTM coordinates in the input grid of this assignment. Instead of the original UTM coordinates you should therefore use smaller numbers, ie you could translate the coordinates to the origin (minx, miny) before using them with SciPy Delaunay.

Caveat 2: Creating the initial TIN

The TIN refinement algorithm requires an initial triangulation. You should make sure that

  1. the intial triangulation completely covers the 2D bounding box of the input points,
  2. there are at least 2 triangles, and
  3. that the vertices of this initial triangulation are in general position.

You can set the elevation of these initial triangles to the average elevation of all the input points. Watch out: you should not write the vertices of the initial triangles to the output.

Other tips and pointers

What to submit and how to submit it

You have to submit a total of 10 files:

  1. the Python file my_code_hw02.py, where your name is clearly identified at the top of the file,
  2. 4 OBJ files with simplified TINs, for the input file el_capitan.tif, for the error thresholds 10, 20, 50 and 100, respectively named tin_10m.obj, tin_20m.obj, tin_50m.obj, tin_100m.obj,
  3. 4 GeoTIFFs with the differences between the input raster and the simplified TIN for the error thresholds 10, 20, 50 and 100, respectively named diff_10m.tif, diff_20m.tif, diff_50m.tif, diff_100m.tif, and
  4. a brief report in PDF format (2-5 pages with figures/graphs) where you elaborate on the results with the 4 different thresholds. Discuss things like: What is the statistical distribution of the errors in the difference grids? Does the maximum error exceed the error threshold and if so why? Is there a spatial pattern to the errors? How many points are left at each threshold? How does the threshold affect the computation time?

Do not submit your assignment by email, but upload the requested files to this Dropbox file request page. Make sure that you put the full name of one of the member of the team (only one is sufficient). You’ll get a confirmation email when everything has been successfully uploaded, keep it in case things go wrong.

[last updated: 2018-12-03 11:12]