earcut - The fastest and smallest JavaScript polygon triangulation library for your WebGL apps

  •        303

The fastest and smallest JavaScript polygon triangulation library. 2.5KB gzipped.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.




Related Projects

delaunator - A really fast JavaScript library for Delaunay triangulation of 2D points

  •    Javascript

A really fast JavaScript library for Delaunay triangulation of 2D points.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.

turf - A modular geospatial engine written in JavaScript

  •    Javascript

Turf is a JavaScript library for spatial analysis. It includes traditional spatial operations, helper functions for creating GeoJSON data, and data classification and statistics tools. Turf can be added to your website as a client-side plugin, or you can run Turf server-side with Node.js (see below).Download the minified file, and include it in a script tag. This will expose a global variable named turf.

flatbush - A very fast static spatial index for 2D points and rectangles in JavaScript

  •    Javascript

A really fast static spatial index for 2D points and rectangles in JavaScript. An efficient implementation of the packed Hilbert R-tree algorithm. Enables fast spatial queries on a very large number of objects (e.g. millions), which is very useful in maps, data visualizations and computational geometry algorithms.

polypartition - Tiny Polygon Partitioning and Triangulation Library

  •    C++

PolyPartition is a lightweight C++ library for polygon partition and triangulation. PolyPartition implements multiple algorithms for both convex partitioning and triangulation. Different algorithms produce different quality of results (and their complexity varies accordingly). The implemented methods/algorithms with their advantages and disadvantages are outlined below. For input parameters and return values see method declarations in polypartition.h. All methods require that the input polygons are not self-intersecting, and are defined in the correct vertex order (conter-clockwise for non-holes, clockwise for holes). Polygon vertices can easily be ordered correctly by calling TPPLPoly::SetOrientation method.

Wykobi Computational Geometry Library

  •    C++

Wykobi is an efficient, robust and simple to use multi-platform 2D/3D computational geometry library. Wykobi provides a concise, predictable, and deterministic interface for geometric primitives and complex geometric routines using and conforming to the ISO/IEC 14882:2003 C++ lan

Simple Polygon Triangulation


A concise implementation of the 'ear clipping' (aka 'subtracting ears') algorithm to convert simple (convex or concave, no holes) polygons to a collection of triangles. These triangles can then easily be used in 3D mesh geometries. The implementation favors simplicity over per...

Computational Geometry

  •    CSharp

A library of Computational Geometry algorithms such as convex hulls, Voronoi diagrams, line intersections, triangulations, and more; written in C#.

supercluster - A crazy fast geospatial point clustering library for browsers and Node.

  •    Javascript

A very fast JavaScript library for geospatial point clustering for browsers and Node.Loads an array of GeoJSON Feature objects. Each feature's geometry must be a GeoJSON Point. Once loaded, index is immutable.

polylabel - A fast algorithm for finding the pole of inaccessibility of a polygon (in JavaScript and C++)

  •    C++

A fast algorithm for finding polygon pole of inaccessibility, the most distant internal point from the polygon outline (not to be confused with centroid), implemented as a JavaScript library. Useful for optimal placement of a text label on a polygon.This is an iterative grid-based algorithm, which starts by covering the polygon with big square cells and then iteratively splitting them in the order of the most promising ones, while aggressively pruning uninteresting cells.

delaunay - Fast Delaunay Triangulation in JavaScript.

  •    Javascript

This is just a quick little implementation of Delaunay Triangulation in JavaScript. It was mostly ported from Paul Bourke's C implementation, but I referenced some bits from another JavaScript implementation and rewrote a bunch of things in ways more amenable to fast JavaScript execution. To the extent possible by law, I have waived all copyright and related or neighboring rights to this library.


  •    C++

[2017/11/12] - Added simple tessellation shader sample. Fixed misc issues with pipeline setup for tessellation. [2017/11/10] - Added ChessSet demo. Added geometry shader sample. Fixes to depth stencil handling. [2017/11/10] - Added TexturedCube sample. Updated depth attachment handling on swapchain render pass. Switched out lc_image for stb_image. Added DXC shader build script. [2017/05/27] - Fixed some annoying buffer state transitions. Added build script for shaders. Updated shader naming convention to be more exact. Added OpaqueArgs and PassingArrays for investigation. [2017/05/20] - Updated Append/Consume sample for Vulkan. Requires latest glslang. ConstantBuffer also works for both platforms. [2017/05/13] - Added Linux support. Moved to project files to cmake. Moved glsl shaders to glsl sub directory - forcing HLSL for now. [2017/04/30] - Clarified shader usage in some sample programs to point out which source they're coming from. [2017/04/27] - Added ConstantBuffer sample (D3D12 only for now). Updated Vulkan samples to use negative viewport height. [2017/04/25] - Updated SimpleCompute and StructuredBuffer to work on Vulkan. [2017/04/24] - Added compute samples (D3D12 only for now). One for simple compute and another for structured buffers.

