How to triangulate/tesselate some shape in Java?

Question

I want to tessellate country shape from GeoTools to display it in 3D on Earth surface. GeoTools use JTS topology suite inside which looks feature rich.

Does it contain utility to tessellate some shape? I see there is triangulation package, but can't figure out, how to use it for shapes with holes.

Also I with it not just connect existing vertices like here

it should fill shape with multiple vertices inside.

UPDATE

I found, that JTS contains class ConformingDelaunayTriangulationBuilder which allows to make wished tessellations somehow, but it works bad. First of all it allows only constraining, which means additional code is needed to remove triangles from concaved regions. And also it tries to conserve Delaunay nature of tessellation, which leads to creating many additional sections.

Finally it causes ConstraintEnforcementException for complex shapes like countries and unusable.

Also I found "triangle" package, which is written in C and implementing Chew's second algorithm and works well

Now I wonder, was it ported to Java or wrapped into it?

Answer 1

I know this post is relatively old, but I recently faced the same situation and needed some Java Library or similar tool to triangulate some complex Polygons (as I wanted to display them on OpenGL, which can only draw triangles as primitive operations).

After quite some search and testing, the library that worked for me was Poly2Tri from Orbgis. You can get that library from Maven here^*.

This library has many features, including Polygons with holes, Steiner points to optimize your triangulation, and other stuff. A basic usage example would be the following (based from the example on the linked repo):

//Create the polygon passing a List of PolygonPoints
Polygon polygon = new Polygon(
    Arrays.asList(
        new PolygonPoint(0, 0, 0),
        new PolygonPoint(10, 0, 1),
        new PolygonPoint(10, 10, 2),
        new PolygonPoint(0, 10, 3)));
//Here you could add holes as needed, passing them as Polygons
polygon.addHole(someHoleYouCreated);
//Next, proceed to calculate the triangulation of the polygon 
Poly2Tri.triangulate(polygon);
//Finally, obtain the resulting triangles
List<DelaunayTriangle> triangles = polygon.getTriangles();

Edit: Don't know if you already tried, but JTS Topology Suite also has a DelaunayTriangulationBuilder class (that is without the Conforming part). It is found at org.locationtech.jts.triangulate.DelaunayTriangulationBuilder, and perhaps it works better than the other one you tried but performed badly.

^*Note: careful not to use this one instead, as I did at first and found that it was not the correct dependency (wasn't the -core version)

Answer 2

Here's a quick and dirty way using JTS:

First:

• Triangulate your geometry with JTS DelaunayTriangulationBuilder
• Prepare a set of sites, sites; copy in vertex sites from the initial triangulation

Loop:

• Iterate over triangle geometries of the triangulation, adding triangle centroids** to sites
• Re-triangulate using sites(now comprised of the original sites and the new centroid sites)

Finally:

• Intersect the triangulation with the original geometry to restore its concave hull and any holes

**For this dirty technique, I've found that using triangle centroids lead to better results than the triangle circumcenters even though the latter tends to be used in more formal refinements (Chew, Ruppert and so on..)).

Code

static Geometry refinedTriangulation(Geometry g, int nRefinements, double tolerance) {

    DelaunayTriangulationBuilder builder = new DelaunayTriangulationBuilder();
    builder.setSites(g); // set vertex sites
    builder.setTolerance(tolerance); // set tolerance for initial triangulation only

    Geometry triangulation = builder.getTriangles(geometryFactory); // initial triangulation

    HashSet<Coordinate> sites = new HashSet<>();
    for (int i = 0; i < triangulation.getCoordinates().length; i++) {
        sites.add(triangulation.getCoordinates()[i]);
    }

    for (int refinement = 0; refinement < nRefinements; refinement++) {
        for (int i = 0; i < triangulation.getNumGeometries(); i++) {
            Polygon triangle = (Polygon) triangulation.getGeometryN(i);

            if (triangle.getArea() > 50) { // skip small triangles
                sites.add(new Coordinate(triangle.getCentroid().getX(), triangle.getCentroid().getY()));
            }
        }
        builder = new DelaunayTriangulationBuilder();
        builder.setSites(sites);
        triangulation = builder.getTriangles(geometryFactory); // re-triangulate using new centroid sites
    }

    triangulation = triangulation.intersection(g); // restore concave hull and any holes
    return triangulation;
}

You can use triangle.getExteriorRing().getLength() > N or triangle.getArea() > N to skip over refining already-small triangles.

Example

Raw shape

JTS triangulation

JTS triangulation w/ intersection

1 Refinement

3 Refinements