Dots Connector

A 2D Delaunay Triangulation TypeScript library. It works in modern browser and NodeJS environments.

• Interactive Demo
• This library is an implementation of A simple sweep-line Delaunay triangulation algorithm, 2013, Liu Yonghe, Feng Jinming and Shao Yuehong paper.

This library is still a work in progress. If you need a fast, feature-rich library, use delaunator instead.

Example

const originalPoints = [[0,0],[1,-2],[2,-0.5],...];

const { points, triangles } = triangulate(originalPoints);
console.log(delaunay.triangles);
// [0,1,2,...]

It returns an array of points because the algorithm requires adding small random noise to the original points, and also sort the points horizontally from left to right.

Install

Install with NPM (npm install dots-connector) then:

// import as an ES module
import triangulate from 'dots-connector'

// or require in Node / Browserify
const triangulate = require('dots-connector');

Or use a browser build directly:

<script src="https://unpkg.com/dots-connector/umd/dots-connector.min.js"></script> <!-- minified build -->
<script src="https://unpkg.com/dots-connector/umd/dots-connector.js"></script> <!-- dev build -->

Bench

Results of running delaunator bench script on Macbook Pro 16" 2019, Node v10.18.1

|| uniform 100k | gauss 100k | grid 100k | degen 100k | uniform 1million | gauss 1million | grid 1million | degen 1million :-- | --: | --: | --: | --: | --: | --: | --: | --: dots-connector | 384ms | 427ms | 1010ms | failed | 5553ms | 5540ms | 11558ms | failed delaunator | 73ms | 61ms | 86ms | 31ms | 1046ms | 1118ms | 945ms | 428ms