Voronoi

This is my modified version of Steve Fortune's voronoi code. I have added memory management which removes all memory leaks and allows the voronoi computation to be executed multiple times in the same application without eventually running out of memory.

You can download the code here: voronoi.tar

Description of Changes

The following changes were made to the original code. The purpose of these changes is basically to keep a memory map of all the allocated memory during the computation of the voronoi diagram, and then allow the memory to be freed at the end of the computation.

vdefs.h

• inserted void free_all(void); function declaration with the other memory functions. Calling this function will free all the memory that has been allocated so far. This function should be called after the voronoi computation is completed for a specific input.

memory.c

• inserted char** memory_map; and int nallocs=0; variables to store and manage the memory map.
• modified the char* myalloc(unsigned n) function to record all allocated memory into the memory map.
• inserted void free_all(void); function to de-allocate all the memory in the memory map.

main.c

• inserted function call to free_all(void); in the main function de-allocate all the memory used during the voronoi computation.

Multiple Execution of the Voronoi Code

If you are running the voronoi code from the command prompt on a single data set, then you don't need to make use of my changes; you can just use the original version of the code. However my changes are useful if you wish to execute the voronoi computation multiple times from within another application. You may notice that, even in my modified version, the voronoi application is still set up to run as a command line program on a single data set. You need to make some additional changes that are specific to your application in order to incorporate the voronoi computation for multiple execution. Here I will give you some suggestions about the way I incorporated the voronoi program into my own application.

1. Copy the voronoi source files into a subdirectory of your project, where they will be built by your application.
2. Rename the main.c file to main_file.c (or something else), so it doesn't conflict with your own main.c file.
3. Rename the main() function in the main_file.c to compute_voronoi (or something similar) and don't forget to update vdefs.h to include this function.
4. You may wish to pass your data points as a parameter to this function, and perhaps have the resulting diagram or triangulation returned as the return value of the function. In this case, you need to modify the readsites() function (in the main_file) to use your data instead of reading from the input, and also the voronoi(Site*(*nextsite)()) function so that it populates your return structure instead of outputting the result to a file.
5. Now in your application you can call triangulation=compute_voronoi(your_data) to execute the voronoi computation on a specific data set.
6. Once you are finished with the triangulation, be sure to call free_all() from your application to clean up the memory.
7. This allows you to iteratively compute voronoi regions on different data sets, while using the memory efficiently.