A simple implementation of the Bowyer-Watson algorithm to construct the Delaunay triangulation of a given set of points. It was put into an easy-to-use C++ header-only library currently based on the build2 build system.
| master |
|
||
| Current |
|
|
|
- Markus Pawellek (lyrahgames@mailbox.org)
- C++17
- build2
- Operating System: Linux | Windows | MacOS
- Compiler: GCC | Clang | MSVC | MinGW
- Build System: build2
The standard installation process will only install the header-only library. If you are interested in installing examples, benchmarks, or tests, you have to run these installation commands manually.
bpkg -d build2-packages cc \
config.install.root=/usr/local \
config.install.sudo=sudo
Get the latest package release and build it.
bpkg build https://github.com/lyrahgames/delaunay.git
Install the built package.
bpkg install lyrahgames-delaunay
For uninstalling, do the following.
bpkg uninstall lyrahgames-delaunay
If your package uses an explicit depends: lyrahgames-delaunay make sure to initialize this dependency as a system dependency when creating a new configuration.
bdep init -C @build cc config.cxx=g++ "config.cxx.coptions=-O3" -- "?sys:lyrahgames-delaunay/*"
For now, there is no official package release on cppget.org.
Therefore add this repository in your repositories.manifest file of your package.
:
role: prerequisite
location: https://github.com/lyrahgames/delaunay#master
Add the following entry to the manifest file of your package with an optional version dependency.
depends: lyrahgames-delaunay
Then import the library in your buildfile to be able to link against your own executable or library.
import libs = lyrahgames-delaunay%lib{lyrahgames-delaunay}
exe{myexe}: {hxx cxx}{**} $libs
#include <random>
#include <vector>
//
#include <lyrahgames/delaunay/bowyer_watson.hpp>
int main() {
using namespace std;
using namespace lyrahgames;
using delaunay::bowyer_watson::point;
// Initialize oracle for random numbers.
mt19937 rng{random_device{}()};
uniform_real_distribution<float> dist{0, 1};
const auto random = [&] { return dist(rng); };
// Generate random points.
vector<point> points(5);
for (auto& p : points) p = point{random(), random()};
// Construct Delaunay triangulation.
const auto elements = delaunay::bowyer_watson::triangulation(points);
}
| 3D Triangulation | Surface Triangles |
|---|---|
 |
 |
-
Lee and Schachter, Two Algorithms for Constructing a Delaunay Triangulation, 1980
-
Dwyer, A Faster Divide-and-Conquer Algorithm for Constructing Delaunay Triangulations, 1986
-
Shewchuk, Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator
-
CP-Algorithms, Delaunay Triangulation and Voronoi Diagram, 2014
-
Shewchuk, TRIANGLE: Mesh Generation and Delaunay Triangulation
-
Peterson, Computing Constrained Delaunay Triangulations: In the Plane