This is the Salzburg Database of Geometric Inputs, a repository of graphs for testing and benchmarking your computational geometry implementations.

All data can be found in the db directory. It can be downloaded either directly or with git-annex using git clone https://sbgdb.cs.sbg.ac.at/db/.git followed by git annex get in the working copy directory. Git annex enables you to also get specific files only.

At the moment, our repository consists of random simple polygons, with and without holes, produced with different generators. Furthermore, we have instances of specific polygons such as the Koch snowflake.

Releases

The latest release of the data is sbgdb-20200507, released on May 7, 2020. This data-set is fixed and will not see updates. It can also be retrieved from zenodo; its persistent identifier is doi:10.5281/zenodo.3784788.

Future updates will happen in the work-in-progress directory wip, which started as a copy of the previous release. In time, this data-set will become the next release.

Citing this dataset

If you use data or tools provided by this database, we would appreciate a short email to held@cs.sbg.ac.at with a description of how you use our data or tools. This aids us in estimating what parts are used and useful and will help guide the direction of this project.

In any case, if you use this database while working on a publication or to get some other real work done, please:

  1. provide the URL of this database, and, if applicable,
  2. cite the following paper: Salzburg Database of Polygonal Data: Polygons and Their Generators; Günther Eder, Martin Held, Steinþór Jasonarson, Philipp Mayer, and Peter Palfrader; Data in Brief, 31:105984, August 2020; doi:10.1016/j.dib.2020.105984.

We also provide BibTeX snippets.

Formats

The graphs in this repository are provided in xz-compressed graphml with additional attributes for storing the vertex coordinates of the embedding as well as for instance multiplicative edge weights.

Most graphs are edge weighted with random weights. This is for users who would like to use and test their code with weighted input. Users are of course free to ignore the weights and assume unit weights if it makes sense for their use-case.

Recent Generators

RPG - Random Polygon Generator

rpg was originally presented in Auer and Held (CCCG’96). rpg implements various algorithms to generate polygons described in that paper, such as Quick Star, Steady Growth, Space Partitioning, and 2-opt Moves. Furthermore, its xmono backend implements Zhu et al’s (CGTA 1996) algorithm for generating x-monotone polygons, and triangle generates polygons by searching for feasible edges within a random triangulation of the vertices. rpg can also produce polygons with holes and smooth sharp corners; please see rpg’s readme.
read more

Koch Snowflake

The code make_koch_snowflake generates instances of Koch’s snowflake curve, optionally in a nested variant, and make_koch_snowflake_quad generates instances of Koch’s rectilinear snowflake. Source code for genpoly-koch-snowflake and genpoly-koch-snowflake-quad is available. For the (triangle-based, classic) snowflake, see /db/wip/polygons/contrived/koch-snowflake/ for polygons and /db/wip/polygons-with-holes/contrived/koch-snowflake-nested/ for polygons with holes. kn00000096 For the rectilinear snowflake, see see /db/wip/polygons/contrived/koch-snowflake_quad/ for grid-aligned and /db/wip/polygons/contrived/koch-snowflake_quad_perturbed/ for randomly perturbed. kq00000256
read more

SRPG - Super Random Polygon Generator

srpg generates simply-connected and multiply-connected polygons by means of a regular grid (with quadratic cells). Source code is available on github. See the srpg* directories in /db/wip/polygons/random/ for polygons and /db/wip/polygons-with-holes/random/ for polygons with holes. There are several variants: srpg_iso: orthogonal polygons. srpg_iso_aligned: orthogonal polygons on an integer grid. srpg_octa: octagonal polygons. srpg_perturbed: random polygons. srpg_perturbed_smo: random polygons with smoothed corners. srpg_perturbed_smr: random polygons with even smoother corners. srpg0000051 srpg_iso0000039 srpg_octa0000035 srpg_smo0000123 srpg_mc0000166 srpg_iso_aligned_mc0000150
read more

More

Lebesgue Curves

Sierpinski Curves

Hilbert Curves

FPG - Triangulation Perturbation

All Generators