An object-oriented C++ library for the generation of polygonal meshes
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Failed to load latest commit information.

Delynoi: an object-oriented C++ library for the generation of polygonal meshes

This repository contains the code for an open source C++ library for the generation of polygonal meshes on arbitrary domains, based on the constrained Voronoi diagram.


  • The meshes are generated on arbitrary domains, created from user defined points. Domains have no restrictions on convexity.
  • It allows the inclusion of completely contained or intersecting holes, which are processed if required.
  • The meshes are generated from seed points, which can be read either directly from a text file, included one by one, or created from a number of generation rules included in the library. New generation rules can be easily included.
  • Meshes can be stored in OFF-style text files, or used directly in another program.
  • To generate the meshes, the library first computes the conforming Delaunay triangulation using Triangle; the triangulation is considered as a mesh that is left available for use if needed. Then, it computes the constrained Voronoi diagram.


Catalina Alvarez - B.Sc., M.Sc., Universidad de Chile.

Usage instructions

Delynoi is currently for Unix systems only.
  1. Download the source code and unpack it.
  2. In the root directory of Veamy, create a build/ folder.
  3. Go to test/ folder located in the root directory of Delynoi and: (a) add the main C++ file (say, mytest.cpp) containing your test example problem, (b) modify the CMakeLists.txt by changing the file name example.cpp in
    set(SOURCE_FILES example.cpp)
  4. by the name of your main C++ file (in this case, mytest.cpp)
  5. Inside the build folder and in the command line type:
    cmake .. 
    to create the makefiles. And to compile the program type:
  6. To run your example, go to the build/test/ folder and in the command line type:

Usage example

To generate a polygonal mesh, one needs to:
  1. List, in counterclockwise order, the points that define the domain and create the domain as a Region instance:
    std::vector square_points = {Point(0,0), Point(10,0), Point(10,10), Point(0,10)};
    Region square(square_points);   
  2. Include the required seed points on the domain, for which there are three alternatives:
    1. Create the points as a list of Point instances, and call:
      std::vector seeds = {Point(5,5)};
    2. With the points coordinates listed on a text file, say seeds.txt (an example is found in the test folder), call:
    3. Decide on two generation rules (one for each axis) from the predifined list of functions (or create a new one inheriting following the instructions given in the manual), and create a PointGenerator instance. If required, include a noise function from the noise list provided. Then, call including the PointGenerator and the number of points on each axis:
      PointGenerator rules(functions::random_double(0,10), functions::random_double(0,10));
      int nX = 5, nY = 5;
      square.generateSeedPoints(rules, nX, nY); 
  3. Create a TriangleVoronoiGenerator instances with the points inside the domain, and the domain itself:
    std::vector seeds = square.getSeedPoints();
    TriangleVoronoiGenerator generator (seeds, square);
  4. To obtain the Voronoi diagram, call:
    Mesh<Polygon> voronoi = generator.getMesh();
  5. To use the Delaunay triangulation instead of the Voronoi diagram, a different class is used, TriangleDelaunayGenerator, which can return the constrained Delaunay triangulation or the conforming Delaunay triangulation:
    TriangleDelaunayGenerator generator (seeds, square);
    Mesh<Triangle> constrained_delaunay = generator.getConstrainedDelaunayTriangulation();
    Mesh<Triangle> conforming_delaunay  = generator.getConformingDelaunayTriangulation();
    It is also possible to define a number of constrained segments inside the domain, that will not be flipped when the Delaunay triangulation is computed:
    Mesh<Triangle> constrained_delaunay = generator.getConstrainedDelaunayTriangulation(restrictedSegments);
  6. To print the mesh to a text file use:


Delynoi depends on two external open source libraries, whose codes are included in the repository.


This project is licensed under the GPL License. This program is free software; it can be redistributed or modified under the terms of the GNU General Public License as published by the Free Software Foundation.