Skip to content

earcut4j/earcut4j

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

23 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

earcut4j

This triangulation library is based on the javascript version located in @mapbox/earcut

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 and Triangulation by Ear Clipping by David Eberly.

Installation

Download the latest version:

Maven dependency:
<dependency>
  <groupId>io.github.earcut4j</groupId>
  <artifactId>earcut4j</artifactId>
  <version>2.2.2</version>
</dependency>
Or when using Gradle:
dependencies {
  compile "io.github.earcut4j:earcut4j:2.2.2"
}

Usage

List<Integer> triangles = Earcut.earcut(new double[] { 10,0, 0,50, 60,60, 70,10 }, null, 2);
// returns [1,0,3, 3,2,1]

Signature: earcut(double[] data, int[] holeIndices, int dim).

  • data is a flat array of vertice coordinates like [x0,y0, x1,y1, x2,y2, ...].
  • holeIndices is an array of hole indices if any (e.g. [5, 8] for a 12-vertice input would mean one hole with vertices 5–7 and another with 8–11).
  • dim is the number of coordinates per vertice in the input array (2 by default).

Each group of three vertice indices in the resulting array forms a triangle.

// triangulating a polygon with a hole
List<Integer> triangles = Earcut.earcut(new double[] { 0, 0, 100, 0, 100, 100, 0, 100, 20, 20, 80, 20, 80, 80, 20, 80 }, new int[] { 4 }, 2);
// [3,0,4, 5,4,0, 3,4,7, 5,0,1, 2,3,7, 6,5,1, 2,7,6, 6,1,2]

// triangulating a polygon with 3d coords
List<Integer> triangles = Earcut.earcut(new double[] { 10, 0, 1, 0, 50, 2, 60, 60, 3, 70, 10, 4 }, null, 3);
// [1,0,3, 3,2,1]

If you pass a single vertice as a hole, Earcut treats it as a Steiner point.

About

Java implementation of earcut polygon triangulation library based on https://github.com/mapbox/earcut

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages