Search packages, repositories and app categories

Package detailsv1.2.0

dart_earcut

Performant triangulation algorithm based on https://github.com/mapbox/earcut

AndroidiOSWebmacOSWindowsLinux
30-day downloads
1.1M
Likes
10
Pub points
150

Install package

flutter pub add dart_earcut

Package Overview

Package selection guidance compiled from public package information, community data, and project usage.

dart_earcut is a high-performance triangulation library for Dart, implementing the Earcut algorithm originally developed by Mapbox. It efficiently converts polygonal shapes into triangles, making it ideal for rendering complex geometries in 2D graphics and visualization applications. The package supports multiple platforms including Android, iOS, Web, macOS, Windows, and Linux, ensuring cross-platform consistency. Designed for speed and accuracy, it handles both simple and complex polygons with holes, providing reliable results for computational geometry tasks.

Use cases

  • 2D game development
  • Web-based map rendering
  • Vector graphics processing
  • Interactive data visualization
  • Mesh generation for UI components

Key features

  • Fast triangulation performance
  • Supports polygons with holes
  • Cross-platform compatibility
  • Simple API for polygon input
  • Accurate results for complex shapes

Suitable for

  • Graphics developers
  • GIS application creators
  • UI/UX designers working with custom shapes
  • Game engine integrators
  • Data visualization engineers

Considerations

  • Requires valid polygon input (non-intersecting edges)
  • Not optimized for real-time dynamic updates
  • Limited to 2D triangulation
  • Does not handle self-intersecting polygons directly
  • May need preprocessing for irregular inputs

Original README

Original README snapshot from the linked source repository. Visit the repository for the latest content.

dart_earcut

Ear-clipping (earcutting) triangulation algorithm, ported (with minor API differences) from earcut4j/earcut4j and mapbox/earcut. Also includes the fix from mapbox/earcut#91.

Usage

  • 2D (x/y) coordinates, without holes

    • triangulateRaw: expects points in the format [x0, y0, x1, y1, x2, y2, ...]
    • triangulateFromPoints: expects 'dart:math's Point objects
    final triangles = Earcut.triangulateRaw([10,0, 0,50, 60,60, 70,10]);
    final triangles = Earcut.triangulateFromPoints([Point(10, 0), Point(0,50), Point(60,60), Point(70,10)]);
    // Both return [1,0,3, 3,2,1]
    
  • Holes
    A list of hole indicies, if any. For example, [5, 8] for a 12-vertice input would mean one hole with vertices 5-7 and another with 8-11. If you pass a single vertice as a hole, Earcut treats it as a Steiner point.

    final List<int> triangles = Earcut.triangulateRaw([0, 0, 100, 0, 100, 100, 0, 100, 20, 20, 80, 20, 80, 80, 20, 80], holeIndices: [4]);
    // Returns [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]
    
    • triangulateFromPointsAndHolePoints performs the logic to generate holeIndices when the outline of a polygon and the outline of its holes are available as points seperately.
  • More dimensions
    Expected to be in the format [x0, y0, z0, x1, y1, z1, x2, y2, z2, ...]

    final List<int> triangles = Earcut.triangulateRaw([10, 0, 1, 0, 50, 2, 60, 60, 3, 70, 10, 4], dimensions: 3);
    // Returns [1,0,3, 3,2,1]
    

The Algorithm

The library implements a modified ear slicing algorithm, optimized by z-order curve hashing and extended to handle holes, twisted polygons, degeneracies and self-intersections in a way that doesn't guarantee correctness of triangulation, but attempts to always produce acceptable results for practical data.

It's based on ideas from FIST: Fast Industrial-Strength Triangulation of Polygons by Martin Held andTriangulation by Ear Clipping by David Eberly.

Categories

Source repository

Projects using this package