delaunator vs d3-delaunay vs polylabel vs delaunay-triangulate
Delaunay Triangulation and Voronoi Diagrams Comparison
Search packages..
1 Year
delaunatord3-delaunaypolylabeldelaunay-triangulate
What's Delaunay Triangulation and Voronoi Diagrams?

Delaunay triangulation and Voronoi diagrams are fundamental concepts in computational geometry with applications in graphics, geographic information systems (GIS), and data visualization. Delaunay triangulation is the process of connecting a set of points in a plane to form triangles such that no point is inside the circumcircle of any triangle. This property maximizes the minimum angle of the triangles, resulting in a triangulation that avoids skinny triangles. Voronoi diagrams, on the other hand, partition the plane into regions based on the distance to a given set of points, where each region corresponds to one point and consists of all locations closer to that point than to any other. These concepts are widely used in various fields, including computer graphics, spatial analysis, and machine learning. The npm packages d3-delaunay, delaunator, delaunay-triangulate, and polylabel provide efficient algorithms and data structures for computing Delaunay triangulations and Voronoi diagrams, each with its own unique features and optimizations.

Package Weekly Downloads Trend
Github Stars Ranking
Stat Detail
Package
Downloads
Stars
Size
Issues
Publish
License
delaunator4,552,5322,46755.3 kB4a year agoISC
d3-delaunay4,330,395642104 kB12 years agoISC
polylabel213,9971,47615.8 kB16a year agoISC
delaunay-triangulate28,965160-211 years agoMIT
Feature Comparison: delaunator vs d3-delaunay vs polylabel vs delaunay-triangulate

Algorithm Efficiency

  • delaunator:

    delaunator is known for its performance, particularly with large datasets. It implements an incremental algorithm that operates in O(n log n) time, making it one of the fastest libraries for Delaunay triangulation in JavaScript.

  • d3-delaunay:

    d3-delaunay leverages the Bowyer-Watson algorithm for Delaunay triangulation, which is efficient for most practical applications. However, its performance may vary depending on the input data and the specific operations being performed.

  • polylabel:

    polylabel focuses on optimizing label placement within polygons rather than triangulation. Its algorithm efficiently finds the best point for labeling, but it is not designed for triangulating point sets.

  • delaunay-triangulate:

    delaunay-triangulate provides a simple and efficient triangulation algorithm, but it may not be as optimized as delaunator for handling very large datasets. It is suitable for small to medium-sized point sets.

Integration with Other Libraries

  • delaunator:

    delaunator is a standalone library that can be easily integrated with other JavaScript projects. Its simple API allows for quick adoption in various applications, but it does not have built-in integrations with other libraries.

  • d3-delaunay:

    d3-delaunay is designed to work seamlessly with other D3.js modules, making it an excellent choice for projects that involve data visualization and require tight integration with D3's ecosystem.

  • polylabel:

    polylabel can be used in conjunction with other graphics and mapping libraries to enhance label placement. It works well with any library that provides polygon data, making it versatile for integration.

  • delaunay-triangulate:

    delaunay-triangulate is a lightweight library that can be used alongside other JavaScript tools and frameworks. Its simplicity makes it easy to incorporate into projects without any complex dependencies.

Use Case Scenarios

  • delaunator:

    delaunator is suitable for applications that require fast and accurate Delaunay triangulation, such as geographic information systems (GIS), computer graphics, and spatial analysis tools. Its performance makes it a great choice for processing large datasets.

  • d3-delaunay:

    d3-delaunay is ideal for data visualization projects that require dynamic triangulation and Voronoi diagram generation. It is particularly useful for creating interactive visualizations where geometric relationships between points are important.

  • polylabel:

    polylabel is specialized for labeling applications, such as placing labels on maps, diagrams, or any graphical representation where optimal label placement is needed to avoid overlap and improve readability.

  • delaunay-triangulate:

    delaunay-triangulate is best for simple triangulation tasks in educational projects, prototypes, or applications where minimal setup and functionality are needed. It is not intended for complex or large-scale triangulation tasks.

Code Example

  • delaunator:

    Delaunay triangulation with delaunator

    import Delaunator from 'delaunator';

