Opened 7 months ago

Last modified 6 weeks ago

## #5722 new defect

# Spatial exception - geometry boundary touches interior of edge 4 (XX000)

Reported by: | strk | Owned by: | strk |
---|---|---|---|

Priority: | medium | Milestone: | PostGIS 3.6.0 |

Component: | topology | Version: | master |

Keywords: | robustness | Cc: |

## Description

Repro:

Prepare:

SELECT topology.DropTopology ('topo'); SELECT topology.TopoGeo_AddLineString ('topo', 'LINESTRING( -11.968112622212203 0.651457829865329, 8.13909499443551 0.334122751124234, -11.964143711257549 0.31568377154268)');

Fail:

SELECT topology.TopoGeo_AddLineString ('topo', 'LINESTRING( -0.65145782986533 -11.968112622212203, -0.159231454672685 8.13973141470126)');

What happens in this case is that the intersection point computed by GEOS is further than the minimum computed tolerance for the point so when PostGIS Topology adds the point it fails to snap/split the existing edge on which the intersection point was computed, thus creating an isolated node and finding an intersection between that aforementioned edge and the incoming edge upon adding it.

The exception is thrown in the master branch. I didn't try what happens in the 3.4 branch but chances are an invalid topology is created instead.

### Attachments (1)

### Change History (21)

### comment:1 by , 7 months ago

### comment:5 by , 6 months ago

Work continues in https://git.osgeo.org/gitea/postgis/postgis/pulls/202

What we would need here is a way to tell how much the GEOS input lines were moved to snap to detected intersection points. I don't think such information is currently available even at the C++ level.

Alternatively we should compute intersection points on the PostGIS side, analyzing segment by segment and snapping each in turn if needed.

### by , 6 months ago

Attachment: |
screen01.png
added |
---|

### comment:6 by , 6 months ago

New analisys: upon adding the vertical line GEOS correctly computes nodes but PostGIS is unable to tell that the node falls on the edge. Logs:

[topo/lwgeom_topo.c:_lwt_AddPoint:6536] Adding point: POINT(-0.350498072243138 0.326335974301659) [topo/lwgeom_topo.c:_lwt_AddPoint:6612] New point is within 1.26179306007529e-15 units of 0 edges [topo/lwgeom_topo.c:lwt_GetFaceContainingPoint:7479] Closest segment on edge 2 is 1 (dist 8.28391e-18) DEBUG: [topo/lwgeom_topo.c:lwt_GetFaceContainingPoint:7482] Closest segment on edge 2 is LINESTRING(8.13909 0.334123, -11.9641 0.315684)

What the logs say is a contradiction:

- The point is NOT within 1.24e-15 units from the edge
- The point is at 8.28e-18 distance from the edge

Either 1 or 2 is true, cannot both be true.

- _lwt_AddPoint (1) uses ST_DWithin to find edges within distance, which gives the wrong answer, in this case.
- lwt_GetFaceContainingPoint (2) uses the ↔ operator to find the closest edge and ptarray_closest_segment_2d to compute the distance.

### comment:7 by , 6 months ago

I'm not sure how 8.28391e-18 comes out from but ST_Distance seems to give `1.8318679906315083e-15`

which is still bigger than the computed tolerance of `1.26179306007529e-15`

:

postgis_reg=# select edge_id, ST_Distance(geom, '0101000000C11966778F6ED6BF27924848B0E2D43F') dist, ST_DWithin(geom, '0101000000C11966778F6ED6BF27924848B0E2D43F', 1.26179306007529e-15) from t opo.edge where edge_id = 2; edge_id | dist | st_dwithin ---------+------------------------+------------ 2 | 1.8318679906315083e-15 | f

In any case the intersection point computed by GEOS is found to be further than the computed min tolerance.

### comment:8 by , 6 months ago

So the bottom line problem for PostGIS is to find out which existing edges need to be snapped to the new node. At the moment the code just assumes the maximum drift of an edge can be computed based on the floating point grid. That's where the computed tolerance comes from. I'm pretty sure GEOS uses a different "tolerance" internally, and it would be helpful to extrapolate it externally, or inject it from outside in, using the GEOS-3.9 backed functions for fixed-precision overlay.

### comment:9 by , 6 months ago

For the record: current minimum GEOS version is 3.8 so not enough to guarantee fixed-precision overlay support

### comment:10 by , 6 months ago

winnie is complaining about this now, did you put a test in place for this?

https://winnie.postgis.net/job/PostGIS_EDB_Regress_winnie/18898/consoleFull

