ERROR: XX000: SQL/MM Spatial exception - geometry crosses edge 2, LOCATION: pg_error, lwgeom_pg.c:250

[Lars Aksel Opsahl]

When running a test with about 20 millions edges I see this error 625 times and I am able to handle it most of this errors with different retry patterns but with a side effects that creates extra nodes or having to delete re add an old edge.

I had problems to create a simple test case that failed until I discovered that the order of adding lines are very important.

I case 1 it fails, but in case 2 it goes ok and I have only changed the order of adding the same lines.

I am running on POSTGIS="3.1.0dev 3.1.0alpha2-63-g82d31f3" [EXTENSION] PGSQL="120" GEOS="3.8.1-CAPI-1.13.3" PROJ="7.1.0" LIBXML="2.9.1" LIBJSON="0.11" TOPOLOGY

Test case 1 that fails.

select topology.CreateTopology ('test01_fail', 4258, 1e-06);
select topology.TopoGeo_addLinestring('test01_fail','0102000020A210000019000000ACFF73982FC326404B9D369927344E400127254E38C32640C2A5BE8726344E40D77CA6A844C32640CEAF9C7326344E40D381ACA756C32640E1AAFC7C25344E401DF0AFD469C32640350BB43B24344E408C88BDAB79C32640B862354C23344E40AC7713D78CC32640D006600322344E403AAE4676A5C326402B27EB8120344E40F4A3E194B9C326401FAD7B751F344E408C73E5FDC9C32640259B61591F344E400987DEE2E1C32640F5E27ACA20344E40C64CA25EF0C32640C49A255C23344E40AA0029FBF8C32640453FBF9426344E408EE8F92E00C42640D246BFC72A344E40DF2A99AD06C426404D147C2E2E344E40E0AF13A80FC42640BDC3EDD030344E405458045A15C42640155FA39B33344E4098480E7D1CC426407F37386C36344E40A09630E422C426401894693439344E40CD4AA47E28C426408E4B66063B344E401EC18D942DC42640103EEF213C344E40C896E5EB32C426406F719EFB3C344E406D872B0C36C426409FDB95A73D344E40E6142EF53DC426404531D4BC3E344E406A6F4B3F3CC426405CB521B53F344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_fail','0102000020A2100000040000006A6F4B3F3CC426405CB521B53F344E40C62A4AAE07C4264090943EBE4E344E40C6CE256607C42640BF2FE4C74E344E407EBF3D74E6C3264032E0D16B58344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_fail','0102000020A21000000200000040F09D3D3CC4264026158DB53F344E406A6F4B3F3CC426405CB521B53F344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_fail','0102000020A210000002000000E24A87985CC42640BAF3C47336344E406A6F4B3F3CC426405CB521B53F344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_fail','0102000020A21000001E0000000EEC42BD2AC526400E61A17BFB334E40CEF4B7A926C52640730F09DFFB334E40B08ADC781CC526406675BC13FD334E40EADB93D112C52640AD94AF15FE334E409558BED309C52640D1F4C8D5FE334E40BC4681F403C52640CAD53494FF334E409A5F28BBF4C426407BD058A002344E40D0CBCDDCE8C42640E5D6FF9405344E40CE5AC0BAE0C4264090FDE20808344E40F37B5171D2C42640643BDF4F0D344E40A58DD948C8C426408C07A57911344E40852BFB09C2C42640CCA843B813344E40CCA66D0DB6C42640DDDFEA4A15344E40B475CB69AAC426400CC0AB8A15344E40D6D127A897C42640ADA0698915344E40765BD88981C4264054104DEA15344E405C68F86063C42640651C7E9216344E4035E4446051C42640EEB7D15B17344E40D20D5E0542C4264094C8F43A18344E40CE9BD4E132C426406A15FDA119344E401F3D8F9B2BC426402DF713DF1A344E405F03C70A23C42640E4C814BD1D344E403CBD529621C42640FB5D335420344E40123EA59421C426400B4A873D23344E406310B3F226C426407461FFD027344E40AA91A7F633C42640361D01DC2C344E40F73768AF3EC426404665790D30344E4081D1408754C426401AD1877835344E4007F98F3B5BC4264049809A5A36344E40E24A87985CC42640BAF3C47336344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_fail','0102000020A2100000020000000EEC42BD2AC526400E61A17BFB334E40E24A87985CC42640BAF3C47336344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_fail',
'0102000020A210000025000000E24A87985CC42640BAF3C47336344E40573B2FBA61C426406163A8D436344E4070C0F8B369C42640E3C85E4A38344E409D746C4E6FC4264077F52A323A344E4077BAF3C473C42640BD569D303C344E40450A0A2879C42640C8FB82273E344E407AB07BE184C42640BAE2981B42344E407E75B05989C42640E341695E44344E40E5F3E56091C4264041FCB26A46344E400A3BD6D699C4264016BCE82B48344E40DEEBFF779FC426402D54A3FC49344E404C7B945BA4C4264097D3AFBE4B344E4060FB6E5FACC4264013D5B6BC4D344E4087AAF303B2C42640669C2BEF4F344E408F0C8343B9C42640F439D27451344E40E03AB5E9BEC426406A1FE16A53344E4013848659C3C42640920B845355344E40B33396FAC3C426406239F87857344E407E969D34C3C42640EA44DD6259344E403E0FA441C0C42640E9C8DB5B5B344E40ED98BA2BBBC42640E202D0285D344E401166248CB0C42640DB28571D5E344E40233031F1A2C42640476C1C565D344E40F35A649698C426408F66D1E05B344E4067E66E7C92C42640C69970F959344E40BEB4F2DC8CC42640BBF48A0258344E40A1BB24CE8AC42640C8A87C1956344E405251AB9E82C426404102902452344E40603F1FC07DC4264036D0D78750344E40F763496F6EC42640E49B6D6E4C344E40AEA29AED65C42640BC81B8614A344E40B91391065CC4264058F0918348344E400AB54BC054C426403B3CDFAA46344E409E094D124BC42640FA3B80EA44344E40D782DE1B43C42640D7B0F03F43344E4085483C8F40C426404F77F93141344E4040F09D3D3CC4264026158DB53F344E40',
1e-06);

