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	boolean or number	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	boolean or number	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.