triangle-wasm v1.0.0

Triangle-wasm

Javascript wrapper around Triangle - A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.

Triangle generates exact Delaunay triangulations, constrained Delaunay triangulations, conforming Delaunay triangulations, Voronoi diagrams, and high-quality triangular meshes. The latter can be generated with no small or large angles, and are thus suitable for finite element analysis.

Triangle was created at the Carnegie Mellon University by Jonathan Shewchuk.

This is a Javascript wrapper around the original C library, compiled to WebAssembly using Emscripten. The API was preserved, consisting of a single method triangulate() and an input/output object triangulateio. Other methods were added to bridge WASM and Javascript.

Planar Straight Line Graph	Delaunay triangulation	Constrained Delaunay triangulation
input	output	output -p

Quality mesh (minimum angle)	Conforming constrained Delaunay triangulation	Quality mesh (maximum area)
output -pq	output -pqD	output -pqDa0.2

Install

npm install triangle-wasm

Example

const Triangle = require('triangle-wasm');

const data = { pointlist: [-1, -1, 1, -1, 1, 1, -1, 1] };

Triangle.init().then(() => {
  const input = Triangle.makeIO(data);
  const output = Triangle.makeIO();
  
  Triangle.triangulate({ pslg: false, quality: true }, input, output);
  
  // draw output
  // ...
  
  Triangle.freeIO(input, true);
  Triangle.freeIO(output);
});

Demo

• Demo: Minimal
• Demo: Switches
• Demo: Voronoi

API

init(path)

Initialises the WASM module.

• path (default /) path to triangle.out.wasm (See Distributing WASM)

Returns a Promise which resolves when the .wasm module is ready.

triangulate(switches, input, output, vorout = null)

Triangulates the data passed in as input and writes the result to ouput (and the optional Voronoi result to vorout).

• switches an object or a string of switches
• input an instance of TriangulateIO - the input data
• output an instance of TriangulateIO - initialised, but empty
• vorout an instance of TriangulateIO - initialised, but empty (optional)

Returns null

makeIO(data = null)

Creates an instance of TriangulateIO and allocates memory on the heap. data is only required when creating an input instance.

• data input data i.e. from a parsed .poly or .svg

Returns an instance of TriangulateIO

freeIO(io, all = false)

Releases the allocated memory for an input/output instance.

• io reference to the stored i/o object
• all release all copied pointers

Returns null

Switches

Switches can be either an object or a string.

// i.e. the following calls are identical
Triangle.triangulate({ quality: true, convexHull: true }, input, output);
Triangle.triangulate('pzQqc', input, output);

For a full list of switches, see Command line switches.

For more detailed descriptions of all the switches, see Triangle's instructions.

The following are not part of the switches object, but can still be passed in as a string:

• -u, -X, -Y, -V

The following switches have no effect in the Javascript version of Triangle:

• -g, -P, -N, -E, -I, -i, -F, -l, -s, -C

Other examples of switches objects and their correspondent strings:

// default
switches = null; // pzQ

// quality mesh and conforming Delaunay
switches = { quality: true, ccdt: true }; // pzqDQ

// minimum angle, maximum area and output to console
switches = { quality: 20.5, area: 42.8, quiet: false }; // pzq20.5a42.8

// no boundary markers, no holes
switches = { bndMarkers: false, holes: false }; // pzQBO

TriangulateIO

The TriangulateIO structure used to pass data into and out of the triangulate() procedure.

All the parameters are optional, except for pointlist. All the numberof parameters are set automatically.

Releasing Memory

** IMPORTANT ** remember to destroy instances of TriangulateIO after using them to avoid memory leaks.

While JavaScript is fairly forgiving in cleaning up after itself, static languages such as C are definitely not. Debugging memory leaks in WebAssembly using Emscripten

When we call makeIO() we allocate memory ( malloc ) and it needs to be released after with freeIO() ( free ). To make matters even less convenient, Triangle copies pointers from input to output, so we need to be careful not to double-free. The solution is to call 'destroy all' freeIO(io, true) on one of the instances, either input or output.

// allocate memory
const input = Triangle.makeIO(data);
const output = Triangle.makeIO();

Triangle.triangulate(null, input, output);

// use output
// ...

// release memory
Triangle.freeIO(input, true);
Triangle.freeIO(output);

Voronoi Diagrams

This implementation does not use exact arithmetic to compute the Voronoi vertices, and does not check whether neighboring vertices are identical.

The result is a valid Voronoi diagram only if Triangle's output is a true Delaunay triangulation with no holes. The Voronoi output is usually meaningless (and may contain crossing edges and other pathology) if the output is a constrained Delaunay triangulation (CDT) or a conforming constrained Delaunay triangulation (CCDT), or if it has holes or concavities.

Distributing WASM

The .wasm file is distributed with the package, but it might be necessary to manually copy it out of /node_modules/triangle-wasm/ so it can be served as a static file or bundled with a loader. This might change in the future once it becomes clear what is the best way to distribute wasm libraries.

This repository doesn't contain the original C code for Triangle, only the compiled .wasm. The source code can be found here.

See Also

• Triangle - A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator
• poly-parse - A parser for .poly and .node files used by Triangle.
• svg-to-poly - Extracts a PSLG from .svg paths and prepares it for Triangle.
• opentype.js - Read and write OpenType fonts using JavaScript.

License

MIT, see LICENSE for details.