Delaunay triangulations and extensions

This C program is a O(n log(n)) "divide and conquer" implementation of the Delaunay triangulation of a given set of points. It is extended with

• an application of the Delaunay triangulation: efficient computation of the Euclidian Minimum Spanning Tree thanks to Kruskal's algorithm,
• a linear time implementation of the derivation of the Voronoi diagram from the Delaunay triangulation,
• four types of visualization (see Visualization)

This program was written as part of the "LMECA2170 - Numerical Geometry" course project course at UCLouvain (website: https://perso.uclouvain.be/vincent.legat/zouLab/meca2170.php?action=valves).

Any source of inspiration is explicitely written in the code source.

Structure of the project

The project should contain:

• this file (README.md),
• the description of the structure of the program in CMakeLists.txt,
• a src directory containing the the source code of your program,
• a doc directory containing more documentation,
• a deps directory containing the BOV library.

Each source code file (.c, .h) in the src directory comes with a description in the header of the latter.

See doc/COMPILING.md for a step by step tutorial on how to build the program, see doc/tutorial.md for a step by step tutorial on how to use the BOV library, see deps/BOV/include/BOV.h for help on the BOV library functions and see deps/BOV/examples/ for more examples using the BOV library.

Usage

See doc/COMPILING.md for a tutorial on how to build the program. Here are some examples of usage, in src/config.h.

Test the rapidity of the triangulation:

#define EMST                        0
#define VORONOI                     0

#define FINAL_MODE                  0
#define HISTORY_MODE                0  
#define VORONOI_FINAL_MODE          0
#define VORONOI_CIRCLES_MODE        0

See all the visualizations (see Visualization):

#define EMST                        1
#define VORONOI                     1

#define FINAL_MODE                  1
#define HISTORY_MODE                1  
#define VORONOI_FINAL_MODE          1
#define VORONOI_CIRCLES_MODE        1

Compute and see final results of Delaunay triangulation and Voronoi diagram (see Visualization):

#define EMST                        0
#define VORONOI                     1

#define FINAL_MODE                  1
#define HISTORY_MODE                0  
#define VORONOI_FINAL_MODE          1
#define VORONOI_CIRCLES_MODE        0

Visualization

There are four visualization modes : FINAL_MODE, HISTORY_MODE, VORONOI_FINAL_MODE and VORONOI_CIRCLES_MODE.

FINAL_MODE = 1

Shows the final result of the Delaunay triangulation, EMST edges are in red if EMST is executed (see Parameters).

HISTORY_MODE = 1

Show the whole "divide-and-conquer" execution of the Delaunay triangulation, and the execution of Kruskal's algorithm if EMST is executed (see Parameters). It saves the execution in HISTORY_FILE where current states were saved during the execution. If ERASE_AFTER is set to 1 (see Parameters), then the file is erased just after the visualization.

VORONOI_FINAL_MODE = 1

Shows the final result of the derivation of the Voronoi diagram from the Delaunay triangulation, if Voronoi derivation is executed (see Parameters). There is the possibility to show or not the Delaunay triangulation with it during the animation.

VORONOI_CIRCLES_MODE = 1

Shows the computation of the vertices of the Voronoi diagram (the circumcenters of the triangles of the Delaunay triangulation), and the derivation of its edges. There is the possibility to show or not the Delaunay triangulation with it during the animation.

Complexity

The divide-and-conquer is in O(n log(n)), and so are both extensions.

Suppose a Delaunay triangulation is given, applying Kruskal's algorithm to it requires O(n log(n)) operations since there are O(n) edges in the triangulation, and finding the Voronoi triangulation takes O(n) operations.

Parameters

All execution, visualization, and other parameters lie in src/config.h file.

Here is a description for each execution parameter:

• N_POINTS: number of points generated
• UNIFORM: boolean variable to decide if the generation is uniform or not
• EMST: boolean variable to decide if the Euclidian Minimum Spanning Tree is computed
• VORONOI: boolean variable to decide if the Voronoi diagram is computed
• FINAL_MODE: visualization in FINAL_MODE is executed (see Visualization)
• HISTORY_MODE: visualization in HISTORY_MODE is executed (see Visualization)
• VORONOI_FINAL_MODE: visualization in VORONOI_FINAL_MODE is executed (see Visualization)
• VORONOI_CIRCLES_MODE: visualization in VORONOI_CIRCLES_MODE is executed (see Visualization)
• ERASE_AFTER: the HISTORY_FILE is erased after usage (see Visualization)

Here is a description for some visualization parameter (we skip the message configurations, see config.h):

• N_SECOND_STEP: duration in seconds of one step for the HISTORY_MODE visualization
• N_SECOND_CIRCLE: duration in seconds of one step for the VORONOI_CIRCLES_MODE visualization
• N_SECOND_PAUSE: duration in seconds of one pause for the VORONOI_CIRCLES_MODE visualization
• POINT_WIDTH: basic point width
• POINT_COLOR: basic point color
• EDGE_WIDTH: basic edge width
• EDGE_COLOR: basic edge color
• EMST_EDGE_WIDTH: Euclidian Minimum Spanning Tree edge width
• EMST_EDGE_COLOR: Euclidian Minimum Spanning Tree basic edge color
• DUAL_EDGE_WIDTH: Voronoi diagram edge width
• DUAL_EDGE_COLOR: Voronoi diagram edge color
• CIRCLES_WIDTH: circles width
• CIRCLES_WIDTH: circles color
• CIRCLES_CENTER_WIDTH: center of circles width
• CIRCLES_CENTER_COLOR: center of circles color
• CIRCLES_RESOLUTION: number of points for visualizing a circle

Finally, here is a description of the only parameter concerning Voronoi diagrams:

• X_MARGIN: x coordinate of the "infinite" vertex of a Voronoi diagram, must be great in absolute value compared to the maximum x coordinate of the set of points