Categories
2D Delaunay Triangulation Examples in C++

C++ Examples for Delaunay Triangulation – Getting Started (0)

Welcome to our guide to Delaunay triangulation with C++. In this article, we’ll introduce you to the Fade2D library and show you how to perform a basic Delaunay triangulation on four points. This article serves as both an overview of the library and a practical example to get you started.

Fade2D is a powerful library for Delaunay triangulation, and we’ve prepared a series of concise C++ examples to help you get started. The below example collections showcase the library’s practical applications for specific tasks:

All described example source codes are included in the download package.

Point Cloud Properties: 2D vs. 2.5D vs. 3D

Before we dive into the first example, let’s clarify the dimensions:

  • 2D: The Fade2D SDK is designed for 2D Delaunay triangulation in the xy-plane. It offers features like constraint edges, zones, and boolean operations on zones.
  • 2.5D: Similar to Fade2D, Fade2.5D performs Delaunay triangulation but for lifted points. It includes a z-coordinate and additional algorithms for land surveying tasks.
  • 3D: For 3D point clouds, there are two libraries available – Fade3D, which produces tetrahedral meshes, and WOF, which generates 3D triangle meshes

The distinction between 2.5D and 3D is that in 2.5D, each (x, y) coordinate pair corresponds to a single z-coordinate, commonly employed for terrain and height data. In contrast, 3D encompasses surfaces with multiple z-coordinates per (x, y) pair, even for straightforward objects like spheres.

2D Constrained Delaunay triangulation, C++ example
2D Delaunay with constraint edges
2.5D Delaunay Triangulation of a point cloud (TIN, Triangulated Irregular Network)
2.5D Delaunay Triangulation (TIN, Triangulated Irregular Network) of a terrain point cloud
Use WOF to create triangle meshes on 3D point clouds (or Fade3D for tetrahedra)

Example 0: HelloTriangulation

Get started quickly with this fundamental Delaunay triangulation example in C++. This code demonstrates the basics, equivalent to a “HelloWorld” program:

// An empty triangulation
Fade_2D dt;
// 4 points
Point2 p0(0.0,0.0);
Point2 p1(1.0,0.0);
Point2 p2(0.5,2.0);
Point2 p3(0.5,0.5);
// Insert the points
dt.insert(p0);
dt.insert(p1);
dt.insert(p2);
dt.insert(p3);
// Draw as postscript graphic
dt.show("example0.ps");
C++ Example of a 2D Delaunay triangulation
Example0: The code in ex0_hello_triangulation.cpp inserts 4 points and draws the resulting triangulation

This concise code initializes a Fade_2D object, defines four points, inserts them into the triangulation, and generates a postscript graphic of the resulting triangulation. It’s the perfect starting point for your Delaunay triangulation journey.

If you plan to use Fade2.5D, you can jump right into those examples. Nevertheless, you’re welcome to return to the 2D examples at any time to solidify the fundamental concepts that also apply to Fade2.5D.

Compiling under Windows

To compile on a Windows system, follow these steps:

  • Unzip the package and navigate to the examples_2D folder.
  • Next, open the Visual Studio solution file (*.sln) correspondig to your Visual Studio version (e.g., VS2022)
  • Compile the solution.
  • Once compiled, locate the executable in either the “x64” or “Win32” folder.
  • For the best experience, start the executable from a command line window.

Pro tip: To easily open a command line window at the same path in a Windows Explorer window, simply select the address bar and type “cmd

Compiling on MacOS and Linux

To compile on MacOS and Linux, follow these steps:

  • Ensure that you have the GMP library installed. For example, on Debian-based systems, you can install it using the following command:
    sudo apt-get install libgmp10
  • Navigate to the examples_2D directory.
  • Inside this directory, locate the Makefile and open it using a text editor. Uncomment only the line corresponding to your platform. For example, if you’re using Ubuntu 22.04, uncommend the line that looks like:
# Choose a matching distribution below:
# DISTRO :=../lib_centos6.4_${ARCHITECTURE}
# DISTRO :=../lib_ubuntu14.04_${ARCHITECTURE}
# DISTRO :=../lib_fedora24_${ARCHITECTURE}
DISTRO :=../lib_ubuntu22.04_${ARCHITECTURE}
# DISTRO :=../lib_APPLE
# DISTRO :=../lib_raspberry_armv6l
# DISTRO :=../lib_raspberry_armv7l
  • After making the appropriate selection, save the Makefile.
  • In the terminal, type the command ‘make‘ to compile
  • Finally, once the compilation is complete, start the executable from the same directory

The next example benchmarks the performance of Fade on your computer.

9 replies on “C++ Examples for Delaunay Triangulation – Getting Started (0)”

Hi. This looks like a great library and would be very useful for my research. But I don’t know the first thing about C++. I have a C#/Visual Basic application in which I would like to perform constrained Delaunay triangulations. Is there any way to import this into a C# or Visual Basic project?

Hi

The easiest solution is certainly creating a small C++ application with Fade that you call from your C# or VB application. I do not program C# but if you want to create an interface I will support you as good as I can. Just give me an email in this case.

Hi!

I was wondering if Fade_2D is thread-safe. i.e. can I call dt.refineAdvanced on sufficiently distant zones from multiple threads without locking dt? I’m aware that Fade2D already supports threading, I have a niche use case here that will benefit from controlling the threads myself.

Thanks in advance!

Leave a Reply

Your email address will not be published. Required fields are marked *