const points = [
  0, 0,
  1, 1,
  2, 0,
  1, -1,
];

const delaunator = new Delaunator(points);
const triangles = delaunator.triangles;

console.log(triangles); // Output the indices of the triangles
  • d3-delaunay:

    Delaunay triangulation with d3-delaunay

    import { Delaunay } from 'd3-delaunay';

const points = [
  [0, 0],
  [1, 1],
  [2, 0],
  [1, -1],
];

const delaunay = Delaunay.from(points);
const triangles = delaunay.triangles;

console.log(triangles); // Output the indices of the triangles
  • polylabel:

    Optimal label placement with polylabel

    import polylabel from 'polylabel';

const polygon = [
  [0, 0],
  [2, 0],
  [2, 2],
  [0, 2],
];

const labelPoint = polylabel(polygon);

console.log(labelPoint); // Output the optimal label position
  • delaunay-triangulate:

    Delaunay triangulation with delaunay-triangulate

    import { triangulate } from 'delaunay-triangulate';

const points = [
  [0, 0],
  [1, 1],
  [2, 0],
  [1, -1],
];

const triangles = triangulate(points);

console.log(triangles); // Output the triangles
How to Choose: delaunator vs d3-delaunay vs polylabel vs delaunay-triangulate
  • delaunator:

    Select delaunator if you require a fast and memory-efficient Delaunay triangulation algorithm implemented in pure JavaScript. It is ideal for applications where performance is critical, and it works well with large datasets while maintaining a simple API.

  • d3-delaunay:

    Choose d3-delaunay if you are already using the D3.js ecosystem and need a well-integrated solution for Delaunay triangulation and Voronoi diagram generation. It provides a comprehensive set of tools for working with geometric structures and is particularly useful for data visualization projects.

  • polylabel:

    Opt for polylabel if your primary goal is to find the optimal label position within a polygon. This package is specialized for computing the point within a polygon that maximizes the minimum distance to the polygon's edges, making it useful for labeling and annotation tasks in graphics and mapping applications.

  • delaunay-triangulate:

    Use delaunay-triangulate if you need a lightweight and straightforward library for Delaunay triangulation. It is easy to use and suitable for projects that require basic triangulation functionality without the overhead of additional features.

Similar Npm Packages to delaunator

delaunator is a JavaScript library that efficiently computes the Delaunay triangulation of a set of points in the plane. It is designed for performance and can handle large datasets, making it a popular choice for applications that require geometric computations, such as rendering graphics, spatial analysis, and more. Delaunay triangulation is a fundamental operation in computational geometry, and delaunator provides a straightforward API to achieve this.

While delaunator is a powerful tool for triangulation, there are several alternatives in the ecosystem that also provide similar functionality. Here are a few noteworthy options:

  • d3-delaunay is part of the D3.js library, which is widely used for data visualization. It provides a Delaunay triangulation implementation that integrates seamlessly with D3's data-driven approach. If you are already using D3 for your visualizations, d3-delaunay is an excellent choice, as it allows you to leverage D3's powerful features while performing triangulation.
  • delaunay-triangulate is another library focused on Delaunay triangulation. It offers a simple API for computing the triangulation of a set of points and is designed to be lightweight and easy to use. If you are looking for a straightforward solution without the additional features of larger libraries, delaunay-triangulate may be the right fit for your project.
  • polylabel is a library that computes the best-fitting point (the "label") for a polygon, which can be useful in various applications, including labeling and positioning elements in a visual representation. While it is not strictly a triangulation library, it can complement triangulation tasks by helping to determine optimal placement for labels within the triangulated areas.

To see how delaunator compares with d3-delaunay, delaunay-triangulate, and polylabel, check out the comparison: Comparing d3-delaunay vs delaunator vs delaunay-triangulate vs polylabel.

README for delaunator

Delaunator Build Status

An incredibly fast and robust JavaScript library for Delaunay triangulation of 2D points.

Delaunay triangulation example

Projects based on Delaunator

  • d3-delaunay for Voronoi diagrams, search, traversal and rendering (a part of D3).
  • d3-geo-voronoi for Delaunay triangulations and Voronoi diagrams on a sphere (e.g. for geographic locations).

