Creating a Polygon from a MultiLineString

[nk9]

I have a set of LineStrings which form the boundaries of a polygon. Unfortunately, I can't guarantee that they are in the correct order, or that the points in them are all directed in the appropriate direction.

How can I merge them into a single Polygon? Convex Hull won't do it, as some polygons will be C-shaped. I want something like Shapely's polygonize. I'm considering rs_concaveman, but wanted to first check I wasn't missing something already in the geo universe.

[kylebarron]

I'm considering rs_concaveman, but wanted to first check I wasn't missing something already in the geo universe.

FWIW there's also concave hull in geo: https://docs.rs/geo/latest/geo/algorithm/concave_hull/trait.ConcaveHull.html

[nk9]

LOL, I somehow completely missed this. I think I was expecting it to be next to ConvexHull, but of course they're ordered alphabetically! I'll give this a shot, thanks.

[urschrei]

I have a set of LineStrings which form the boundaries of a polygon
I can't guarantee that they are in the correct order

Do you mean that order of the set might not conform to [exterior, [interiors]], or that the linestrings might have loops, which wouldn't be valid polygon rings?

If it's the latter, how is that different from "they might not all be directed in the same direction"?

Looking at the JTS docs (GEOS will do the same thing), I wonder whether we don't already have the internal machinery to do this, in the form of the geomgraph module. It's worth noting that polygonize expects a planar graph, and not (essentially) a bag of points. So it will not work if you have dangling lines, cut edges, or loops.

There's a good reason for that, which is that it's tricky to write an algorithm that will do the right thing (produce a valid geometry) without some constraints on the input: otherwise you essentially might have to guess (in the form of some heuristic) how to actually connect lines into rings, and there's no guarantee it'll be correct.

[nk9]

Apologies for not doing so before now! Please have a look at the issue I've opened with Rust GEOS, there's sample code there including GeoJSON parsed into GeosGeometry structs by way of geo.

[nk9]

I've just discovered JTS TestBuilder. And it has revealed that there's a non-simple intersection in the polygon that's failing, whereas the successful polygonize case is classed as "simple".

This is at 10^-10! I wonder if this is the issue? This kind of trivial overlap is going to happen all the time in my data. Is there a straightforward way to round my nodes, or algorithmically simplify the LineStrings in such a way that these end points wind up actually being the same point?

[nk9]

Indeed, this is (at least part of) the problem. When I round-trip the MultiLineString through GEOS with set_rounding_precision set to 6 decimal places, the shape becomes simple, and polygonize works! Not ideal to have to turn my geometries into WKT only to parse them out again, though. And I'm sure there will be situations where simply rounding won't address the problem. (Like .0000004 and .0000005 are right next to each other, but would be rounded to different values, which could conceivably generate the same sort of non-simple overlap.) Would be very interested to hear if there are any other solutions.

Sorry for the spam in this thread, LOL, hope it helps someone else debugging this kind of issue in the future!

[urschrei]

JTS has a snapping noder which I'm pretty sure is what you need to solve this. We have internal noding methods (ported from JTS) for geometries, but I can't recall whether they have snapping, and I'm not in front of a real screen so I can't check til tomorrow. If we dont, we'd have to look at what it would take to implement. GEOS may also have it, since it has a lot of feature parity with JTS.

[urschrei]

Rounding is always an option, but it's obviously a trade-off; if you can throw away four decimal places of precision and still have enough detail (totally plausible for real-world geometries; that's ~10 cm in most projections) that's probably the easiest thing to do.