delaunator vs earcut vs polylabel vs clipper-lib
Geometric Algorithms for Web Development Comparison
Search packages..
1 Year
delaunatorearcutpolylabelclipper-libSimilar Packages:
What's Geometric Algorithms for Web Development?

These npm packages provide essential algorithms for handling geometric operations in web development. They are particularly useful for tasks involving polygons, triangulation, and spatial analysis. Each library specializes in different aspects of geometry, making them suitable for various applications such as rendering graphics, computational geometry, and geographic information systems (GIS). Understanding their unique functionalities helps developers choose the right tool for their specific needs.

Package Weekly Downloads Trend
Github Stars Ranking
Stat Detail
Package
Downloads
Stars
Size
Issues
Publish
License
delaunator3,880,8192,40855.3 kB5a year agoISC
earcut3,171,2702,26257.4 kB223 months agoISC
polylabel209,1781,45515.8 kB158 months agoISC
clipper-lib19,092184215 kB7-BSL
Feature Comparison: delaunator vs earcut vs polylabel vs clipper-lib

Primary Functionality

  • delaunator:

    delaunator focuses on Delaunay triangulation, which is a method of connecting a set of points to form triangles without overlapping. This is essential for creating meshes and surfaces in computational geometry, making it ideal for applications that require efficient triangulation of scattered points.

  • earcut:

    earcut is designed for fast polygon triangulation, converting polygons into triangles for rendering in 2D graphics. It is optimized for performance, making it suitable for real-time applications where speed is crucial, such as game development or interactive visualizations.

  • polylabel:

    polylabel is used to find the best position for labeling polygons, ensuring that labels are placed optimally within the shape. This is particularly useful in mapping and visualization applications where clear and effective labeling is necessary.

  • clipper-lib:

    clipper-lib specializes in polygon clipping operations, allowing for complex geometric manipulations such as union, intersection, and difference of polygons. It supports both simple and complex polygons and provides functionalities for offsetting and simplifying shapes, making it a powerful tool for CAD and GIS applications.

Performance

  • delaunator:

    delaunator is highly efficient and fast, capable of processing large datasets quickly. It uses an incremental algorithm that ensures performance remains optimal even with a significant number of points, making it ideal for real-time applications.

  • earcut:

    earcut is one of the fastest triangulation algorithms available, designed to handle simple polygons with high efficiency. Its performance makes it a go-to choice for applications requiring quick rendering of 2D shapes.

  • polylabel:

    polylabel is efficient in calculating the optimal label position, but its performance can vary based on the complexity of the polygon. It is generally fast for most use cases, especially when dealing with simple shapes.

  • clipper-lib:

    clipper-lib is optimized for performance in handling complex polygon operations, but it may have a steeper learning curve due to its extensive feature set. It is best suited for applications where precision and advanced geometric operations are required.

Use Cases

  • delaunator:

    delaunator is ideal for applications in computer graphics, terrain modeling, and any scenario where triangulation of scattered points is necessary, such as mesh generation for 3D models.

  • earcut:

    earcut is widely used in game development and web graphics where quick rendering of 2D polygons is required. It is particularly effective for applications that need to visualize complex shapes in real-time.

  • polylabel:

    polylabel is particularly useful in mapping applications, where it helps in placing labels on geographic features or in data visualization tools where clear labeling is essential.

  • clipper-lib:

    clipper-lib is commonly used in applications that require detailed geometric calculations, such as CAD software, GIS systems, and any application needing precise polygon manipulations.

Complexity

  • delaunator:

    delaunator has a straightforward API that is easy to use for developers familiar with triangulation concepts. Its focus on Delaunay triangulation makes it less complex than some alternatives, while still providing powerful functionality.

  • earcut:

    earcut is designed for simplicity and speed, with a minimalistic API that allows developers to quickly implement triangulation without needing extensive knowledge of computational geometry.

  • polylabel:

    polylabel offers a simple interface for determining label positions, making it easy to integrate into applications without requiring advanced geometric knowledge.

  • clipper-lib:

    clipper-lib has a more complex API due to its wide range of features, which may require a deeper understanding of geometric concepts. This complexity allows for greater flexibility and precision in geometric operations.

