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.

Features:

• 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.

Installation

To use the library, it must be created as a submodule in git inside the path of a project:

git submodule add https://github.com/SmartBuildingDesign/Delynoi.git lib/delynoi

This will create the delynoi folder inside lib. Then, inside CMakeLists.txt:

import_library(lib/delynoi/Delynoi)
target_link_libraries(MyProject Delynoi)

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)

by the name of your main C++ file (in this case, mytest.cpp)
4. Inside the build folder and in the command line type:

   cmake .. 

   to create the makefiles. And to compile the program type:

   make 

5. To run your example, go to the build/test/ folder and in the command line type:

   ./Test

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)};
      square.addSeedPoints(seeds);
      

   2. With the points coordinates listed on a text file, say seeds.txt (an example is found in the test folder), call:
      

      square.addSeedsFromFile("seeds.txt");

   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:
   

   mesh.printInFile("mesh.txt");

Acknowledgements

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

• Triangle - A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.
• Clipper - an open source freeware library for clipping and offsetting lines and polygons.

License

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.

Author

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