Buffer has unexpected boundary artifacts

[grimsa]

Context:
We are taking a 3D model of a residential building's roof faces and doing a union of all of them to end up with the building's outline.
For example, this building has 15 roof faces:

However, there the 3D models that we get are not perfect - there may be tiny gaps / overlaps between adjacent roof faces.

Our current logic is to perform the following:

1. Union all roof faces (this takes care of overlaps)
2. Simplify the result by inflate-deflate (i.e. buffer the result by a positive distance and then by the same a negative distance to fill the tiny gaps)
3. Simplify the result by using DouglasPeuckerSimplifier to remove collinear points

The result of step 1 for the example building produces such polygon:

POLYGON (
  (2.0170067048366906 -84.71337237629689, -12.984315240409249 -84.65217008498418, -40.12517639000342 -84.54144105957226, -40.12517639002321 -84.54144106442428, -44.02720810592564 -84.52552158794427, -44.91690582873482 -84.52189180769467, -44.91690582873031 -84.52189180658837, -87.42860934460377 -84.34845291282237, -87.42860935733478 -84.34845292544992, -95.41482496842893 -84.31587086048607, -94.1050254753286 236.73018045480651, 14.895653180512372 236.28548043114017, 27.196646775505254 248.4865177684017, 94.94657976437676 248.21011221386513, 107.14761031477858 235.9091116721634, 106.460578042544 67.51005066328379, 106.45014245144604 67.51009323831846, 106.16236266062828 -3.027839071738372, 106.17279830171603 -3.0278816469807674, 105.80522876740423 -93.12315983639334, 53.8948266913008 -92.91137621125644, 1.9844246363900568 -92.69959258611956, 2.0170067048366906 -84.71337237629689), 
  (60.83344748977622 189.97129168888915, 60.83344749611575 189.97129169517717, 14.895653180512372 236.28548043114017, 60.83344748977622 189.97129168888915), 
  (30.956462997097567 232.69757332187498, 40.93329171543613 222.8278621420623, 30.956462997097567 232.69757333455448, 27.196646775505254 248.4865177684017, 30.956462997097567 232.69757332187498), 
  (91.05805982958996 232.45237139377738, 91.05805981887482 232.4523713833489, 91.05805983077643 232.45237138590588, 94.94657976437676 248.21011221386513, 91.05805982958996 232.45237139377738), 
  (5.589445021025172 7.913748898311642, 5.5894450210251705 7.913748898311644, 5.5894091562367905 7.91371332495585, 5.589445021025172 7.913748898311642), 
  (54.10661019243061 -41.00094507549473, 36.037647332454895 -22.783932898520042, 54.10661018609108 -41.00094508178274, 54.10661019243061 -41.00094507549473), 
  (-44.844438636949285 -66.75939643693377, -44.84443862894605 -66.75939643696643, -12.704109382918666 -15.970676529420322, -44.844438636949285 -66.75939643693377)
)

Then we inflate it like this: resultFromStep1.buffer(0.7988331909277314, -10) and get this result:

The extrusion in the top-right corner is not expected.
Changing the second parameter seems to change the shape of it - either make it wider or longer

The reason why we noticed it was that after deflating (using the same buffering parameters and negative distance) a very narrow pointy section is not simplified away:

Everything works fine if we reduce the precision after performing the union operation.

JTS version: 1.18.2 with OverlayNG enabled.

Looking at the open issues, #739 seems somewhat similar - maybe they are related?

[dr-jts]

Yes, the buffer boundary artifacts are probably caused by a robustness bug in the buffer code. Are you using the endcap=FLAT parameter?

[dr-jts]

One thing I notice in the sample data is that the gaps are all narrow holes. So in this case at least you can just drop the holes and have a clean result.

Removing narrow holes