Example

const coords = [168,180, 168,178, 168,179, 168,181, 168,183, ...];

const delaunay = new Delaunator(coords);
console.log(delaunay.triangles);
// [623, 636, 619,  636, 444, 619, ...]

Install

Install with NPM (npm install delaunator) or Yarn (yarn add delaunator), then import as an ES module:

import Delaunator from 'delaunator';

To use as a module in a browser:

<script type="module">
    import Delaunator from 'https://cdn.skypack.dev/delaunator@5.0.0';
</script>

Or use a browser UMD build that exposes a Delaunator global variable:

<script src="https://unpkg.com/delaunator@5.0.0/delaunator.min.js"></script>

API Reference

new Delaunator(coords)

Constructs a delaunay triangulation object given an array of point coordinates of the form: [x0, y0, x1, y1, ...] (use a typed array for best performance).

Delaunator.from(points[, getX, getY])

Constructs a delaunay triangulation object given an array of points ([x, y] by default). getX and getY are optional functions of the form (point) => value for custom point formats. Duplicate points are skipped.

delaunay.triangles

A Uint32Array array of triangle vertex indices (each group of three numbers forms a triangle). All triangles are directed counterclockwise.

To get the coordinates of all triangles, use:

for (let i = 0; i < triangles.length; i += 3) {
    coordinates.push([
        points[triangles[i]],
        points[triangles[i + 1]],
        points[triangles[i + 2]]
    ]);
}

delaunay.halfedges

A Int32Array array of triangle half-edge indices that allows you to traverse the triangulation. i-th half-edge in the array corresponds to vertex triangles[i] the half-edge is coming from. halfedges[i] is the index of a twin half-edge in an adjacent triangle (or -1 for outer half-edges on the convex hull).

The flat array-based data structures might be counterintuitive, but they're one of the key reasons this library is fast.

delaunay.hull

A Uint32Array array of indices that reference points on the convex hull of the input data, counter-clockwise.

delaunay.coords

An array of input coordinates in the form [x0, y0, x1, y1, ....], of the type provided in the constructor (or Float64Array if you used Delaunator.from).

delaunay.update()

Updates the triangulation if you modified delaunay.coords values in place, avoiding expensive memory allocations. Useful for iterative relaxation algorithms such as Lloyd's.

Performance

Benchmark results against other Delaunay JS libraries (npm run bench on Macbook Pro Retina 15" 2017, Node v10.10.0):

  | uniform 100k | gauss 100k | grid 100k | degen 100k | uniform 1 million | gauss 1 million | grid 1 million | degen 1 million :-- | --: | --: | --: | --: | --: | --: | --: | --: delaunator | 82ms | 61ms | 66ms | 25ms | 1.07s | 950ms | 830ms | 278ms faster‑delaunay | 473ms | 411ms | 272ms | 68ms | 4.27s | 4.62s | 4.3s | 810ms incremental‑delaunay | 547ms | 505ms | 172ms | 528ms | 5.9s | 6.08s | 2.11s | 6.09s d3‑voronoi | 972ms | 909ms | 358ms | 720ms | 15.04s | 13.86s | 5.55s | 11.13s delaunay‑fast | 3.8s | 4s | 12.57s | timeout | 132s | 138s | 399s | timeout delaunay | 4.85s | 5.73s | 15.05s | timeout | 156s | 178s | 326s | timeout delaunay‑triangulate | 2.24s | 2.04s | OOM | 1.51s | OOM | OOM | OOM | OOM cdt2d | 45s | 51s | 118s | 17s | timeout | timeout | timeout | timeout

Papers

The algorithm is based on ideas from the following papers:

Robustness

Delaunator should produce valid output even on highly degenerate input. It does so by depending on robust-predicates, a modern port of Jonathan Shewchuk's robust geometric predicates, an industry standard in computational geometry.

Ports to other languages

npm-compare.com is an independent website designed to help developers choose the most suitable npm packages. We are not affiliated with npm, Inc or npmjs.com, the official website for the npm registry. Please note that npm is a registered trademark of npm, Inc. For more details, please refer to our Terms & Privacy.