verb - Open-source, cross-platform NURBS

  •    Javascript

verb is a library for creating and manipulating NURBS surfaces and curves in many languages including JavaScript. verb provides advanced tools like derivative evaluation, adaptive tessellation, and intersection. Verb provides a concurrent execution runtime via WebWorkers in modern browsers and thread pools on other platforms and is suitable for use in a datacenter or in the browser.

cgal - The public CGAL repository, see the README below

  •    C++

The Computational Geometry Algorithms Library (CGAL) is a C++ library that aims to provide easy access to efficient and reliable algorithms in computational geometry. The primary vector of distribution of CGAL are sources tarballs, released twice a year, announced on the web site of CGAL. The sources distributed that way can be built using the CGAL installation manual.

CleverAlgorithms - An open source book that describes a large number of algorithmic techniques from the the fields of Biologically Inspired Computation, Computational Intelligence and Metaheuristics in a complete, consistent, and centralized manner such that they are accessible, usable, and understandable

  •    TeX

Clever Algorithms: Nature-Inspired Programming Recipes is an open source book that describes a large number of algorithmic techniques from the the fields of Biologically Inspired Computation, Computational Intelligence and Metaheuristics in a complete, consistent, and centralized manner such that they are accessible, usable, and understandable. This is a repository for the book project used during the development and ongoing maintenance of the books’ content. Implementing an Artificial Intelligence algorithm is difficult. Algorithm descriptions may be incomplete, inconsistent, and distributed across a number of papers, chapters and even websites. This can result in varied interpretations of algorithms, undue attrition of algorithms, and ultimately bad science. This book is an effort to address these issues by providing a handbook of algorithmic recipes drawn from the fields of Metaheuristics, Biologically Inspired Computation and Computational Intelligence, described in a complete, consistent, and centralized manner. These standardized descriptions were carefully designed to be accessible, usable, and understandable. Most of the algorithms described were originally inspired by biological and natural systems, such as the adaptive capabilities of genetic evolution and the acquired immune system, and the foraging behaviors of birds, bees, ants and bacteria. An encyclopedic algorithm reference, this book is intended for research scientists, engineers, students, and interested amateurs. Each algorithm description provides a working code example in the Ruby Programming Language.

rbush - RBush — a high-performance JavaScript R-tree-based 2D spatial index for points and rectangles

  •    Javascript

RBush is a high-performance JavaScript library for 2D spatial indexing of points and rectangles. It's based on an optimized R-tree data structure with bulk insertion support. Spatial index is a special data structure for points and rectangles that allows you to perform queries like "all items within this bounding box" very efficiently (e.g. hundreds of times faster than looping over all items). It's most commonly used in maps and data visualizations.

point-in-polygon - determine if a point is inside a polygon

  •    Javascript

Determine if a point is inside of a polygon.This module casts a ray from the inquiry point and counts intersections, based on this algorithm.

Visualization Toolkit

  •    C++

The Visualization Toolkit (VTK) is an open-source, freely available software system for 3D computer graphics, image processing and visualization. VTK supports a wide variety of visualization algorithms including: scalar, vector, tensor, texture, and volumetric methods; and advanced modeling techniques such as: implicit modeling, polygon reduction, mesh smoothing, cutting, contouring, and Delaunay triangulation.

toxiclibsjs - Toxiclibsjs is a library for computational design tasks with JavaScript

  •    Javascript

Toxiclibs.js is a port of Karsten Schmidt's Toxiclibs for Java and Processing. Toxiclibs.js provides powerful datatypes for the browser and node. It works well for manipulating any DOM element, including Canvas and SVG. The plethora of examples demonstrate its use for geometry and color manipulation as well as physics, automata and more. The examples pair with such fine libraries as: Processing.js, Three.js, D3.js or Raphael.js.

mapbox-gl-js - Interactive, thoroughly customizable maps in the browser, powered by vector tiles and WebGL

  •    Javascript

Mapbox GL JS is a JavaScript library for interactive, customizable vector maps on the web. It takes map styles that conform to the Mapbox Style Specification, applies them to vector tiles that conform to the Mapbox Vector Tile Specification, and renders them using WebGL.Mapbox GL JS is part of the cross-platform Mapbox GL ecosystem, which also includes compatible native SDKs for applications on Android, iOS, macOS, Qt, and React Native. Mapbox provides building blocks to add location features like maps, search, and navigation into any experience you create. To get started with GL JS or any of our other building blocks, sign up for a Mapbox account.