ERROR:  XX000: SQL/MM Spatial exception - geometry crosses edge 2
LOCATION:  pg_error, lwgeom_pg.c:250

Test case 2, that works ok with same lines but in different order than case 1.

select topology.CreateTopology ('test01_ok', 4258, 1e-06);
select topology.TopoGeo_addLinestring('test01_ok','0102000020A21000001E0000000EEC42BD2AC526400E61A17BFB334E40CEF4B7A926C52640730F09DFFB334E40B08ADC781CC526406675BC13FD334E40EADB93D112C52640AD94AF15FE334E409558BED309C52640D1F4C8D5FE334E40BC4681F403C52640CAD53494FF334E409A5F28BBF4C426407BD058A002344E40D0CBCDDCE8C42640E5D6FF9405344E40CE5AC0BAE0C4264090FDE20808344E40F37B5171D2C42640643BDF4F0D344E40A58DD948C8C426408C07A57911344E40852BFB09C2C42640CCA843B813344E40CCA66D0DB6C42640DDDFEA4A15344E40B475CB69AAC426400CC0AB8A15344E40D6D127A897C42640ADA0698915344E40765BD88981C4264054104DEA15344E405C68F86063C42640651C7E9216344E4035E4446051C42640EEB7D15B17344E40D20D5E0542C4264094C8F43A18344E40CE9BD4E132C426406A15FDA119344E401F3D8F9B2BC426402DF713DF1A344E405F03C70A23C42640E4C814BD1D344E403CBD529621C42640FB5D335420344E40123EA59421C426400B4A873D23344E406310B3F226C426407461FFD027344E40AA91A7F633C42640361D01DC2C344E40F73768AF3EC426404665790D30344E4081D1408754C426401AD1877835344E4007F98F3B5BC4264049809A5A36344E40E24A87985CC42640BAF3C47336344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_ok','0102000020A2100000020000000EEC42BD2AC526400E61A17BFB334E40E24A87985CC42640BAF3C47336344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_ok','0102000020A210000019000000ACFF73982FC326404B9D369927344E400127254E38C32640C2A5BE8726344E40D77CA6A844C32640CEAF9C7326344E40D381ACA756C32640E1AAFC7C25344E401DF0AFD469C32640350BB43B24344E408C88BDAB79C32640B862354C23344E40AC7713D78CC32640D006600322344E403AAE4676A5C326402B27EB8120344E40F4A3E194B9C326401FAD7B751F344E408C73E5FDC9C32640259B61591F344E400987DEE2E1C32640F5E27ACA20344E40C64CA25EF0C32640C49A255C23344E40AA0029FBF8C32640453FBF9426344E408EE8F92E00C42640D246BFC72A344E40DF2A99AD06C426404D147C2E2E344E40E0AF13A80FC42640BDC3EDD030344E405458045A15C42640155FA39B33344E4098480E7D1CC426407F37386C36344E40A09630E422C426401894693439344E40CD4AA47E28C426408E4B66063B344E401EC18D942DC42640103EEF213C344E40C896E5EB32C426406F719EFB3C344E406D872B0C36C426409FDB95A73D344E40E6142EF53DC426404531D4BC3E344E406A6F4B3F3CC426405CB521B53F344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_ok','0102000020A210000002000000E24A87985CC42640BAF3C47336344E406A6F4B3F3CC426405CB521B53F344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_ok','0102000020A21000000200000040F09D3D3CC4264026158DB53F344E406A6F4B3F3CC426405CB521B53F344E40',1e-06);
select topology.TopoGeo_addLinestring('test01_ok','0102000020A2100000040000006A6F4B3F3CC426405CB521B53F344E40C62A4AAE07C4264090943EBE4E344E40C6CE256607C42640BF2FE4C74E344E407EBF3D74E6C3264032E0D16B58344E40',1e-06);