PostgreSQL 15.6, compiled by Visual C++ build 1937, 64-bit Postgis 3.5.0dev - (3.4.0rc1-1104-gfd3a41f8d) - 2024-05-06 06:18:42 scripts 3.5.0dev 3.4.0rc1-1104-gfd3a41f8d raster scripts 3.5.0dev 3.4.0rc1-1104-gfd3a41f8d GEOS: 3.13.0dev-CAPI-1.18.0 PROJ: 8.2.1 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org USER_WRITABLE_DIRECTORY=C:\Users\Administrator\AppData\Local/proj DATABASE_PATH=e:\jenkins\proj\rel-proj-8.2.1w64gcc81\share\proj\proj.db SFCGAL: 1.5.1 GDAL: GDAL 3.8.5, released 2024/04/02 ./topology/test/regress/topogeo_addlinestring .. failed (diff expected obtained: /projects/postgis/tmp/3.5.0dev_pg15_geos3.13_gdal3.8.5w64/test_228_diff) ----------------------------------------------------------------------------- --- ./topology/test/regress/topogeo_addlinestring_expected 2024-04-30 15:13:51.239393800 -0400 +++ /projects/postgis/tmp/3.5.0dev_pg15_geos3.13_gdal3.8.5w64/test_228_out 2024-05-06 03:27:40.668553000 -0400 @@ -171,8 +171,7 @@ t3280.start|t t3280|L11 t3280|L22 -t3280|L1b1 -t3280|L1b2 +ERROR: Spatial exception - geometry intersects edge 2 t3280.end|Topology 'bug3280' dropped t3380.start|t t3380.L1|1 ----------------------------------------------------------------------------- ./topology/test/regress/topogeo_addlinestring_robust .. failed (diff expected obtained: /projects/postgis/tmp/3.5.0dev_pg15_geos3.13_gdal3.8.5w64/test_229_diff) ----------------------------------------------------------------------------- --- ./topology/test/regress/topogeo_addlinestring_robust_expected 2024-04-30 15:13:51.265763100 -0400 +++ /projects/postgis/tmp/3.5.0dev_pg15_geos3.13_gdal3.8.5w64/test_229_out 2024-05-06 03:29:00.619283800 -0400 @@ -1,2 +1,4 @@ #5699|-checking- +#5699|addline exception|Spatial exception - geometry intersects edge 3 (XX000) #5711|-checking- +#5711|addline exception|Spatial exception - geometry intersects edge 3 (XX000) -----------------------------------------------------------------------------

### comment:11 by , 6 months ago

hmm I thought winnie was running with latest geos, but looks like the hook isn't working, so her last build was like a month ago. https://winnie.postgis.net/view/GEOS/job/GEOS_Master/

Going to force a rebuild to see if it fixes this issue.

### comment:12 by , 6 months ago

topogeo_addlinestring is not any recent, topogeo_addlinestring_robust is recent

I guess the floating point grid on 32bit is different

### comment:13 by , 6 months ago

Interesting fact: the test for this case succeeds with GEOS-3.8 (before OverlayNG)

### comment:14 by , 6 months ago

Confirmed. Building PostGIS against GEOS-3.8 and then installing/uninstalling GEOS from the main branch shows the difference:

$ regress/run_test.pl --nodrop --topology -v topology/test/regress PostgreSQL 15.6 (Debian 15.6-0+deb12u1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 12.2.0-14) 12.2.0, 64-bit Postgis 3.5.0dev - (3.4.0rc1-1104-gfd3a41f8d) - 2024-05-07 06:58:49 GEOS: 3.13.0dev-CAPI-1.19.0 Running tests topology/test/regress/topogeo_addlinestring_robust .. failed (diff expected obtained: /tmp/pgis_reg/test_1_diff) ----------------------------------------------------------------------------- --- topology/test/regress/topogeo_addlinestring_robust_expected 2024-05-07 09:01:54.377226450 +0200 +++ /tmp/pgis_reg/test_1_out 2024-05-07 09:03:58.072220001 +0200 @@ -1,3 +1,4 @@ #5699|-checking- #5711|-checking- #5722|-checking- +#5722|addline exception|Spatial exception - geometry boundary touches interior of edge 4 (XX000) ----------------------------------------------------------------------------- Run tests: 1 Failed: 1

$ regress/run_test.pl --nodrop --topology -v topology/test/regress PostgreSQL 15.6 (Debian 15.6-0+deb12u1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 12.2.0-14) 12.2.0, 64-bit Postgis 3.5.0dev - (3.4.0rc1-1104-gfd3a41f8d) - 2024-05-07 06:58:49 GEOS: 3.8.4-CAPI-1.13.5 Running tests topology/test/regress/topogeo_addlinestring_robust .. ok in 195 ms Run tests: 1 Failed: 0

### follow-up: 17 comment:16 by , 6 months ago

It's hard to tell who's right and who's wrong between GEOS-3.8 and GEOS-3.12 because the error could also be in a false negative validity detection too. Comparing logs when run against 3.8 and 3.12:

3.8: [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:700] Edge 4 relate pattern is FF1F00102 3.12: [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:700] Edge 4 relate pattern is F01F001F2

This is what is reported here: https://github.com/libgeos/geos/issues/1064#issuecomment-2097689307

### comment:17 by , 6 months ago

Replying to strk:

It's hard to tell who's right and who's wrong between GEOS-3.8 and GEOS-3.12 because the error could also be in a false negative validity detection too.

GEOS 3.12 (and some earlier versions) has the best available `Orientation`

algorithm (for testing line-line intersection) that we have found so far. This test reports that the endpoints of B lie on opposite sides of Line A, and vice-versa. So Line B does intersect Line, in their interiors. This means that the relate matrix computed by 3.12 is correct (as best we can tell).

This is a good example of why to get fully valid noding a snap-rounding approach with a distance tolerance needs to be used.

### comment:18 by , 6 months ago

I confirm GEOS-3.8 "succeeds" only because it does not notice the interior-interior intersection. I tested this by using GEOS-3.8 to build the topology. The so-built topology validates fine with GEOS-3.8. Then I upgraded to GEOS-3.12 and ONLY run the topology validation, which told me the topology was invalid !

I am aware that we need to snap-round existing edges. The current problem with this ticket is finding out what a proper "distance tolerance" is. My current guess is that GEOS is internally computing such "distance tolerance" and it does not match the one computed by PostGIS Topology.

### comment:19 by , 8 weeks ago

Milestone: | PostGIS 3.5.0 → PostGIS 3.6.0 |
---|

### comment:20 by , 6 weeks ago

Keywords: | robustness added |
---|

**Note:**See TracTickets for help on using tickets.

Confirmed: in 3.4 branch the line is added but an invalidity is created: edge crosses edge|4|5