search

libgeos / geos

Geometry Engine, Open Source
https://libgeos.org
GNU Lesser General Public License v2.1
1.19k stars 357 forks source link

Structural repair of a multipolygon #1179

Open afabri opened 1 week ago

afabri commented 1 week ago

When I repair a polygon with a hole that sticks out with the structural option I get what I see in the first line. So it is boundary area minus hole area.

What is the formal definition of what happens when repairing a multipolygon which consists of two outer boundaries, and a hole in the first polygon sticking out of it and overlapping with the boundary of the second polygon of the multipolygon?

It does what we see in the second line, so it looks like the union of the structurally repaired polygons. It could have been the union of the boundary areas minus the union of holes.

image

afabri commented 1 week ago

Note also that the PostGIS 3.2.0 Manual states in Section 8.6.4 ST_MakeValid

"structure" is an algorithm that distinguishes between interior and exterior rings, building new geometry by unioning exterior rings, and then differencing all interior rings.

JamesParrott commented 1 week ago

What does JTS do?

In Geos, there are a couple of enumerators. The second one "Assumes that holes and shells are correctly categorized".

https://libgeos.org/doxygen/geos__c_8h.html#acb2987c643bda31b1fcaecff8b62ce98

An MRX would be of great assistance.

afabri commented 1 week ago

I've put code on gist.github.com

dr-jts commented 1 week ago

The GEOS GEOS_MAKE_VALID_STRUCTURE repair mode is algorithmically identical to the JTS GeometryFixer. They both have the behaviour that repair is executed "bottom-up" or "element-wise". So the polygons are repaired individually, and then combined to form the final repaired MultiPolygon,. The invalid hole is removed from its parent polygon only.

MULTIPOLYGON (((0 0, 10 0, 10 10, 0 10, 0 0), (8 6, 8 8, 12 8, 12 6, 8 6)), ((11 0, 15 0, 15 10, 11 10, 11 0)))
image

It's subjective as to what the desirable semantics are for this operation. Certainly it would also be reasonable to remove the hole from all elements of the MultiPolygon, but this is not what was chosen.

afabri commented 1 week ago

That's why I wrote "the union of the structurally repaired polygons". Do you agree that this is different from what the PostGIS Manual states? Does the manual express a "should" or " must"? Do you know what other implementations of ST_MakeValid have implemented?

dr-jts commented 1 week ago

That's why I wrote "the union of the structurally repaired polygons". Do you agree that this is different from what the PostGIS Manual states? Does the manual express a "should" or " must"?

Yes, it's different. The manual should state what the semantics actually are, so it needs to be changed.

Do you know what other implementations of ST_MakeValid have implemented?

This is the RFC for the JTS implementation, which is used for the ST_MakeValid struture mode: https://github.com/locationtech/jts/issues/652.

I'm not aware of any other implementations which subtract holes from an entire MultiPolygon, but there may well be some. It's a reasonable semantic, just not the one chosen.