-- Works ok
select topology.TopoGeo_addLinestring('test01_ok',
'0102000020A210000025000000E24A87985CC42640BAF3C47336344E40573B2FBA61C426406163A8D436344E4070C0F8B369C42640E3C85E4A38344E409D746C4E6FC4264077F52A323A344E4077BAF3C473C42640BD569D303C344E40450A0A2879C42640C8FB82273E344E407AB07BE184C42640BAE2981B42344E407E75B05989C42640E341695E44344E40E5F3E56091C4264041FCB26A46344E400A3BD6D699C4264016BCE82B48344E40DEEBFF779FC426402D54A3FC49344E404C7B945BA4C4264097D3AFBE4B344E4060FB6E5FACC4264013D5B6BC4D344E4087AAF303B2C42640669C2BEF4F344E408F0C8343B9C42640F439D27451344E40E03AB5E9BEC426406A1FE16A53344E4013848659C3C42640920B845355344E40B33396FAC3C426406239F87857344E407E969D34C3C42640EA44DD6259344E403E0FA441C0C42640E9C8DB5B5B344E40ED98BA2BBBC42640E202D0285D344E401166248CB0C42640DB28571D5E344E40233031F1A2C42640476C1C565D344E40F35A649698C426408F66D1E05B344E4067E66E7C92C42640C69970F959344E40BEB4F2DC8CC42640BBF48A0258344E40A1BB24CE8AC42640C8A87C1956344E405251AB9E82C426404102902452344E40603F1FC07DC4264036D0D78750344E40F763496F6EC42640E49B6D6E4C344E40AEA29AED65C42640BC81B8614A344E40B91391065CC4264058F0918348344E400AB54BC054C426403B3CDFAA46344E409E094D124BC42640FA3B80EA44344E40D782DE1B43C42640D7B0F03F43344E4085483C8F40C426404F77F93141344E4040F09D3D3CC4264026158DB53F344E40',
1e-06);

