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
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
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 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)
Two function of BOV were overwritten:
- The shortcut function
- The help function
- 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
- 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
- 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
- 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
mkdir build
cd build
cmake ..
make
bin/Devillez_Poncelet_Fortune