Friday, April 23, 2010

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]);
}

}

No comments:

Post a Comment