[Lars Aksel Opsahl]

The last line is the same in both cases and that is the line that fails in case 1.

[strk]

Simplified test:

select topology.DropTopology('t4758');

select topology.CreateTopology ('t4758', 0, 1e-06);

select topology.TopoGeo_addLinestring('t4758',
'LINESTRING(
11.38327215  60.4081942,
11.3826176   60.4089484)
'); -- length: 0.0009986257269390762 (=~ 1e-3)

select topology.TopoGeo_addLinestring('t4758',
'LINESTRING(
11.3832721  60.408194249999994,
11.38327215 60.4081942)
'); -- length: 7.071067643283874e-08
    -- distance of start point from first edge: 4.9893601355070966e-09

select topology.TopoGeo_addLinestring('t4758',
'LINESTRING(
11.38330505 60.408239599999995,
11.3832721  60.408194249999994)
'); -- length:  5.6056444769047025e-05

[strk]

image of the problem

[strk]

Here's the problem: the intersection point (blue) computed between the existing edges (black) and the new line (red) gets snapped to the existing node being below tolerance.

My feeling is that the starting condition should never happen, given the tolerance, and the red node should have attracted the passing-by edge instead of leaving where it is, effectively changing the existing edge rather than creating a new one. Here order matters because if the smaller edge was inserted before, its node would have resulted in the longer edge snapping to it.

At this moment, the code tries NOT to snap existing edges to new nodes, to avoid dealing with edge collapses (you can see, in this case, that snapping the existing edge to the new node would result in a collapse).

[strk]

NOTE: passing a smaller tolerance avoids the excessive snapping and makes the operation pass.

[strk]

This patch fixes this case, although I'm afraid it would make the code more fragile, due to missing handling of collapsed edges:

diff --git a/liblwgeom/lwgeom_topo.c b/liblwgeom/lwgeom_topo.c
index 236a292fb..97b3b5aef 100644
--- a/liblwgeom/lwgeom_topo.c
+++ b/liblwgeom/lwgeom_topo.c
@@ -5351,7 +5351,7 @@ _lwt_AddLineEdge( LWT_TOPOLOGY* topo, LWLINE* edge, double tol,
     return 0; /* must be empty */
   }
   nid[0] = _lwt_AddPoint( topo, start_point,
-                          _lwt_minTolerance(lwpoint_as_lwgeom(start_point)),
+                          tol,
                           handleFaceSplit, &mm );
   lwpoint_free(start_point); /* too late if lwt_AddPoint calls lwerror */
   if ( nid[0] == -1 ) return -1; /* lwerror should have been called */

[Lars Aksel Opsahl]

Thanks for the the explanations and the patch, yes I do agree with you that is better to not change existing edges, but using your patch above works quite good thou.

The number of error was reduced to 123 cases for the test with 20 mill. edges, from 252 errors. (I now found out that the case with with 625 error was before I added the code that tries fix error by deleting and re adding edges.) This errors left does not seem to cause any information loss, since we use different methods with retry.

I have also been testing a smaller dataset with 1.5 million edges where we have also have some polygons that does have a neighbors and there we reduced the number of error from 24 to 15.

I did not see any other side effects either when I checked problem areas, but I need to more checking on this.

[strk]

Good to hear your errors reduced with the patch. Looking forward for further checking results.

[Lars Aksel Opsahl]

I used this patch on another project now and the result was accepted as good with no errors, when checked by the users who should use the result.

I have done some more checking and as far I can see this patch makes the method more robust and does not seem to have any big problem side effects.

Maybe this patch could be added to Postgis 3.1 ?

[strk]

Yes, I'll see about adding a testcase to secure the result and include the patch

[strk]

