LMECA2170 - Fortune's algorithm

How to use

Simply execute the file Devillez_Poncelet_Fortunes and it will show our implementation of fortune algorithm with 20 points and a sweep animation. Some options are available. You can have the following list with Devillez_Poncelet_Fortunes -h:

-b, --benchmark [n]: output the time taken to apply the algorithm on the [n] points
-a, --animation [mode]: specify the level of animation
 * 0: No animation
 * 1: Manual mode
 * 2: Step mode
 * 3: Sweep mode
-h, --help: Print this help
-r, --resolution [n]: specify the max number of points [n] to draw the beachline
-p, --points [n]: specify the number of points [n] to use (default: 20)
-s, --save: specify to save the animation
-f, --fps [n]: specify the number of fps to save (default: 10)
-v, --version: Print the version number

--benchmark

Will apply the fortune algorithm on [n] points and return the time taken to initialise the structures and to apply the algorithm in microseconds.

If other flags are specified with -b, they will not be taken into account.

One can also use a small python CLI to perform a benchmark and display results:

python3 cli.py benchamrk --help

python3 benchmark run
python3 becnhmark plot

Animation

There are 4 mode of display:

• No animation: it will directly output the voronoid
• Manual: you can move the sweep line step by step or event by event
• Step mode: the sweep line will move event by event
• Sweep mode: the sweep line will move at constant speed

Shortcuts

Shortcuts are design for a AZERTY keyboard but the are mapped to the physical key (so on a QWERTY press Q instead of A for example)

Disclaimer

Two function of BOV were overwritten:

• The shortcut function
• The help function

Reference

• Computanional Geometry book for the main idea of the algorithm
• Course's slides
• Henri Devillez implementation: to check the implementation of the sorted queue
• Steven Fortune implentation: To compare how the original implentation was done

V0

V1

Todo

V0 - It's done

• Have a working Algo -> I think it's ok
• Have a basic plot
• Free everything correctly
• Benchmark the V0
• Should be able to select random input of n points
• Take an gif of the working algorithm to see the evolution and add it to the git

V1

• Clean the code
  • Better use of functions
  • Better name for functions
  • Add comment to the code
• Improve the speed
  • Improve the heap
  • Improve processSite
  • Improve processCircle
  • Improve circle creation
  • Benchmark after the upgrade
  • Tool to check function call and function duration (min, max, average, total) ?
  • Rebalance tree (maybe variable with depth ?) and benchmark -> Would be very nice to do :3 -> partially done
• Add a verbose environnement
  • Add general option for verbose
  • Add relevant print
• Check if memory is clean (valgrind)
• Add nice tool for visual
  • Each element shoulde be toggable
  • Help should gives shortcut
  • Speed of sweep line should be variable
  • Sweep line should be able to stop
  • manual increase for sweep line should be ok
  • Should be able to adjuste resolution of lines (beachLine, cicle) (during ?)
  • should be able to switch between different animation type
• Add nice visual
  • Sweepline
  • Beachline
  • Site event
  • Circle Event (differentiate the valid one from the others) (and keep memory of those events)
  • Circle from circle event (dashed)
  • Next Event should be highlighted
  • Finite vertex
  • Vertex in construction
  • semi-finite vertex
  • Bound everything to a box
  • Vertex of the He
  • Finish animation when all bpx are outside the box (add flag ?)
• Clean the data
  • verify if when add points
• Flags
  • Add a flag to save the animations
  • Flag for listing the help

V2

• Add -O3 to make
  • Benchmark this
  • Test othe flags and benchmark them -> No need
• Add a realtime ploting execution time / data-size
  • Should be able to plot with different color different option and choose which one to plot. (Data should be the same).
• Add tool to save anim to gif/save pictures
• Should be able to go back in time during animation
• Should be able to add point (and auto update)
• Process images
  • Basic input with pictures http://phrogz.net/js/image-voronoi/
  • Should process any image in input

Installation

mkdir build
cd build
cmake ..
make
bin/Devillez_Poncelet_Fortune