Area Optimal Polygonisation

This is a project to implement, test and evaluate different local and global optimisation algorithms for solving the area optimal polygonisation problem, using the CGAL library.

This software was written collaboratively by Nikos Alexandris and Panagiotis Iatrou.

Algorithms implemented

Local

• Incremental
• Convex Hull

Global

• Local Search
• Simulated Annealing
  • Local Step
  • Global Step
  • Subdivision

Evaluation

x axis: number of vertices
y axis: score

• Minimization (the goal is to minimize y)

• Maximization (the goal is to maximize y):

Build and Run instructions

Dependencies

• A standard C++ compiler with C++14 support
• CMake
• CGAL
• Boost

A Dockerfile is also provided for building the project in a container.

Build

mkdir build
cd build
cmake .. -DCMAKE_BUILD_TYPE=Release
cmake --build .
cd ..

Run

./build/evaluate -i instances/data/images -o stats.txt

Visualisation of results

python scripts/mitsos.py stats.txt

Docker build

docker build -t <image_name> -f Dockerfile .
docker run -it --rm <image_name>
# in docker shell now...
cd root/AreaOptimalPolygonisation/
# same steps as Build from here on...