To make this a robust workflow you may want to remove only "narrow" holes. There a few heuristics you can use to determine this. This GIS-Stack Exchange post has some good suggestions for how to detect narrow polygons. (It's PostGIS-focussed, but the same techniques can be used with JTS). In particular:

• using the simple Shape Index calculation could work well, and is performant
• use the JTS MaximumInscribedCircle to find holes with a small maximum diameter
• I would avoid using a negative buffer, since that might be slow and might have some failure cases

Removing Gores

Do you also have cases where the outer shell contains narrow "gores"? In this case, the brand new PolygonHull class is a way to remove these (see this blog post). Compute the outer hull of the polygon with a very small area ratio, and that should remove the gores.

If you have sample data with gores, can you share some of that? And if you try the PolygonHull approach I'd like to hear how it works for you. If it's a success I'll do a blog post on this, since it's a generally useful technique.

Note: I see now that the PolygonHull algorithm might be easier to use in this case if it supported a parameter based on the maximum length of the edges to remove (i.e. the width of the "mouth" of the gores"). I will look into adding this.

[dr-jts]

Another idea to remove gores (and spikes): use the VWSimplifier with a small tolerance value. VW simplification works by removing small-area "corners" from a polygon, so using a sufficiently small tolerance can remove spikes and gores. (This is in contrast to the DouglasPeuckerSimplifier, which uses a distance-based approach which is not suitable for this workflow.)

[grimsa]

First of all, thank you for all the comments - they are immensely useful.

Yes, the buffer boundary artifacts are probably caused by a robustness bug in the buffer code. Are you using the endcap=FLAT parameter?

We are not specifying cap style explicitly. We are using Geometry#buffer(double distance, int quadrantSegments) method with -10 as qadrantSegments which translates to joinStyle = JOIN_MITRE with mitreLimit = 10 (BufferParameters line 188). Not sure if cap style is relevant or not in such configuration.

Do you also have cases where the outer shell contains narrow "gores"?

Yes, in our case we can have both narrow holes and gores.

One such case that has both holes and a gore:

POLYGON (
  (-88.42857187767537 -234.59729265207386, -130.44346921367185 -234.59729265802918, -130.44346921367185 -222.593024794631, -137.94612944240316 -222.593024794631, -137.94612944240316 -161.07115205426842, 76.62995336634087 -161.07115204843547, 76.62995336634087 -161.0711520483131, -137.94612944240316 -161.0711520483131, -137.94612944240316 -99.54927934368231, 133.65017118099271 -99.54927934368231, 133.65017118099271 -155.06901814043522, 133.65017118099271 -210.58875693718815, 81.1315495162953 -210.58875693718815, 81.1315495162953 -222.593024794631, -47.91420659166372 -222.593024794631, -47.91420659166372 -234.59729262229737, -70.4221872990504 -234.59729262229737, -88.42857187767537 -234.59729262229737, -88.42857187767537 -234.59729265207386), 
  (-81.67617769512916 -173.82568669188308, -81.67617767393645 -185.82995455528126, -81.67617767393645 -173.82568670712055, -81.67617769512916 -173.82568668592782, -130.44346921367185 -222.593024794631, -81.67617769512916 -173.82568669188308), 
  (-70.42218730202806 -197.08395562361935, -70.4221872990504 -197.0839556206417, -81.67617767393645 -185.82995455528126, -70.42218730202806 -197.08395562361935), 
  (-47.914206597619 -207.5876900428022, -47.91420659166372 -207.5876900428022, -57.4015202075508 -198.1003673635164, -47.914206597619 -207.5876900428022)
)

We hope to soon experiment with some of the options you outlined, will share the results then.

If you have sample data with gores, can you share some of that?

Sure, if additional samples would be useful, we could try to generate some. What format would work best? A text file with one polygon in WKT per line?

[dr-jts]

Good to hear.

Note that I have just made a change to the PolygonHull code to make it better at removing gores and spikes. See #868.

As for additional examples, a WKT test file with one geometry per line is perfect.

[hmurij]

Attached additional examples of geometries with artefacts.

[dr-jts]

Thanks for the additional examples. From the sample I've tried it looks like removing small holes and then using PolygonHull on the shell with a very small area ratio tolerance (say 0.001) removes all the unwanted artifacts.

VWSimplifier probably works even better, since it also can remove "nearly flat" vertices from the polygon edges. It also removes small-area holes as part of the process. One thing to be aware of though is that VWSimplifier currently does not simplify the initial vertex of a ring. I saw at least one case where this resulted in a gore being retained. PolygonHull doesn't have this issue.

[hmurij]

In 100+ cases PolygonHull#hullByAreaDelta(Geometry geom, double areaDeltaRatio) with areaDeltaRatio = 0.0001 removed 99% of narrow gores on outer shell, except one case below.

POLYGON ((297.0685363504 85.1680518624, 138.3932126134 -0.0000015365, 171.8055983282 110.837893827, 127.3878013432 193.5920207069, 171.7537581054 110.8100769428, 138.3516547269 -0.0222990557, 74.7857066522 118.4171800069, 40.7502728478 100.1488587687, 0.0000003 176.0700732374, 38.627797619 196.8033197406, 7.6575972144 254.5034332194, 145.8341964236 328.6689209996, 203.6995776812 220.8608051945, 219.6430308126 229.4183621204, 297.0685363504 85.1680518624))

In addition, to generate hull of set of polygons we've used ConcaveHullOfPolygons#concaveHullByLengthRatio(Geometry polygons, double lengthRatio, boolean isTight, boolean isHolesAllowed) with lengthRatio = 0.000.1, isTight = true, isHolesAllowed = false. In most cases it generated hulls perfectly matching outer shell. However, we've noticed few issues:

1. Parameter isHolesAllowed had no effect and holes were included regardless.
2. MultiPolygons were generated in two cases below, not sure whether it is a bug or expected result.

MULTIPOLYGON (((172.0243958731 135.2960373192, 90.5126264011 201.870287691, 230.1037738866 372.7820841007, 311.6155591692 306.2078516573, 423.3655772683 214.9367040343, 377.1931145312 158.4043440674, 341.5990760564 187.4755578532, 330.8612967498 174.3284954361, 336.2170925461 169.9541777865, 325.4793179478 156.8071136949, 409.620507099 88.0853267217, 337.6773867992 0, 172.0243958731 135.2960373192), (287.5356852975 114.3751288397, 329.6062917062 80.0142311395, 333.6418397572 40.0071127923, 329.6062921421 80.0142312654, 287.5356852975 114.3751288397), (289.8446327861 222.7820677282, 321.5464042541 225.9798502725, 289.8446309554 222.7820685574, 293.4066499438 187.4693933381, 289.8446327861 222.7820677282)), ((89.5609830555 296.1967191359, 183.3198098981 410.9925999962, 230.1037737971 372.7820841738, 136.3449469564 257.9862033136, 89.5609830555 296.1967191359)))

MULTIPOLYGON (((192.2570917695 222.4838807279, 223.2810671715 222.0062618224, 221.0521271936 77.2277271977, 190.0281518012 77.7053633609, 192.2570917695 222.4838807279)), ((51.2573625712 246.2041893484, 121.9230699449 245.1162566267, 192.5887773185 244.0283066473, 189.4576395587 40.6489411075, 118.791932185 41.736891087, 48.1262248114 42.8248238087, 51.2573625712 246.2041893484)), ((1.1012056673 179.7418317986, 50.2224871186 178.9855846044, 49.1212814512 107.4581015829, 0 108.214348761, 1.1012056673 179.7418317986)))

Test examples

[dr-jts]

PolygonHull#hullByAreaDelta(Geometry geom, double areaDeltaRatio) with areaDeltaRatio = 0.0001 removed 99% of narrow gores on outer shell, except one case below.

Yes, that case requires a larger areaDeltaRatio. 0.001 worked for me.

[dr-jts]

Parameter isHolesAllowed had no effect and holes were included regardless.

This does not remove holes from the input polygons. Is that what you are seeing? Perhaps it should do this.

MultiPolygons were generated in two cases below, not sure whether it is a bug or expected result.

This is actually the expected result. The problem is that on one side of the narrow gap there is no vertex to match to the other side, so the triangle actually has a very long side and so is not included in the result. I'm thinking about how best to address this. Possibly by snapping or introducing a vertex. It's also possible that GeometrySnapper could work here.

[hmurij]

This does not remove holes from the input polygons. Is that what you are seeing? Perhaps it should do this.

I was expecting holes to be removed from polygons, but they weren't. Not a big deal, we used Polygon#getExteriorRing to build new polygon without any holes and it worked flawlessly.

Possibly by snapping or introducing a vertex. It's also possible that GeometrySnapper could work here.

GeometrySnapper#snapToSelf(Geometry geom, double snapTolerance, boolean cleanResult) worked perfectly well in this case, producing one clean polygon.
Thank you so much, for your great support!

[grimsa]

(Somewhat related to the original issue)

@dr-jts I wanted to share one more test case related to negative buffer operation and high precision coordinates.

Input polygon looks like this:

A small negative buffer makes the polygon disappear in this case:

    @Test       // Using OverlayNG and JTS 1.18.2
    void negativeBufferMakesPolygonDisappear() throws ParseException {
        Geometry input = new WKTReader().read(
                "POLYGON ((-12.938208669606965 1.849377051662391, -12.938208669607528 1.8493770516624835, -12.938046785276917 1.8503631701941243, -12.93788467995832 1.851350634877792, -12.937884679957756 1.8513506348776994, -12.871316362679488 2.25685159374457, -7.723171526914614 1.4117129496014245, -7.214666756542695 0.9118058484891076, -7.211867863449079 0.9113463717665793, -7.213429304711479 0.9105893191785625, -7.2121918521981945 0.909372789197481, -7.214990746835125 0.9098322661729774, -7.856632151196722 0.5987374479125224, -13.004776986659984 1.4438760927199985, -12.938208669606965 1.849377051662391))"
        );

        Geometry result = input.buffer(-0.001, -10);

        assertFalse(result.isEmpty(), "Result should not be empty");     // Fails
    }

Reducing the precision slightly before performing the buffer operation makes it produce the expected result.

[dr-jts]

A small negative buffer makes the polygon disappear in this case:

The quadrantSegments argument should be positive. Does fixing that solve the problem?

[grimsa]

That is actually intended - we want the JOIN_MITRE join style.
In JTS 1.18.2 it was possible to set it by using negative quadrantSegments value, which I saw was changed in JTS 1.19.0 (#778).

The same buffer operation can be expressed like this for 1.19.0 (producing the same empty result):

        BufferParameters bufferParameters = new BufferParameters();
        bufferParameters.setJoinStyle(BufferParameters.JOIN_MITRE);
        bufferParameters.setMitreLimit(10);
        Geometry result = BufferOp.bufferOp(input, -0.001, bufferParameters);

Using input.buffer(-0.001, 10) produces the geometry, but it has rounded edges, while we want the lines to remain straight:
(blue is input, red is result)