Given a set of vertices, using the Randomized Incremental Algorithm we can Delaunay-triangulate it with complexity = O(n log n).
- C++, (v17 or newer)
- CMAKE/CCMAKE, (v3.1 or newer)
- Predicates, (v1.0.0) : Routines for Arbitrary Precision Floating-vertex Arithmetic and Fast Robust Geometric Predicates
- CLI11, (V1.9.0) : Command Line Parser for C++11 and above
-
include/src:
- This directory contains the header and sources files of the DelaunayTriangulation program.
-
inputFiles:
- This directory contains example input files.
-
.gitignore
- This file includes what git should ignore.
-
CmakeLists.txt
- This file defines the building properties of this Repository.
-
LICENCE
- The file which includes the GNU 3 Licence.
-
README.md
- This file.
- create a build directory inside the root of this project
- cd into the build directory
cmake ..
Input files:
Output files
- .node for the vertices of the triangulation, which can be visualized using ShowMe.
- .ele for the triangles of the triangulation, which can be visualized using ShowMe.
Del-O-Matic
Usage: ./delomatic [OPTIONS]
Options:
-h,--help Print this help message and exit
-i,--input TEXT:FILE Excludes: --random
Input Vertices file to triangulate.
-r,--random UINT:POSITIVE Excludes: --input
Generates and uniformly random set of N 2D Vertices.
-p,--robust-predicates BOOLEAN
Uses Robust Predicates. '0' doesn't use Robust Predicates, '1' uses Robust Predicates.
(Default: 1)
-d,--validate-delaunay Validates the Delaunay Property of the triangulation.
-o,--output TEXT REQUIRED Output file that includes triangulation.
delomatic --random 1000000 --output output.ele
Performance evaluation was performed with an AMD Ryzen 5 3600 3.6GHz using uniformly random distributed vertices and Robust Predicates.
| vertices | Triangle's incremental-algorithm | Del-O-Matic's incremental-algorithm |
|---|---|---|
| 2,500 | 0.002 seconds | 0.012004 seconds |
| 5,000 | 0.004 seconds | 0.024208 seconds |
| 10,000 | 0.018 seconds | 0.041508 seconds |
| 25,000 | 0.042 seconds | 0.105986 seconds |
| 50,000 | 0.095 seconds | 0.239179 seconds |
| 100,000 | 0.208 seconds | 0.512371 seconds |
| 250,000 | 1.009 seconds | 1.510440 seconds |
| 500,000 | 3.770 seconds | 3.361120 seconds |
| 1,000,000 | 11.825 seconds | 7.401540 seconds |
| 2,500,000 | 47.039 seconds | 21.639200 seconds |
| 5,000,000 | 124.060 seconds | 46.717200 seconds |
Results: Del-O-Matic's incremental-algorithm scales better than Triangle's incremental-algorithm.
Author: Spiros Tsalikis (stsaliki@odu.edu)
Department of Computer Science, Old Dominion University, 5115 Hampton Blvd, Norfolk, VA 23529, USA
Copyright (C) Spiros Tsalikis