stripped-hds

Stripped halfedge data structure for parallel computation of arrangements of segments. Guillaume Damiand, David Coeurjolly and Pierre Bourquat.

This repository contains code, scripts and dataset.

Let us denote by SRC_DIR the root directory of the gitlab repository.

1. Data set

Each data is a text file containing a list of segments. In the gitlab repository, these files are compressed. To uncompress all the data files:

// We suppose the current directory is SRC_DIR

gunzip -r data/

2. Install required dependencies

• Boost, with components system and filesystem
• Intel TBB
• Qt5
• CGAL, with component Qt5

3. Compile the programs

// We suppose the current directory is SRC_DIR

mkdir builds
cd builds
mkdir release
cd release
cmake -DCMAKE_BUILD_TYPE=Release ../../src
make

4. Run the main program

One example of run:

// We suppose the current directory is SRC_DIR/builds/release

./parallel-arrangement -t1 ../../data/countries/FRA.txt -nbs 8 -nbt 8 -crop -draw

• The parameter after -t1 is the filename
• -nbs gives the number of strips
• -nbt gives the number of thread
• -crop is an option to crop segments in the strips
• -draw will draw the final arrangement

Run ./parallel-arrangement -h for an help showing all options. Press the h key to view the help of the interactive viewer.

5. You can use different scripts to reproduce results of the paper

5.1 To compare computation times of CGAL and our method, for GIS dataset.

// We suppose the current directory is SRC_DIR

./run-gis-test.sh 5

Run our program on all the gis data.

• 5 is the number of runs for each file (in the paper we use 5 runs);
• 1 is used by default.

Computation times of the method are stored in file times.dat; number of cells in nbcells.dat; and times of the different parts of our method in detailed-times.dat.

5.2 To draw computation time graphs for stochastics dataset

You need python3, numpy, matplotlib

// We suppose the current directory is SRC_DIR

python3 python_scripts/run_benchmark.py --log outputmixerP4.log --thread 1 2 4 8 16 32 --repeat 5 --crop data/mixerP4.txt

Run our program on the given dataset, and store the log output in a file.

• --log gives the log filename
• --thread gives the number of threads to test
• --repeat gives the number of runs for each file (in the paper we use 5 runs)
• --crop is an option to crop segments in the strips
• last parameter is a directory of a list of files to test. When a directory is used, the program is ran for each file in the directory.

In the paper we used:

python3 python_scripts/run_benchmark.py --log outputmixerP4.log --thread 1 2 4 8 16 32 --repeat 5 --crop data/mixerP4.txt 
python3 python_scripts/run_benchmark.py --log FRA.log --thread 1 2 4 8 16 32 --repeat 5 --crop data/countries/FRA.txt
python3 python_scripts/run_benchmark.py --log gauss-short.log --thread 1 2 4 8 16 32 --repeat 5 --crop data/gauss-short/
python3 python_scripts/run_benchmark.py --log gauss-long.log --thread 1 2 4 8 16 32 --repeat 5 --crop data/gauss-long/      
python3 python_scripts/run_benchmark.py --log best.log --thread 1 2 4 8 16 32 --repeat 5 --crop data/best/
python3 python_scripts/run_benchmark.py --log worst.log --thread 1 2 4 8 16 32 --repeat 5 --crop data/worst/

To visualize the results, you need to use plot_result.py, for example:

python3 python_scripts/plot_result.py --no-load --no-error outputmixerP4.log
python3 python_scripts/plot_result.py --no-load --no-error FRA.log
python3 python_scripts/plot_result.py --no-load --no-error gauss-short.log
python3 python_scripts/plot_result.py --no-load --no-error gauss-long.log
python3 python_scripts/plot_result.py --no-load --no-error best.log
python3 python_scripts/plot_result.py --no-load --no-error worst.log