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…Continue readingC++ Examples for Delaunay Triangulation – Getting Started (0)
Author: Bernhard Kornberger
Fade2D is a powerful C++ Delaunay triangulation library known for its speed and robustness. In this benchmark, we explore its performance in triangulating varying point cloud sizes. Performance and Settings Benchmark Code Benchmarking Single- and Multithreaded Delaunay Triangulation In this section, we take a closer look at benchmarking Fade2D’s performance, both in single-threaded and multithreaded…Continue reading2D Delaunay Triangulation Benchmark – Example1
In this article, we will achieve two main objectives: first, we’ll explore how to access the elements within a triangulation, and second, we’ll demonstrate how to draw them in Postscript- or PDF format. This visualization is crucial as it enables you to visualize your source code’s outcomes. Preparing a triangulation Let’s start by preparing and…Continue readingAccessing Triangulation Elements and Drawing PDF or Postscript – Example2
When you perform a triangulation using only the vertices of a polygon, there’s no guarantee that the resulting Delaunay triangulation will contain the original polygon’s edges. However, don’t worry; you can enforce edges in a triangulation. In the example below, we demonstrate the insertion of constraint edges into a 2D triangulation. Similarly, you can insert…Continue readingConstraint Edges – Example3
If you want to triangulate a polygon or define a polygonal area in a triangulation, you’re in the right place. A Zone2 represents a region within a triangulation, and it can be defined directly or as the result of combining other zones through Boolean operations. Here’s a list of possible Zone2 types categorized by their…Continue readingZones: Polygonal Areas in a Triangulation (4)
Polygon Clipping: Boolean Set Operations Fade provides polygon clipping and functions to combine shapes through the following Boolean operations: You can find the C++ source code for this demo in examples_2D/ex5_booleanOps.cpp in the download package. Note: The term “polygon clipping” in this context refers to the Boolean operations, such as calculating the intersection of two…Continue readingPolygon Clipping: Boolean Operations – Example 5
Implementing Boolean operations on Polygons with Holes can be challenging. Therefore, in the present example, examples_2D/ex6_booleanOps2.cpp, you’ll find C++ source code already prepared to handle arbitrary shapes, whether they are convex or non-convex, with or without holes. Feel free to use this code in your project. Additionally, it’s advisable to review the previous Example 5.…Continue readingPractical Boolean Operations on Polygons with Holes – Example 6
Delaunay meshing is not merely about creating a mesh on points; it’s about Quality Meshing. This involves crafting a Delaunay mesh with triangles that meet certain quality criteria, such as minimal interior angles or maximum edge lengths. These properties are typically achieved by adding points, effectively refining an existing triangulation. You can find the source…Continue readingAdvanced Delaunay Meshing – Example 7
A frequently asked question is how to export a triangulation as a list of points and indices for use in one’s own software. Users have two options: they can implement this themselves, or they can utilize the FadeExport data structure. Using FadeExport is memory-efficient as it can optionally release memory within Fade while building the…Continue readingExporting a Triangulation – Example 8
When coding geometry software, numerical errors and unexpected geometric settings occur frequently. Thus, automated software testing with random geometric data is essential. But, for instance, creating random polygons without self-intersection is not trivial. Therefore the module testDataGenerators is provided to create repeatable sequences of random geometric objects for software testing and debugging. These include random…Continue readingRandom Polygons, Surfaces and more – Example 9
Fade2D is fast, and most of the time, you will not need progress updates at all. However, for very large triangulations, you may still want to connect your own progress bar to Fade2D’s update mechanism. Creating Your Custom Progress Receiver Class To receive progress information, you must create a custom class in your software that…Continue readingProgress Bar Mechanism – Example 10
Manually saving and loading a triangulation is challenging. This is especially true when there are millions of elements, and speed is crucial. For this reason, there are functions in Fade2D to assist you in saving and loading a triangulation, its zones and constraint edges. The included file “examples_2D/ex11_save_and_load.cpp” provides simple demo source code for this…Continue readingSaving and Loading a Triangulation – Example 11
This is a fast C++ Voronoi diagram example. The Voronoi diagram (Wikipedia) divides the plane into convex regions around the input points such that each region is closest to one point. There is an incredible number of applications for the Voronoi diagram so many scientists and engineers are familiar with this basic concept. A C++…Continue readingVoronoi Diagram in C++, Example 12
2.5D Delaunay triangulations (TIN – Triangulated Irregular Networks) are like a 2D Delaunay triangulation, but with elevated points. This article first describes the simple triangulation of point clouds from LiDAR scans and surface metrology data. It then demonstrates their optional simplification using adaptive and grid-based clustering methods. Finally, it shows how to re-export the triangle-mesh…Continue reading2.5D Terrain Triangulation and Point Cloud Simplification
In this example, we will flip edges in an unnatural looking triangulation to better match its valleys and ridges. Further we will use Fade’s Weighted Laplacian smoothing technique to improve the quality of a noisy triangle mesh. And finally we address an annoying problem, namely large edges at the boundary of a triangulation and we…Continue readingValleys and Ridges, Smoothing, Mesh-Improvements
In the field of land surveying constraint edges are maybe better known as “breaklines”. Similarly to the 2D case you can insert them into the triangle mesh, forcing segment subdivision or not. In addition you can insert a segment with its original height or you can adjust its height to the triangulation. This results in…Continue readingBreaklines, ISO Contours and the Cookie Cutter
The Segment Checker computes intersections of 2D or 2.5D line segments. But in contrast to 3D two line segments are considered to intersect when their 2D projections in the xy-plane intersect. In other words, even if the involved segments are at different heights. The Segment Checker is fast and robust against degenerate and glancing intersections.…Continue readingSegment Checker for 2D and 2.5D Segment Intersections
Cut And Fill (Wikipedia) Earthwork volume computations for C++. The library module Cut-And-Fill takes two overlapping surfaces and computes the volume between. The result is a set of volumes where soil must be filled or where material must be digged off to turn one surface into the other one. Example Source Code – Basic Usage…Continue readingCut and Fill Volumes in C++
If you’re a software developer in land surveying, you understand the importance of processing large point clouds efficiently. You also know the critical role of triangle filtering to generate correct terrain representations. Automatically removing unwanted triangles while retaining the important ones is a crucial step in achieving this goal. In this article, we’ll explore a…Continue readingTriangle Filtering in Land Survey Software
Fade2D offers powerful triangulation functionalities, essential in fields like land surveying, mining, and road construction. This article provides an overview of the I/O operations engineers use in practice to bridge their software with the Fade2D library. We will discuss the individual I/O methods through a C++ example, that you can also find in the download…Continue readingI/O: Bridging your Software with Fade2D
Creating an offset polygon without self-intersections is a surprisingly complex task. Therefore, Fade2D provides functions to compute positive or negative offsets for shapes, ensuring that the resulting offset contours are free from self-intersections. In this article, we will explain the source code from Example 13, located in the examples_2D/ex13_polygonOffset.cpp file in the Fade2D package, which…Continue readingOffset Polygons in C++ (Example 13)
The focus here is on merging: Two point clouds with different properties may overlap and need to be combined. Alternatively, you might need to merge triangulated objects with point clouds, such as a road with a terrain point cloud. This article presents practical solutions for merging triangulations and point clouds in 2.5D. The C++ source…Continue readingMerging Triangulations and Point Clouds
Just like the previous article, this one focuses on the C++ example of merging. In this part, we describe the function demo3_mergeShapes(), which explains how to merge two triangulations. You pass two zones to the function: one is the higher-priority triangulation, while the other has just base priority. The higher-priority triangulation remains intact, and we…Continue readingMerging Two Triangulations
When working with polygons, we are often interested in their enclosed area. However, inconsistent edge orientations and self-intersections introduce ambiguity regarding this area. Therefore, Fade2D provides a Polygon Clipper to repair corrupt polygons or restrict them to a defined region. This tool supports polygons that may contain holes, it resolves self-intersections, and it orients polygon…Continue readingPolygon Clipper – Repairing Polygons, Example 14
