d3-delaunay vs delaunator vs delaunay-triangulate vs polylabel
Delaunay Triangulation and Voronoi Diagrams
Search packages..
d3-delaunaydelaunatordelaunay-triangulatepolylabel

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.

Npm Package Weekly Downloads Trend

3 Years

Github Stars Ranking

Stat Detail

Package
Downloads
Stars
Size
Issues
Publish
License
d3-delaunay0650104 kB13 years agoISC
delaunator02,57155.3 kB62 years agoISC
delaunay-triangulate0163-212 years agoMIT
polylabel01,52815.8 kB182 years agoISC

Feature Comparison: d3-delaunay vs delaunator vs delaunay-triangulate vs polylabel

Algorithm Efficiency

  • 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.

  • 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.

  • 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.

  • 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.

Integration 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.

  • 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.

  • 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.

  • 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.

Use Case Scenarios

  • 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.

  • 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.

  • 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.

  • 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.

Code Example

  • 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
  • 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
  • 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
  • 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

How to Choose: d3-delaunay vs delaunator vs delaunay-triangulate vs polylabel

  • 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.

  • 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.

  • 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.

  • 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.

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 d3-delaunay

d3-delaunay

Georgy “The Voronator” Voronoy

This is a fast library for computing the Voronoi diagram of a set of two-dimensional points. It is based on Delaunator, a fast library for computing the Delaunay triangulation using sweep algorithms. The Voronoi diagram is constructed by connecting the circumcenters of adjacent triangles in the Delaunay triangulation.

For an interactive explanation of how this library works, see The Delaunay’s Dual.

Installing

If you use npm, npm install d3-delaunay. You can also download the latest release on GitHub. For vanilla HTML in modern browsers, import d3-delaunay from Skypack:

<script type="module">

import {Delaunay} from "https://cdn.skypack.dev/d3-delaunay@6";

const points = [[0, 0], [0, 1], [1, 0], [1, 1]];
const delaunay = Delaunay.from(points);
const voronoi = delaunay.voronoi([0, 0, 960, 500]);

</script>

For legacy environments, you can load d3-delaunay’s UMD bundle from an npm-based CDN such as jsDelivr; a d3 global is exported:

<script src="https://cdn.jsdelivr.net/npm/d3-delaunay@6"></script>
<script>

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

</script>

API Reference

Delaunay

# new Delaunay(points) <>

Returns the Delaunay triangulation for the given flat array [x0, y0, x1, y1, …] of points.

const delaunay = new Delaunay(Float64Array.of(0, 0, 0, 1, 1, 0, 1, 1));

# Delaunay.from(points[, fx[, fy[, that]]]) <>

Returns the Delaunay triangulation for the given array or iterable of points. If fx and fy are not specified, then points is assumed to be an array of two-element arrays of numbers: [[x0, y0], [x1, y1], …]. Otherwise, fx and fy are functions that are invoked for each element in the points array in order, and must return the respective x- and y-coordinate for each point. If that is specified, the functions fx and fy are invoked with that as this. (See Array.from for reference.)

const delaunay = Delaunay.from([[0, 0], [0, 1], [1, 0], [1, 1]]);

# delaunay.points

The coordinates of the points as an array [x0, y0, x1, y1, …]. Typically, this is a Float64Array, however you can use any array-like type in the constructor.

# delaunay.halfedges

The halfedge indexes as an Int32Array [j0, j1, …]. For each index 0 ≤ i < halfedges.length, there is a halfedge from triangle vertex j = halfedges[i] to triangle vertex i. Equivalently, this means that triangle ⌊i / 3⌋ is adjacent to triangle ⌊j / 3⌋. If j is negative, then triangle ⌊i / 3⌋ is an exterior triangle on the convex hull. For example, to render the internal edges of the Delaunay triangulation:

const {points, halfedges, triangles} = delaunay;
for (let i = 0, n = halfedges.length; i < n; ++i) {
  const j = halfedges[i];
  if (j < i) continue;
  const ti = triangles[i];
  const tj = triangles[j];
  context.moveTo(points[ti * 2], points[ti * 2 + 1]);
  context.lineTo(points[tj * 2], points[tj * 2 + 1]);
}

See also delaunay.render.

# delaunay.hull

An Int32Array of point indexes that form the convex hull in counterclockwise order. If the points are collinear, returns them ordered.

See also delaunay.renderHull.

# delaunay.triangles

The triangle vertex indexes as an Uint32Array [i0, j0, k0, i1, j1, k1, …]. Each contiguous triplet of indexes i, j, k forms a counterclockwise triangle. The coordinates of the triangle’s points can be found by going through delaunay.points. For example, to render triangle i:

const {points, triangles} = delaunay;
const t0 = triangles[i * 3 + 0];
const t1 = triangles[i * 3 + 1];
const t2 = triangles[i * 3 + 2];
context.moveTo(points[t0 * 2], points[t0 * 2 + 1]);
context.lineTo(points[t1 * 2], points[t1 * 2 + 1]);
context.lineTo(points[t2 * 2], points[t2 * 2 + 1]);
context.closePath();

