Skip to main content

A clip round the ear

Inspired by a recent discussion on the JTS user list about decomposing simple polygons into triangles, here is a program that demonstrates the brute force, ear-clipping algorithm. To run this you will need the JTS library which you can get from the project web site or as a maven artifact (version 1.11) from the Maven central repository.


import com.vividsolutions.jts.algorithm.Angle;
import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.LineString;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.io.WKTReader;
import java.util.ArrayList;
import java.util.List;

/**
* Demonstrates brute force approach to the ear clipping algorithm
* to triangulate a polygon. This demo doesn't yet cope with
* polygons that have holes.
*
* @author Michael Bedward
*/
public class EarClipping {
private static final double EPS = 1.0E-4;

GeometryFactory gf = new GeometryFactory();

public static void main(String[] args) throws Exception {
new EarClipping().demo();
}

/**
* Demonstrate the ear-clipping algorithm
* @throws Exception
*/
private void demo() throws Exception {
WKTReader reader = new WKTReader(gf);
Polygon poly = (Polygon )reader.read("POLYGON((0 0, 5 0, 2 3, 5 5, 10 0, 10 -5, 5 -2, 0 -5, 0 0))");
System.out.println("Input polygon:");
System.out.println(poly);

Geometry ears = triangulate(poly);
final int n = ears.getNumGeometries();

System.out.println();
System.out.println("Found " + n + " ears:");
for (int i = 0; i < n; i++) {
System.out.println(ears.getGeometryN(i));
}
}

/**
* Brute force approach to ear clipping
*
* @param inputPoly input polygon
* @return GeometryCollection of triangular polygons
*/
private Geometry triangulate(Polygon inputPoly) {
if (inputPoly.getNumInteriorRing() > 0) {
throw new IllegalArgumentException("Can't deal with polgons that have holes yet");
}

List<Polygon> ears = new ArrayList<Polygon>();
Polygon workingPoly = (Polygon) inputPoly.clone();

Coordinate[] coords = workingPoly.getBoundary().getCoordinates();
coords = removeColinearVertices(coords);
int N = coords.length - 1;

boolean finished = false;
int k0 = 0;
do {
int k1 = (k0 + 1) % N;
int k2 = (k0 + 2) % N;
LineString ls = gf.createLineString(new Coordinate[] {coords[k0], coords[k2]});

if (workingPoly.covers(ls)) {
Polygon ear = gf.createPolygon(
gf.createLinearRing(new Coordinate[]{coords[k0], coords[k1], coords[k2], coords[k0]}),
null);
ears.add(ear);
workingPoly = (Polygon) workingPoly.difference(ear);
coords = workingPoly.getBoundary().getCoordinates();
coords = removeColinearVertices(coords);
N = coords.length - 1;
k0 = 0;
if (N == 3) { // triangle
ears.add(gf.createPolygon(gf.createLinearRing(coords), null));
finished = true;
}
} else {
k0++ ;
}
} while (!finished);

return gf.createGeometryCollection(ears.toArray(new Geometry[0]));
}

/**
* Remove co-linear vertices. TopologyPreservingSimplifier could be
* used for this but that seems like over-kill.
*
* @param coords polygon vertices
* @return coordinates with any co-linear vertices removed
*/
private Coordinate[] removeColinearVertices(Coordinate[] coords) {
final int N = coords.length - 1;
List<Coordinate> coordList = new ArrayList<Coordinate>();

for (int j = 1; j <= N; j++) {
int i = (j - 1) % N;
int k = (j + 1) % N;
if (Math.abs(Math.PI - Angle.angleBetween(coords[i], coords[j], coords[k])) > EPS) {
coordList.add(coords[j]);
}
}

coordList.add(new Coordinate(coordList.get(0)));
return coordList.toArray(new Coordinate[0]);
}

}

Comments

Popular posts from this blog

Fitting an ellipse to point data

Some time ago I wrote an R function to fit an ellipse to point data, using an algorithm developed by Radim Halíř and Jan Flusser1 in Matlab, and posted it to the r-help list. The implementation was a bit hacky, returning odd results for some data. A couple of days ago, an email arrived from John Minter asking for a pointer to the original code. I replied with a link and mentioned that I'd be interested to know if John made any improvements to the code. About ten minutes later, John emailed again with a much improved version ! Not only is it more reliable, but also more efficient. So with many thanks to John, here is the improved code: fit.ellipse <- function (x, y = NULL) { # from: # http://r.789695.n4.nabble.com/Fitting-a-half-ellipse-curve-tp2719037p2720560.html # # Least squares fitting of an ellipse to point data # using the algorithm described in: # Radim Halir & Jan Flusser. 1998. # Numerically stable direct least squares fitting of ellipses. …

Build an application plus a separate library uber-jar using Maven

I've been working on a small Java application with a colleague to simulate animal movements and look at the efficiency of different survey methods. It uses the GeoTools library to support map projections and shapefile output. GeoTools is great but comes at a cost in terms of size: the jar for our little application alone is less than 50kb but bundling it with GeoTools and its dependencies blows that out to 20Mb.

The application code has been changing on a daily basis as we explore ideas, add features and fix bugs. Working with my colleague at a distance, over a fairly feeble internet connection, I wanted to package the static libraries and the volatile application into separate jars so that he only needed to download the former once (another option would have been for my colleague to set up a local Maven repository but for various reasons this was impractical).

A slight complication with bundling GeoTools modules into a single jar (aka uber-jar) is that individual modules make ext…

Circle packing with R

To visualize the results of a simulation model of woodland trees within R, I needed an algorithm that could arrange a large number of circles within a rectangle such that no two circles overlapped by more than a specified amount. A colleague had approached this problem earlier by sorting the circles in order of descending size, then randomly dropping each one into the rectangle repeatedly until it landed in a position with acceptable overlap.

I suspected a faster and more robust algorithm could be constructed using some kind of "jiggling the circles" approach. Luckily for me, I discovered that Sean McCullough had written a really nice example of circles packing into a cluster using the Processing language. Sean's program is based on an iterative pair-repulsion algorithm in which overlapping circles move away from each other. Based on this, and modifying the algorithm a little, I came up with an R function to produce constrained random layouts of a given set of circles. He…