javajts

JTS polygon buffer produces a MultiPolygon when there are self-intersections, but only with inner buffer, not outer. Why?


I need a buffer sometimes around a polygon and sometimes inside a polygon. I had an own naive solution in the past but decided to use something more robust this time: Here comes my first attempt with JTS.

Here is my observation. It might be my bug, but most likely I'm doing something wrong.

If you make the inner buffer self-intersect, the buffer algorithm gives you (correctly) a MultiPolygon. See picture below, the buffer is the rounded shape, the source polygon is filled.

inner buffer with self-intersection

Howewer, if you have an outer buffer and make a C-shaped polygon so that the buffer self-intersects, only a Polygon is produced, IMO not ok. Here:

outer buffer with self-intersection

It looks like the algorithm did most of the work, but the path did not get split. If there was an index, where in the list of coordinates the second ring begins, one would split the list and have the right result. These two splits would make the correct two Polygons of a MultiPolygon I would like to have as an outcome.

From other experience I assumed the orientation of the source polygon might be an issue. I tried reversing them, but that had no effect.

I followed the debugger into the sources of JTS (1.19.0) to see what was going on, but that is above my head for now. I might go back and try that again with more coffee, but hopefully someone gives me some insight here.

I'm rendering with JavaFX Canvas, I'm sure that has nothing to do with it. Because: It's the Geometry.buffer() method (called on a Polygon class), that produces MultiPolygon or Polygon respectively in these two scenarios.

A simplified code would be:

Polygon polygon = (new GeometryFactory()).createPolygon(new Coordinate[]{
    new Coordinate(0,0),
    new Coordinate(10,0),
    new Coordinate(10,10),
    new Coordinate(0,10)/*, ...a lot loaded from file*/
});
//optionally here check if Orientation.isCCW(polygon.getCoordinates())
//then polygon = polygon.reverse()

//would produce a MultiPolygon if buffer self-intersected like in the 1st picture
Geometry innerPadding = polygon.buffer(-1);

//would produce a malformed Polyon if buffer self-intersected like in the 2nd picture
Geometry outerMargins = polygon.buffer(1);

//to get simple Polygons from a MultiPolygon
for (int n = 0; n < innerPadding.getNumGeometries(); n++) {
    Geometry part = innerPadding.getGeometryN(n);
    //here "part" would be a Polygon instance
    //render using a loop over part.getCoordiantes()
}

Solution

  • The problem is a misunderstanding what a Polygon and a MultiPolygon is and therefore how it's content should be retreived and rendered.

    A MultiPolygon is simply a collection of Polygons. Calling getNumGeometries() and getGeometryN(int) is used to get those one by one. That is however not used to store holes next to the polygon's shell. That's what I got wrong.

    A Polygon is not only a closed line as I thought (or does not have to be). The Polygon contains a LinearRing of the shell (get by calling getExteriorRing()) and can hold a number of holes which are also LinearRings (get the amount of holes with getNumInteriorRing() and then each with getInteriorRingN(int)).

    Calling getCoordinates() on the Polygon will give the coordinates of all LinearRings concatenated into a single array, not making much sense by itself as demonstrated by the picture in the question. To use the data right one would call getCoordinates() on each of the rings instead. Rendering the buffer as a shell and a triangle-shaped hole (Interior ring) is the way to go.

    The first image (inner buffer) worked well from the beginning, because the output of buffer(-1) was a MultiPolygon comprised of two Polygons without holes.

    Here a happy image:

    Outer buffer with a hole

    Edit:

    The CoordianteSequence class is your friend. Using getCoordiantes() which returns a possibly constructed array of possibly constructed copies of coordinates at any place might be wasteful, creating garbage in the rendering loop.

    You can access the Xs and Ys of each LinearRing easily without using these Coordiante arrays:

    CoordinateSequence cs = somePolygon.getExteriorRing().getCoordinateSequence();
    for (int i = 0; i < cs.size(); i++) {
        double x = cs.getX(i), y = cs.getY(i);
        //Use...
    }
    //The same for each interior ring
    

    Since Polygons in normal form have shell points in clockwise orientation and holes in couter-clockwise orientation, rendering using JavaFX Canvas is very easy:

    //GraphicsContext gc from your Canvas, assuming you've set a fill Paint etc.
    //Polygon somePolygon made with JTS in normal form
    gc.beginPath();
    CoordinateSequence cs = somePolygon.getExteriorRing().getCoordinateSequence();
    gc.moveTo(cs.getX(0), cs.getY(0));
    for (int i = 1; i < cs.size(); i++) {
        double x = cs.getX(i), y = cs.getY(i);
        gc.lineTo(x, y);
    }
    //LinearRings (as other closed structures) in JTS repeat the first point
    //as the last, so the last lineTo will close the rendered loop
    
    for (int holeIdx = 0; holeIdx < somePolygon.getNumInteriorRing(); holeIdx++) {
        //exactly the same code as above, just for each hole
        cs = somePolygon.getInteriorRingN(holeIdx).getCoordinateSequence();
        gc.moveTo(cs.getX(0), cs.getY(0));
        for (int i = 1; i < cs.size(); i++) {
            double x = cs.getX(i), y = cs.getY(i);
            gc.lineTo(x, y);
        }
    }
    gc.closePath();
    gc.fill();
    //Even with the default FillRule.NON_ZERO fill() will result in filling only
    //the "inside" of the Polygon, leaving the holes untouched
    //(because Exterior is oriented Clockwise and Interior Counter-Clockwise