See also delaunay.renderTriangle.

# delaunay.inedges

The incoming halfedge indexes as a Int32Array [e0, e1, e2, …]. For each point i, inedges[i] is the halfedge index e of an incoming halfedge. For coincident points, the halfedge index is -1; for points on the convex hull, the incoming halfedge is on the convex hull; for other points, the choice of incoming halfedge is arbitrary. The inedges table can be used to traverse the Delaunay triangulation; see also delaunay.neighbors.

# delaunay.find(x, y[, i]) <>

Returns the index of the input point that is closest to the specified point ⟨x, y⟩. The search is started at the specified point i. If i is not specified, it defaults to zero.

# delaunay.neighbors(i) <>

Returns an iterable over the indexes of the neighboring points to the specified point i. The iterable is empty if i is a coincident point.

# delaunay.render([context]) <>

delaunay.render

Renders the edges of the Delaunay triangulation to the specified context. The specified context must implement the context.moveTo and context.lineTo methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

# delaunay.renderHull([context]) <>

delaunay.renderHull

Renders the convex hull of the Delaunay triangulation to the specified context. The specified context must implement the context.moveTo and context.lineTo methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

# delaunay.renderTriangle(i[, context]) <>

delaunay.renderTriangle

Renders triangle i of the Delaunay triangulation to the specified context. The specified context must implement the context.moveTo, context.lineTo and context.closePath methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

# delaunay.renderPoints([context][, radius]) <>

Renders the input points of the Delaunay triangulation to the specified context as circles with the specified radius. If radius is not specified, it defaults to 2. The specified context must implement the context.moveTo and context.arc methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

# delaunay.hullPolygon() <>

Returns the closed polygon [[x0, y0], [x1, y1], …, [x0, y0]] representing the convex hull.

# delaunay.trianglePolygons() <>

Returns an iterable over the polygons for each triangle, in order.

# delaunay.trianglePolygon(i) <>

Returns the closed polygon [[x0, y0], [x1, y1], [x2, y2], [x0, y0]] representing the triangle i.

# delaunay.update() <>

Updates the triangulation after the points have been modified in-place.

# delaunay.voronoi([bounds]) <>

Returns the Voronoi diagram for the associated points. When rendering, the diagram will be clipped to the specified bounds = [xmin, ymin, xmax, ymax]. If bounds is not specified, it defaults to [0, 0, 960, 500]. See To Infinity and Back Again for an interactive explanation of Voronoi cell clipping.

The Voronoi diagram is returned even in degenerate cases where no triangulation exists — namely 0, 1 or 2 points, and collinear points.

Voronoi

# voronoi.delaunay

The Voronoi diagram’s associated Delaunay triangulation.

# voronoi.circumcenters

The circumcenters of the Delaunay triangles as a Float64Array [cx0, cy0, cx1, cy1, …]. Each contiguous pair of coordinates cx, cy is the circumcenter for the corresponding triangle. These circumcenters form the coordinates of the Voronoi cell polygons.

# voronoi.vectors

A Float64Array [vx0, vy0, wx0, wy0, …] where each non-zero quadruple describes an open (infinite) cell on the outer hull, giving the directions of two open half-lines.

# voronoi.xmin
# voronoi.ymin
# voronoi.xmax
# voronoi.ymax

The bounds of the viewport [xmin, ymin, xmax, ymax] for rendering the Voronoi diagram. These values only affect the rendering methods (voronoi.render, voronoi.renderBounds, cell.render).

# voronoi.contains(i, x, y) <>

Returns true if the cell with the specified index i contains the specified point ⟨x, y⟩. (This method is not affected by the associated Voronoi diagram’s viewport bounds.)

# voronoi.neighbors(i) <>

Returns an iterable over the indexes of the cells that share a common edge with the specified cell i. Voronoi neighbors are always neighbors on the Delaunay graph, but the converse is false when the common edge has been clipped out by the Voronoi diagram’s viewport.

# voronoi.render([context]) <>

voronoi.render

Renders the mesh of Voronoi cells to the specified context. The specified context must implement the context.moveTo and context.lineTo methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

# voronoi.renderBounds([context]) <>

voronoi.renderBounds

Renders the viewport extent to the specified context. The specified context must implement the context.rect method from the CanvasPathMethods API. Equivalent to context.rect(voronoi.xmin, voronoi.ymin, voronoi.xmax - voronoi.xmin, voronoi.ymax - voronoi.ymin). If a context is not specified, an SVG path string is returned instead.

# voronoi.renderCell(i[, context]) <>

cell.render

Renders the cell with the specified index i to the specified context. The specified context must implement the context.moveTo , context.lineTo and context.closePath methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

# voronoi.cellPolygons() <>

Returns an iterable over the non-empty polygons for each cell, with the cell index as property.

# voronoi.cellPolygon(i) <>

Returns the convex, closed polygon [[x0, y0], [x1, y1], …, [x0, y0]] representing the cell for the specified point i.

# voronoi.update() <>

Updates the Voronoi diagram and underlying triangulation after the points have been modified in-place — useful for Lloyd’s relaxation.

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