Upon trying to make the patch official I'm even less convinced about the patch. The thing is that at that point in code we're expecting the input line to have been fully noded, but this is NOT the case. This is the problem. I'm not even sure the edge should not be touched, in that vertices have more importance over lines, because vertices are what you survey, not lines, so if a measurement finds a points in a place, that's more likely to exist there. In the case above, attracting the line to the vertex would make the more sense to me. Not an easy task to deal with, as it requires implementing merge of edges…

[strk]

There's also a TODO comment in code about doing this:

  /* TODO: refactor to first add all nodes (re-snapping edges if
   * needed) and then check all edges for existing already

[Lars Aksel Opsahl]

Replying to strk:

Upon trying to make the patch official I'm even less convinced about the patch. The thing is that at that point in code we're expecting the input line to have been fully noded, but this is NOT the case. This is the problem. I'm not even sure the edge should not be touched, in that vertices have more importance over lines, because vertices are what you survey, not lines, so if a measurement finds a points in a place, that's more likely to exist there. In the case above, attracting the line to the vertex would make the more sense to me. Not an easy task to deal with, as it requires implementing merge of edges…

Is it possible to use ST_ClosestPoint in any way to help out with this ?

When adding the second line with code the below we get the blue point and not the red point close by and we can add the last without any error.

select topology.TopoGeo_addLinestring('t4758',
ST_MakeLine(
(
select ST_ClosestPoint(e.geom,p)
from t4758.edge_data e ,
ST_MakePoint(11.3832721,60.408194249999994) p
where ST_DWithin(p,e.geom,1e-06)
)
,
(
select ST_ClosestPoint(e.geom,p)
from t4758.edge_data e ,
ST_MakePoint(11.38327215,60.4081942) p
where ST_DWithin(p,e.geom,1e-06)
)
)
); -- length: 7.071067643283874e-08
    -- distance of start point from first edge: 4.9893601355070966e-09

If it's possible will it then kill the performance ?

[strk]

Performance is not of my concern in this stage, but correctness is.

Your idea boils down to basically implement "snap-to-segment", which was one idea I have been in mind for some time now. But this means NOT buying the argument of "vertices are more important than lines", do you think this is correct ?

Note that even if we snap to segments, we'll _need_ to split the first segment and the two resulting edges might slightly move anyway (due to need to represent that node). The movement should be small so hopefully won't create another collision, but this has to be kept in mind.

So, do you still think incoming vertices should snap to existing edges (not vertices) ? If so I could look into doing this.

[Lars Aksel Opsahl]

I am really unsure about what is the best to do here, since I am not able to see all the consequences, but I think "snap-to-segment" is ok because

1) We must avoid that the red point close the blue point are added when adding line two or else we we have blocked the system for the blue node, without moving an existing node.

2) We must avoid that lines/nodes already added are moved/changed. Adding a node to a line does not mean that a line is changed.

3) We run with snapto and then we must accept that incoming points are moved or adjusted to fit to data already added inside given tolerance. One used case can for instance be that we add the most accurate lines first and use bigger tolereance when adding the next lines.

4) “snap to vertex” is the best, but I don't see snapto "snap-to-segment" as problem, when there are no vertex to snap for the given tolerance. I here understand a vertex as node, where a line end or meet other lines. So the problem when adding line two this is that there are no node so we to have to create the blue node before we can snap to it.

[strk]

The affirmation "we add the most accurate lines first" is to be considered. How can a line be accurate, if not ONLY via their vertexes ? Vertexes are what you measure, not lines. Is this not the case ?

Aren't vertexes inherently always the most accurate data at our disposal ?

[Lars Aksel Opsahl]

Yes you are right that vertexes are the most accurate part, but the case I was thinking about for instance this.

• Lets say we have some polygons that show soil types and those lines are very accurate because they checked out in the field and not picked from orto photo.
• Then we have some other polygons that show ar5 but they are picked from an older orto photo. Then we may want to add this new ar5 data with a bigger tolerance so they can snap to close by soil edges. Then it's important that we do not move the soil data already added and specially if this new lines are added with a big tolerance.

[Lars Aksel Opsahl]

One problem when I describe things here is that I have not been accurate enough when I talk about lines and vertexes, I will try to be more accurate on this.

[strk]

On further analisys I think I found the culprit. The code first nodes to existing edges and AFTER THAT snaps to existing elements. When snapping, the computed intersection nodes are not considered, and thus can result in moving (snapping) those intersection nodes to near-by elements (as the case above). This should be fixed by simply doing all snapping up-front (before noding). I'll try this approach.

[strk]

Temptative fix is ready for test in ​https://git.osgeo.org/gitea/postgis/postgis/pulls/49

How does it perform with your dataset, Lars ?

[Sandro Santilli <strk@…>]

In b1a18d42/git:

Improve topology noding robustness

Avoids snapping again after noding.
Fixes #4758
Includes automated test

[Lars Aksel Opsahl]

The red is before and the green after the final fix.

[Lars Aksel Opsahl]

Great fix. Thanks, Sandro.

Status Topology Errors

This patch removed all the 'Spatial exception - geometry crosses edge' from the test where I added about 20 million edges. I also reduced other errors a lot.

Before the last fix

count |                     d_msg                     
-------+-----------------------------------------------
     9 | SQL/MM Spatial exception - non-existent edge 
     1 | Side-location conflict: new edge starts in fa
     1 | Invalid edge (no two distinct vertices exist)
    41 | SQL/MM Spatial exception - curve not simple
   122 | SQL/MM Spatial exception - geometry crosses e
(6 rows)

After the last fix

 count |                     d_msg                     
-------+-----------------------------------------------
     2 | Invalid edge (no two distinct vertices exist)
    12 | SQL/MM Spatial exception - curve not simple

I also test did test on another dataset with 1.5 mill edges and there I did not get anyTopology Exception of any kind, they where all gone.

Before we had this error list.

 count |                     d_msg                     
-------+-----------------------------------------------
     3 | SQL/MM Spatial exception - non-existent edge 
     6 | SQL/MM Spatial exception - curve not simple
     1 | SQL/MM Spatial exception - geometry crosses a
    15 | SQL/MM Spatial exception - geometry crosses e
(5 rows)

Performance

Before this patch I used around 12 hours to ad the 20 million rows and now it used around 1 hour more, but may also be related to other people also testing on this server.

Problem description

I also have made a short sum up of problem, because different people tends put different meanings in the same words, when I talk to them.

I now try to define as is used Postgis Topology where we have faces, edges and nodes.

Vertex : Any point not only nodes (before I have mixed the usage of vertex and nodes) Node : A Vertex where 2 or more edges meet . Edge : A line with a start node and end node and zero or more vertexes between Edge segment : A line with only 2 vertexes.

If we look at this case ​https://trac.osgeo.org/postgis/attachment/ticket/4758/intersection.png , the long black edge is added first.

What's important here is that when adding the next line which is the short black line, the red node can't be added where it was, because then you can never add an edge that generate a node at the blue vertex, without starting to move already exiting nodes.

Now when adding the short black line, a vertex close to blue vertex is generated. This new vertex will become a node because two edges will now meet there, when the second line is added.

This means that the long black edge is split into two edges, but for all practical purposes it still a straight line, but it's now made up of two edges and not one as it was originally.

By doing this we can add the red line without any error if we snap lower vertex to the blue node when adding the red line.

All these changes are done inside a tolerance of 1-e06.

The result before and after is here ​https://trac.osgeo.org/postgis/attachment/ticket/4758/ar5_solution_4758.png

Thanks a lot, this problem been bugging mee for many years.

[strk]

Thanks for the sum-up, but I don't think the behavior you're describing matches the current implementation as snap-to-segment was NOT implemented. The red node will be added as-is. The result should be having both the red AND the blue node, effectively having 2 nodes closer-than-tolerance.

[Sandro Santilli <strk@…>]

In 73dd48b/git:

Improve topology noding robustness

Avoids snapping again after noding.
Fixes #4758 in 3.0 branch
Includes automated test