---

Description

Given a set of vertices, using the Randomized Incremental Algorithm we can Delaunay-triangulate it with complexity = O(n log n).

---

Programming Language & Build System

• C++, (v17 or newer)
• CMAKE/CCMAKE, (v3.1 or newer)

---

Libraries

• 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

---

Structure of repository

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

---

Installation & Compilation

• create a build directory inside the root of this project
• cd into the build directory
• cmake ..

---

Input and Output files

Input files:

• .node which can be visualized using ShowMe.

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.

---

Usage

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.

---

Execution Example

delomatic --random 1000000 --output output.ele

---

Performance Evaluation

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.

---

Contact Information

Author: Spiros Tsalikis ([email protected])
Department of Computer Science, Old Dominion University, 5115 Hampton Blvd, Norfolk, VA 23529, USA

---

Copyright (C) Spiros Tsalikis