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?

Lombard

I'm by no means a skilled enough programmer to provide you a solution, but perhaps you might begin with a list of vertices along the edge. Then, find a point inside the shape and connect the nearest vertices to it. Then, find a point further in, and repeat. Do so until each vertex either A (has a minimum amount of edges connected), or B (the points never exceed x distance apart). Either way, the naive algorithm above connects only existing points; your desired algorithm must create new points near existing points. – Scoles

Wanted to comment on this earlier: Creating a "good" triangulation is really challenging. I had some promising results with the Ruppert class from www3.math.tu-berlin.de/jtem/numericalMethods , but it does not treat holes. I consider the "triangle" package that you mentioned as THE solution for triangulations (it's really good). But - it's implemented in a horrible, horrible "C"ish way, and can not even remotely be ported to java (never-ever ... horrible). Once I wrote a small wrapper for this lib with JNI, but it is not published yet and might still need some cleanups. – Twenty

@Twenty perhaps you should try the library suggested in my answer :) has worked quite well for me so far... – Tiphane

@Tiphane There are some (java) triangulation libs out there ( see github ), but it's a looong path from "implementing ear clipping as described on wikipedia" to a good, robust library with steiner points, hole handling, angle constraints etc. The one that you linked to at least looks like it was non-trivial and maintained and tested for a while (although I won't upvote until I tested it). A pity that the creator of the triangle lib did not respond to my request to publish the Java bindings for his lib... – Twenty

@Twenty yes, try it out, it has worked nicely for me so far. I also considered at some point the Triangle library, but didn't found any Java versions (now I know why :/) and also found that their licence has its restrictions when planning to go commercial. Thanks for the other link you included, will check it out – Tiphane

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)

Tiphane

Be aware that this library will not work if you need to triangulate polygons in 3D space. Although its PolygonPoint class has a Z coordinate, the triangulation code only looks at X and Y so if you have a vertical polygon (e.g. a wall) the library will treat its vertices as colinear and refuse to triangulate it. – Tver

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

Loferski

How are you drawing the triangulation? – Schleicher

@BilalBashir Processing. – Loferski

I am sure I just meant is there a library you are using to do it (adding the points to a frame and then drawing lines)? If so which one? Or is this just all from scratch with a JPanel and Graphics. – Schleicher

@BilalBashir It's a Java library / environment called Processing! – Loferski

I don't understand the point of SO if such great answers don't get more upvotes. – Camphorate