Dual Graphs

We’ll have a mini-lecture at the beginning of class explaining this further.

Your Task

• Download the starter code.

The code contains a working Delaunay triangulation computation (from the lab from last time). Your task is to code the dual() method in the DCEL that produces a the dual graph of the Delaunay triangulation.

Notes:

• When you create a vertex of your dual graph (one for each face of the originalgraph), you have to give it coordinates. I have added two methods to Face to do this for you: barycenter() and circumcenter(). Use barycenter() initially, because it is easier to see if you are going wrong, but once your dual() is working, if you place the vertices of the dual at the circumcenter() of the corresponding face then the resulting figure is the Voronoi diagram (more on this Friday).
• The outer face turns into a vertex at infinity. I have changed the constructor of DCEL so that the DCEL will either be created with an outer face (by passing true to the first parameter of the constructor) or a vertex at infinity (by passing true to the second parameter).
• The drawing code does not draw the edges incident to a vertex at infinity. How could you make this work?
  

Turning it in

Turn it in on Canvas by Friday 11:55pm.