Iterated noding failed to converge

[pjanetzek]

Hello, I ran into this error and was wondering if it's expected or be considered a bug:

ERROR: GEOSNode: TopologyException: Iterated noding failed to converge after 6 iterations (near 132163 474)

select st_node('MULTILINESTRING(
(125635 6696,131951 6376,132163 474.0000000000043,128381 1569.9999999999986,125635 6696),
(125635 6696,131951 6376,132163 474,128381 1570,125635 6696))'::geometry)

I'm using Arch linux with libgeos 3.11.1-1

[pjanetzek]

Snapping the geometry to an appropriate grid to made it work for me

[dr-jts]

This is more of a design issue than a bug. It's a robustness problem with the current implementation of GEOSNode. The cause is the nearly parallel segments in the two lines:

This code is pretty old. If some recent improvements can be brought into GEOSNode that might avoid the failure for this case. Unfortunately so far there is no 100% guaranteed way to avoid all robustness errors.

[dr-jts]

@pjanetzek A question for you: It looks like you are performing the noding using PostGIS (or some other DB). Currently ST_Node operates as a function on a single geometry. This means that to use it on a set of geometry records they must be combined into a single geometry, and thus the noded output no longer has the attributes of the original records. It is possible to expose noding using a window function (say ST_NodeWin), which would allow preserving the original attribution.

What is your use case for noding? Would attribute preservation via a window function be useful for you?

[dr-jts]

Also, in PostGIS ST_Node is essentially the same as ST_UnaryUnion. And in recent GEOS versions the union function is more robust than the noding function. Indeed, UnaryUnion in GEOS works for the example geometry:

bin/geosop -a "MULTILINESTRING(
(125635 6696,131951 6376,132163 474.0000000000043,128381 1569.9999999999986,125635 6696),
(125635 6696,131951 6376,132163 474,128381 1570,125635 6696))" unaryUnion

MULTILINESTRING ((125635 6696, 131951 6376), (131951 6376, 132163 474.0000000000043), (132163 474.0000000000043, 128381 1569.9999999999986), (128381 1569.9999999999986, 125635 6696))

Note that the window function version ST_NodeWin proposed above would be different, in that it would not dissolve duplicate linework. It would be nice to hear of use cases for this.

[martinfleis]

What is your use case for noding? Would attribute preservation via a window function be useful for you?

I can see this very useful for our use cases when working with urban street networks that come from OpenStreetMap or other sources. We often need to add additional nodes on intersections when there are none or as a preprocessing step prior polygonization to ensure proper result. Having the geometry properly noded and containing the original attributes would be super helpful.

Also, in PostGIS ST_Node is essentially the same as ST_UnaryUnion

Is this the case in GEOS (via shapely) as well? Shall we rather use shapely.unary_union over node? It tends to be faster to use union over an array of geoms than creating a collection and noding that.

[dr-jts]

What is your use case for noding? Would attribute preservation via a window function be useful for you?

I can see this very useful for our use cases when working with urban street networks that come from OpenStreetMap or other sources. We often need to add additional nodes on intersections when there are none or as a preprocessing step prior polygonization to ensure proper result. Having the geometry properly noded and containing the original attributes would be super helpful.

Thanks for the reply. Linear network noding is indeed one of the use cases that I thought would be useful.

Also, in PostGIS ST_Node is essentially the same as ST_UnaryUnion

Is this the case in GEOS (via shapely) as well? Shall we rather use shapely.unary_union over node? It tends to be faster to use union over an array of geoms than creating a collection and noding that.

Yes, this is how GEOS works (PostGIS uses it). So Shapely should work in the same way.

[pjanetzek]

@dr-jts Thanks a lot for your suggestions! I'm currently revisiting old plpgsql code for generating 3D models with roof shapes from OpenStreetMap data that I procrastinated for a university project ten years ago. Now I'm trying to get it to a state that it finally could be released onto the public. Looking at your image there is certainly a bug in the quadruple_saltbox roof code.

Yes, I recall there were cases where it was tricky to reattach the line attributes after noding.

[dr-jts]

A further note: in PostGIS you can combine noding and snapping to a grid by using ST_UnaryUnion with the gridSize option specified. E.g. ST_UnaryUnion(geom, 1000) to snap to the 3rd decimal place.

A future ST_NodeWin will also provide this option.

[martinfleis]

We have recently discussed exposing shapely.node on the level of geopandas.GeoDataFrame and decided to postpone the implementation as the optimal API would be exactly the one outlined above as ST_NodeWin, i.e. the one that retains the attributes of all geometries in a data frame and only fixes noding within the geometry column.

Just wanted to mention this here in case it makes a difference when putting ST_NodeWin on the roadmap.