Community and Support

  • delaunator:

    delaunator has a growing community and is well-documented, providing users with examples and guidance for implementing triangulation in various applications. Its focus on performance has garnered interest among developers.

  • earcut:

    earcut benefits from a vibrant community and is widely used in the graphics programming space, leading to a wealth of tutorials and resources available online. Its popularity ensures that developers can find help easily.

  • polylabel:

    polylabel has a smaller community compared to the others, but it is well-documented and easy to understand, making it accessible for developers looking to implement labeling solutions.

  • clipper-lib:

    clipper-lib has a strong community and extensive documentation, making it easier for developers to find support and examples for complex operations. Its long-standing presence in the field ensures a wealth of resources.

How to Choose: delaunator vs earcut vs polylabel vs clipper-lib
  • delaunator:

    Select delaunator for efficient Delaunay triangulation of a set of points. It is particularly useful in scenarios where you need to create a mesh or triangulated surface from scattered data points, such as in terrain modeling or mesh generation for 3D graphics.

  • earcut:

    Opt for earcut when you need a fast and simple solution for polygon triangulation. It is well-suited for rendering 2D polygons in graphics applications, especially when performance is critical and the polygons are simple and non-complex.

  • polylabel:

    Use polylabel if you require a method to find the optimal label position for polygons. This is particularly useful in mapping applications where you need to place labels or markers in a way that maximizes visibility and minimizes overlap.

  • clipper-lib:

    Choose clipper-lib if you need advanced polygon clipping operations such as union, intersection, difference, and offsetting. It is ideal for applications that require precise geometric manipulations and is widely used in CAD and GIS applications.

Similar Npm Packages to earcut

earcut is a fast and efficient ear clipping triangulation library for 2D polygons. It is widely used in graphics programming, game development, and geographic information systems (GIS) for converting complex polygon shapes into a series of triangles, which can be rendered more efficiently by graphics hardware. Earcut is particularly known for its speed and simplicity, making it a popular choice among developers looking for a lightweight solution for polygon triangulation.

While earcut is a solid option for triangulation, there are several alternatives in the ecosystem that provide similar functionalities. Here are a few noteworthy alternatives:

  • clipper-lib is a robust library for polygon clipping and offsetting. It provides advanced features for performing operations like union, intersection, and difference on polygons. Clipper-lib is particularly useful when you need to handle complex polygon shapes and perform operations beyond simple triangulation. If your project requires extensive polygon manipulation, including clipping and offsetting, clipper-lib is an excellent choice.
  • delaunator is a library specifically designed for Delaunay triangulation. Unlike earcut, which focuses on general polygon triangulation, delaunator is optimized for creating triangulations from a set of points in a 2D space. This library is particularly useful in scenarios where you need to generate a triangulated mesh from scattered points, such as in terrain modeling or spatial analysis. If your application requires Delaunay triangulation, delaunator is the go-to solution.
  • polylabel is a library that focuses on finding the optimal label position for polygons. While it does not perform triangulation directly, it is often used in conjunction with triangulation libraries to improve the placement of labels on complex shapes. If your project involves rendering polygons with labels and you need to ensure that the labels are placed optimally, polylabel can complement your triangulation solution effectively.

To see how earcut compares with clipper-lib, delaunator, and polylabel, check out the comparison: Comparing clipper-lib vs delaunator vs earcut vs polylabel.

Similar Npm Packages to clipper-lib

clipper-lib is a powerful JavaScript library designed for polygon clipping and boolean operations on polygons. It allows developers to perform complex geometric operations such as union, intersection, difference, and XOR on 2D polygons. This library is particularly useful in applications that require advanced geometric manipulations, such as CAD software, GIS applications, and game development. With its robust algorithms, clipper-lib can handle a wide range of polygon shapes and sizes efficiently.

While clipper-lib is a strong choice for polygon operations, there are alternatives that may better suit specific needs:

  • earcut is a fast and efficient library for triangulating polygons. It is particularly useful when you need to convert complex polygon shapes into triangles for rendering in WebGL or other graphics contexts. earcut is lightweight and focuses solely on the triangulation process, making it a great choice for applications that require quick and straightforward polygon triangulation without the overhead of additional features.
  • polygon-clipping is another library that specializes in polygon clipping operations. It provides a simple API for performing boolean operations on polygons, similar to clipper-lib. However, polygon-clipping is designed to be lightweight and easy to use, making it suitable for applications that require basic polygon clipping functionalities without the complexity of more advanced libraries.

To see how clipper-lib compares with earcut and polygon-clipping, check out the comparison: Comparing clipper-lib vs earcut vs polygon-clipping.

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.