Skip to content

2D Constrained Delaunay Triangulation in JavaScript

License

Notifications You must be signed in to change notification settings

savithru-j/cdt-js

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

41 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

CDT-JS is an interactive web app for generating constrained Delaunay triangulations of 2D points, written in JavaScript.

Check out the app here.

CDT

How to use

  1. Insert a set of 2D points to triangulate.
  • Random: A random distribution of points may be added by entering the required number of points and clicking the "Generate random vertices" button. The points can be sampled from a uniform or standard normal distribution.
  • Import from file: Points may also be imported from a file using the button under "Load vertices from file". The x and y coordinates of each point should be space- or comma-separated, and each point should exist on its own line.
  • Manual entry: Directly add or modify points using the text-box under "Vertex list", and click the "Reload input data" button.
  1. Specify the set of edges to constrain, if any.
  • Random: Click the "Generate random edge constraints" button to randomly generate the specified number of edge constraints.
  • Import from file: Edge constraints can also be imported from a file using the button under "Load constrained edges from file". Each edge should be specified by the indices to its two end-points in the vertex list. The vertex indices use 0-based indexing, and should be space- or comma-separated.
  • Manual entry: Directly add or modify edge constraints using the text-box under "Constrained edge list", and click the "Reload input data" button.
  1. Click the "Triangulate!" button to generate the constrained Delaunay triangulation.

  2. Explore!

  • Click on the visualization to see more information about the points and triangles.
  • Locate and visualize a particular point or triangle by its index.
  • The indices to the three vertices of each triangle are printed in the last text-box of the control panel.

Performance

Some benchmark results obtained on an Intel Core i7-4712HQ (2.3 GHz), running Google Chrome v70.0 (JavaScript V8).

N = 100 N = 1000 N = 10,000 N = 100,000
Random points - uniform distribution, no edge constraints 1ms 5ms 41ms 570ms
Random points - normal distribution, no edge constraints 1ms 5ms 52ms 837ms
Random points - uniform distribution, 0.01N edge constraints 2ms 5ms 65ms 1.6s
Random points - uniform distribution, 0.1N edge constraints 2ms 8ms 232ms 26.5s

References

The algorithms implemented here are based on the following papers: