JarCasting
JarCasting JarCasting

earcut4j

earcut4j for polygon triangulation

License

License
GroupId

GroupId

io.github.earcut4j
ArtifactId

ArtifactId

earcut4j
Last Version

Last Version

2.2.2
Release Date

Release Date
Type

Type

jar
Description

Description

earcut4j
earcut4j for polygon triangulation
Project URL

Project URL

https://github.com/earcut4j/earcut4j
Source Code Management

Source Code Management

https://github.com/earcut4j/earcut4j

Download earcut4j

Filename Size
earcut4j-2.2.2.pom
earcut4j-2.2.2.jar 11 KB
earcut4j-2.2.2-sources.jar 8 KB
earcut4j-2.2.2-javadoc.jar 389 KB
Browse

How to add to project

<!-- https://jarcasting.com/artifacts/io.github.earcut4j/earcut4j/ -->
<dependency>
    <groupId>io.github.earcut4j</groupId>
    <artifactId>earcut4j</artifactId>
    <version>2.2.2</version>
</dependency>
// https://jarcasting.com/artifacts/io.github.earcut4j/earcut4j/
implementation 'io.github.earcut4j:earcut4j:2.2.2'
// https://jarcasting.com/artifacts/io.github.earcut4j/earcut4j/
implementation ("io.github.earcut4j:earcut4j:2.2.2")
'io.github.earcut4j:earcut4j:jar:2.2.2'
<dependency org="io.github.earcut4j" name="earcut4j" rev="2.2.2">
  <artifact name="earcut4j" type="jar" />
</dependency>
@Grapes(
@Grab(group='io.github.earcut4j', module='earcut4j', version='2.2.2')
)
libraryDependencies += "io.github.earcut4j" % "earcut4j" % "2.2.2"
[io.github.earcut4j/earcut4j "2.2.2"]

Dependencies

test (1)

Group / Artifact Type Version
junit : junit jar 4.13.2

Project Modules

There are no modules declared in this project.

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.

Versions

Version
2.2.2