Homework 01: Implementation of the DT/VD

Deadline is 2019-12-02 13:00.

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

20% of final marks

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

• Overview
• What you are given to start
• Data structure to use
• Algorithms to implement
• Good to know
• The report to submit
• Marking
• Bonus (+10%)
• What to submit and how to submit it

Overview

The aim of this assignment is to implement, from scratch, a Delaunay triangulator, and extract the Voronoi diagram from it. The algorithm that must be implemented is an incremental insertion based on flips, and the program created will be an interactive, as shown above (it shows the “good answer”).

What you are given to start

hw01-code.zip

We give you the skeleton of the Python program:

1. geo1015_hw01.py is the main(). You are not allowed to modify this file!
2. interface.py is what controls the interface. You are not allowed to modify this file!
3. my_code_hw01.py is where all your code should go. You have to complete the DT class, and you are allowed to add new functions in this unit (please do not include any other unit you code, add your code to that single file). You are only allowed to import modules from the Python standard library (if in doubt, google or ask us).

If you run geo1015_hw01.py the interface appears and you can click in the window to add points; at this moment only points are added, your task is to implement the Delaunay triangulation (and extract the Voronoi diagram from the DT). If you construct appropriately the data structures, they will be automatically displayed in the interface.

The program has 3 keys:

• keyboard ‘d’ to toggle between the DT and the VD
• keyboard ‘q’ to quit the program
• keyboard ‘r’ to reset the DT/VD to an empty one

Data structure to use

The data structure to use for the DT is prescribed: it is the simplest triangle-based data structure as described in Section 3.5 of the book. It considers the triangle as being its atom and stores each triangle with 3 pointers to its vertices and 3 pointers to its adjacent triangles.

In our case, in Python this means that each triangle is a list (array) of 6 values, the first 3 are the indices (integer, 0-based) of the 3 points, and the 3 others of the indices of the neighbouring triangles. We keep the points/vertices in a list self.pts and the triangles in a list self.trs.

Observe that the constructor of the class DT (__init()__) already contains the “big triangle” (see Figure 3.12 in the book) that is necessary to initialise the DT (do not modify this!):

self.pts = []
self.trs = []
#- create infinite triangle
#- create 3 vertices
self.pts.append([-10000, -10000])
self.pts.append([10000, -10000])
self.pts.append([0, 10000])
#- create one triangle
self.trs.append([0, 1, 2, -1, -1, -1])

This is why when you start the program you see that the DT/VD already contains 3 points and one triangle.

Notice also that:

• each point is an array [x, y]
• the big triangle is formed of 3 points placed faraway, and since there are no triangles adjacent to this one the neighbours are set to -1

Algorithms to implement

You need to implement an incremental algorithm based on flips, as described in the book. You are not allowed to reconstruct from scratch the DT after each insertion, it must be updated locally.

For the point location, you are not allowed to do it brute-force (ie checking all triangles against the newly inserted point), you have to implement a “walking” function; this is described in the book.

Good to know

• the canvas of the program given only allows the insertion of new points in the square [0, 500] so there will never be a point outside that range
• the solution does not have to be robust for points that are collinear or cocircular (and other complex cases), that is the points given will be in general position.

The report to submit

You need to submit a very simple report explaining briefly how you implemented the key parts (the walk, the flips, etc.) and explain what works (and what not).

We expect maximum 2 pages for this.

Marking

Bonus (+10%)

If you want to get (potentially) 10% bonus, you can make your code robust, that is then we do not expect that the points are in general position.

If you do so, describe in your report how you made your code robust (then the report can be longer).

What to submit and how to submit it

You have to submit a total of 2 files:

1. the Python file mycode_hw01.py, where your name, and that of your colleague, is clearly identified at the top of the file.
2. report in PDF format (please no Word file)

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: 2019-10-31]