Skip to content

Delaunay Triangulation using Randomized Incremental Algorithm.

License

Notifications You must be signed in to change notification settings

spyridon97/Del-O-Matic

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

50 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Logo

Codacy Badge License: GPL v3 Latest release


Description

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

Example


Programming Language & Build System

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

Libraries


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:

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

About

Delaunay Triangulation using Randomized Incremental Algorithm.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published