sibvrv/tympanum

A Typescript library for multidimensional convex hulling and Delaunay triangulations.

Tympanum

A Typescript library for generating multidimensional convex hulls and delaunay triangulations.

Documentation

• Reference documentation
• The original QuickHull algorithm

Examples:

• 2D Quickhull
• 3D Quickhull
• 2D Delaunay Triangulation
• 3D Delaunay Tetrahedralisation
• Delaunay facet search using visibility walking
• Point reconstruction with barycentric coordinates

Basic Types

Tympanum has the following building blocks to form shapes:

Any N-dimensional shape such as a simplex is a collection of Facets.

• Facet: This is a polygonal face of dimension N-1: a line, a triangle, or a tetrahedron in 2D, 3D or 4D respectively. Each facet is bounded by a set of ridges.
• Ridge: This is an edge of dimension N-2: a point (vertex), a line (edge), or a triangle in 2D, 3D or 4D respectively. A ridge has N-1 vertices (ie: 1 vertex, 2 line end points, 3 triangle corners).
• Vertex: These are represented as an index into a list of points (fe: the list of points used to generate a convex hull). This is so that we can easily map points to other data sets from which the points were extracted, or they can be used to construct 3D meshes for use in WebGL.

Convex Hull

To generate a convex hull using the quickHull algorithm:

import { quickHull } from "@derschmale/tympanum";

const points = [];

for (let i = 0; i < 5000; ++i) {  
    points[i] = [Math.random(), Math.random(), Math.random()];
}

const hull = quickHull(points);

hull will contain an array of Facet.

Delaunay Triangulation

To generate the delaunay triangulation:

import { delaunay } from "@derschmale/tympanum";

const points = [];

for (let i = 0; i < 500; ++i) {  
    points[i] = [Math.random(), Math.random(), Math.random()];
}

const triangulation = delaunay(points);

triangulation will contain an array of Facet, but of a higher dimension than the convex hull would.

Delaunay triangulations allow searching for facets containing a point efficiently using the vibility walk algorithm:

import { visibilityWalk } from "@derschmale/tympanum";

const pos = [ 0.5, 0.2, 0.7 ];
const facet = visibilityWalk(pos, triangulation, points);

When a facet has been found, we can calculate the point's barycentric coordinates. The barycentric coordinates can be used to interpolate values associated to each respective point.

import { barycentricCoords } from "@derschmale/tympanum";

// for example: every point has an RGB color assigned to it:
let colors = [];

// any color at index N is associated with the point at points[N]
for (let i = 0; i < 5000; ++i) {  
    colors[i] = { 
      r: Math.random() * 0xff, 
      g: Math.random() * 0xff, 
      b: Math.random() * 0xff
    };
}

if (facet) {
  const bary = barycentricCoords(pos, facet, points);
  const color = { r: 0, g: 0, b: 0 };
  
  for (let i = 0; i < bary.length; ++i) {
    // get the index of the point
    let index = facet.verts[i];
  
    // get the color at that index
    let c = colors[index];
    
    // add the weighted colors together
    color.r += bary[i] * c.r; 
    color.g += bary[i] * c.g; 
    color.b += bary[i] * c.b; 
  }
}