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);

| string | switch | type | description | | ------ | ------------- | --------------------------- | ------------ | | -p | pslg | boolean | Read input as a Planar Straight Line Graph. (default true) | | -q | quality | booleanornumber | Quality mesh generation by Delaunay refinement.Adds vertices to the mesh to ensure that all angles are between 20 and 140 degrees.A minimum angle can be set by passing a number. Guaranteed to terminate for 28.6 degrees or smaller. Often succeeds up to 34 degrees. | | -a | area | booleanornumber | Imposes a maximum triangle area.A maximum area can be set by passing a number.If true reads maximum area from the input (i.e. a .poly file) | | -D | ccdt | boolean | Conforming constrained Delaunay triangulation | | -r | refine | boolean | Refine a previously generated mesh. | | -c | convexHull | boolean | Create segments on the convex hull of the triangulation.Beware: if you are not careful, this switch can cause the introduction of an extremely thin angle between a PSLG segment and a convex hull segment, which can cause overrefinement (and possibly failure if Triangle runs out of precision). | | -j | jettison | boolean | Prevent duplicated input vertices, or vertices 'eaten' by holes, from appearing in the output. If any vertices are jettisoned, the vertex numbering in the output differs from that of the input. | | -e | edges | boolean | Output a list of edges of the triangulation. | | -n | neighbors | boolean | Output a list of triangles neighboring each triangle. | | -o2 | quadratic | boolean | Generate second-order subparametric elements with six nodes each. | | -A | regionAttr | boolean | Assign an additional floating-point attribute to each triangle that identifies what segment-bounded region each triangle belongs to. | | -B | bndMarkers | boolean | Output boundary markers. (default true)Attention: -B works the other way around, if present it suppresses boundary markers. | | -O | holes | boolean | Read holes from the input. (default true)Attention: -O works the other way around, if present it ignores holes. | | -S | steiner | number | Maximum number of Steiner points - vertices that are not in the input, but are added to meet the constraints on minimum angle and maximum area. (default unlimited) | | -Q | quiet | boolean | Suppress all explanation of what Triangle is doing, unless an error occurs. (default true) | | -v | auto | | When vorout is provided, output the Voronoi diagram associated with the triangulation. (set automatically) | | -z | auto | | Zero based indices, always true. (set automatically) |

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.

| parameter | format | description | | ----------------------------- | ----------------------------------------------- | ------------------------------ | | pointlist | 2 floats per point[x, y, x, y ...] | An array of point coordinates. | | pointattributelist | n floats per point | An array of point attributes. | | pointmarkerlist | 1 int per point | An array of point markers. | | trianglelist | 3 ints per triangle[a, b, c, a, b, c ...] | An array of triangle corners. | | triangleattributelist | n floats per triangle | An array of triangle attributes. | | trianglearealist | 1 floats per triangle | An array of triangle area constraints.Input only. | | neighborlist | 3 ints per triangle | An array of triangle neighbors.Output only. | | segmentlist | 2 ints per segment[p, q, p, q ...] | An array of segment endpoints. | | segmentmarkerlist | 1 int per segment | An array of segment markers. | | holelist | 2 floats per hole[x, y, x, y ...] | An array of holes.Input only, copied to output. | | regionlist | 4 floats per region[x, y, attr, area ...] | An array of regional attributes and area constraints.Input only, copied to output. | | edgelist | 2 ints per edge[p, q, p, q ...] | An array of edge endpoints.Output only. | | edgemarkerlist | 1 int per edge | An array of edge markers.Output only. | | normlist | 2 floats per vector | An array of normal vectors, used for infinite rays in Voronoi diagrams.Output only. | | numberofpoints | int (readonly) | Number of points. | | numberofpointattributes | int (readonly) | Number of point attributes. | | numberoftriangles | int (readonly) | Number of triangles. | | numberofcorners | int (readonly) | Number of triangle corners. | | numberoftriangleattributes | int (readonly) | Number of triangle attributes. | | numberofsegments | int (readonly) | Number of segments. | | numberofholes | int (readonly) | Number of holes. Input only, copied to output. | | numberofregions | int (readonly) | Number of regions. Input only, copied to output. | | numberofedges | int (readonly) | Number of edges. Output only. |

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.