Compute the largest empty rectangle inside general polygons with holes.

Automatically placing labels on maps is a problem relevant geographic information systems. In this case, the shape of the label and, thus, the aspect ratio is known.

This repository contains implementations of two algorithms for finding (approximate) largest rectangles inside general polygons with holes:

• ap: axis-aligned rectangles
• rr: arbitrary rotated rectangles

We switched to CMake. In the project folder, enter the following to obtain the previously mentioned binaries:

mkdir build
cmake ../
make

• Make library out of project and support common GIS format
• Use CGAL for geometric primitives