Fortune's Algorithm in Hyperbolic Space

This is an implementation of Fortune's Algorithm in the polar coordinate model of hyperbolic space. Based on this paper.

You can use the code as a header-only library. Alternatively, you can build an executable that calculates and draws a diagram based on a set of points read from a file. The output then looks like the following picture which shows a Voronoi diagram of N=500 points uniformly distributed across a disk in the hyperbolic plane of radius R=9. The red lines are the Delaunay triangulation that connects points whose Voronoi cells are neighboring.

How to use

This is a header only library that you can easily include to your project. Place the fortune-hyperbolic folder into a directory of your choice and include it in your CMakeLists.txt with

list(APPEND CMAKE_PREFIX_PATH <path/to/fortune-hyperbolic>)
find_package(Fortune_Hyperbolic)

target_include_directories(<your_target> PRIVATE ${Fortune_Hyperbolic_INCLUDE_DIRS})
target_link_libraries(<your_target> PRIVATE ${Fortune_Hyperbolic_LIBRARIES})

High precision floating point values from boost and MPFR are supported. If you wish to use these, set the CMake variable FORTUNE_USE_MPFR to TRUE.

This directory contains a sample application that computes and draws a Voronoi Diagram. See CMakeLists.txt for an example using MPFR. You need boost and MPFR installed for this.

Code Example

The following program allows you to compute a Voronoi Diagram from a set of sites

#include <geometry.hpp>
#include <utils.hpp>
#include <kernels.hpp>
#include <fortune.hpp>

#include <vector>

using namespace hyperbolic;
using floating_point_type = double;

int main() {
    // calculate the diagram
    VoronoiDiagram v;
    vector<Point<double>> sites = {
            {3, 2.43},
            {2, 2.19},
            {6, 0.87},
            {9.2, 1.23}
    };
    FortuneHyperbolicImplementation
            <FullNativeKernel<floating_point_type>, floating_point_type> 
            fortune(v, sites);
    fortune.calculate();
    
    // draw the diagram
    VoronoiCanvas canvas(v, sites);
    canvas.draw_diagram("out.svg");
}

Structure of the project

• fortune-hyperbolic: contains the header only library with the implementation
• experiments: contains an implementation of CGAL for calculation Voronoi Diagrams in the Poincare model and python scripts for comparison of the two versions
• tests: contains tests
• generator: contains a generator for uniform sampling of points in the hyperbolic plane

Documentation

See fortune-hyperbolic/docs/html for some Documentation generated by Doxygen.

How to Build

We use CMake. To build the example application in this project, use

mkdir build
cd build
cmake ..
cmake --build .

You can then execute the generator and let the main executable calculate the corresponding Voronoi diagram with the following commands

./generator -o sample.txt -N 500 -R 10
./main -i sample.txt -d diagram.svg

which samples 500 points uniformly distributed within a disk of radius 10 and then calculates their Voronoi diagram that is written to diagram.svg.