Opened 4 years ago

Closed 4 years ago

#3329 closed defect (fixed)

Topology population regression

Reported by: strk Owned by: strk
Priority: blocker Milestone: PostGIS 2.2.1
Component: topology Version: 2.2.x
Keywords: Cc: esseffe, aperi2007

Description

Another regression spotted between plpgsql and C version of topology loading. I'm attaching the smallest input found so far, can probably be further reduced. Thanks @esseffe for finding this out.

To reproduce the error:

strk=# select createtopology('rer_exception');
 createtopology
----------------
           2650
(1 row)


strk=# select topogeo_addpolygon('rer_exception', st_geometryn(geom, 1)) from rer_exception order by gid;
ERROR:  SQL/MM Spatial exception - geometry crosses edge 58

Switching to the plpgsql version works and returns 60 faces (with a few duplicates and a null, which isn't really expected):

ALTER EXTENSION
strk=# select topogeo_addpolygon('rer_exception', st_geometryn(geom, 1)) from rer_exception order by gid;
 topogeo_addpolygon
--------------------
                 71
                 84
                 71
                 72
                 74
                 76
                 78
                 80
                 82
                 86
                 89
                 91
                 93
                 95
                 96
                 97
                 99
                 87
                 76
                 80
                 88
                 90
                 89
                 92
                 99
                 71
                 73
                100
                107
                106
                 77
                 81
                110
                 78
                115

                 71
                 73
                100
                107
                106
                 77
                 81
                110
                 78
                115
                117
                 84
                 82
                 83
                119
                 86
                126
                125
                130
                 94
                131
                 93
                136
                 91
                 96
                138
                 97
                142
                146
                148
                149
                151
                 98
                 95
                141
(60 rows)

Attachments (7)

rer_exception.zip (15.7 KB) - added by strk 4 years ago.
initial test, 3 polygons with 12, 88 and 988 vertices each
rer_err.png (39.0 KB) - added by strk 4 years ago.
rer_topo_spaghetti.png (60.7 KB) - added by strk 4 years ago.
overview of topo created by 2.1.9
smallertolerance.patch (944 bytes) - added by strk 4 years ago.
empirically find min tolerance
img-ante.gif (5.7 KB) - added by aperi2007 4 years ago.
image-before-intersection
issue_topology_intersection.zip (36.8 KB) - added by aperi2007 4 years ago.
package reduce to produce the intersection issue
img-post.gif (9.9 KB) - added by aperi2007 4 years ago.
image-after-intersection

Download all attachments as: .zip

Change History (23)

Changed 4 years ago by strk

Attachment: rer_exception.zip added

initial test, 3 polygons with 12, 88 and 988 vertices each

Changed 4 years ago by strk

Attachment: rer_err.png added

comment:1 Changed 4 years ago by strk

Changed 4 years ago by strk

Attachment: rer_topo_spaghetti.png added

overview of topo created by 2.1.9

comment:2 Changed 4 years ago by strk

That "shared" edge between the 3 polygons, does not seem to be really equal... overview of topo created by 2.1.9

comment:3 Changed 4 years ago by strk

The topology summary, to get an idea:

strk=# select topologysummary('rer_exception');
                    topologysummary                     
--------------------------------------------------------
 Topology rer_exception (id 2650, SRID 0, precision 0) +
 90 nodes, 174 edges, 85 faces, 0 topogeoms in 0 layers+

comment:4 Changed 4 years ago by strk

The _ST_Mintolerance function returns around 1.79e-08 for the three inputs. Using a smaller tolerance (1e-08) makes the trunk version succeed (returning 91 rows).

comment:5 Changed 4 years ago by strk

I think the difference here is only between a slightly different values of tolerance computed by the plpgsql version and the C version.

For example, the tolerance for the first polygon is:

1.78950816000000e-08 in 2.2
1.78950805740752e-08 in 2.1                   

comment:6 Changed 4 years ago by strk

I confirm that reducing the auto-computed tolerance in 2.2 fixes the import.

comment:7 Changed 4 years ago by strk

I noticed my liblwgeom is built with -fexcess-precision=standard, now I wonder if that would change the computation of minimal tolerance...

comment:8 Changed 4 years ago by strk

Adding code to test the computed tolerance shows that what is computed is anyway bigger than it needs be, for example:

psql:load.sql:4: NOTICE:  computed minTolerance: 1.78950811259422e-08
psql:load.sql:4: NOTICE:   minTolerance 8.94754056297112e-09 is also good
psql:load.sql:4: NOTICE:   minTolerance 4.47377028148556e-09 is also good
psql:load.sql:4: NOTICE:   minTolerance 2.23688514074278e-09 is also good
psql:load.sql:4: NOTICE:   minTolerance 1.11844257037139e-09 is also good
psql:load.sql:4: NOTICE:   minTolerance 5.59221285185695e-10 is also good
psql:load.sql:4: NOTICE:   final minTolerance: 5.59221285185695e-10

comment:9 Changed 4 years ago by strk

For "it needs be" I mean that comparing the number of interest (max ordinate value) with the same value minus or plus the tolerance finds them different.

comment:10 Changed 4 years ago by strk

Changing the min tolerance computation to use this method (halving tolerance while still good) changes behaviour with some of the cases in regress/topogeo_addlinestring, but doesn't introduce any load failure there. I think it would make sense to get "min tolerance" correctly, somehow (still a research matter)

Changed 4 years ago by strk

Attachment: smallertolerance.patch added

empirically find min tolerance

comment:11 Changed 4 years ago by strk

It looks there's a GNU library specifically for getting this right: http://www.mpfr.org/

comment:12 Changed 4 years ago by strk

Just to get a feel of what does it take: https://gforge.inria.fr/scm/viewvc.php/mpfr/branches/3.1/src/next.c?revision=9403&view=markup&pathrev=9605#l27

And this is half of the story (next-to-zero). There's a next-to-infinite too ...

Changed 4 years ago by aperi2007

Attachment: img-ante.gif added

image-before-intersection

Changed 4 years ago by aperi2007

package reduce to produce the intersection issue

comment:13 Changed 4 years ago by aperi2007

Hi strk, I add a new packege with a really reduced dataset to produce the intersection issue.

Also an image to explain the question:

image-before-intersection

The topology has the two edge 58 and 59 loaded. Has you can notice the edge 58 is at right of the 59 edge. Also you can notice the new line to add to the topology (red line) is at left side.

The procedure find before the 58 edge and try to link the new line (red) to the 58 edge and this trigger the intersection with the 59 edge.

ut perhaps thre is more. Infact say-ing that the 58 edge is find before the 59 edge could be not sufficient to explain why it is choose. Infact I remenber that in the core of geos some year ago was done an enhancement to allow the geos snap to find the nearest feature not only the first feature under the snap limit.

(see the geos ticket https://trac.osgeo.org/geos/ticket/501)

If this code is still in geos and active (and is used in this procedure) the explanation is not only that the 58 edge is found before the 59 edge but instead is that the 58 edge has a vertex nearest to the newline (red) rather than the 59 edge.

The image show this kind of use-case, as you can see the vertex (blue) of the 58 edge is near to the red line rather than the two vertex s of the 59 edge.

This could explain why the procedure choose the 58 edge instead of the 59 edge and to so the intersection fail.

regards.

Andrea.

If this enhancemente for snap geos is still in geos core the explanation to why

Changed 4 years ago by aperi2007

Attachment: img-post.gif added

image-after-intersection

comment:14 Changed 4 years ago by aperi2007

image-after-intersection

comment:15 Changed 4 years ago by aperi2007

Cc: aperi2007 added

comment:16 Changed 4 years ago by strk

Resolution: fixed
Status: newclosed

I found out this was a bug in r14155, which was the C version of the fix for #3280. The code adding a point was not snapping the closest edge (59, in Andrea snapshot) because a point projected on it was not found to be _contained_ by it. 2.2.0 is affected, 2.1.9dev is not.

r14251 in trunk (2.3.0dev), r14252 in 2.2 branch (2.2.1dev)

Note: See TracTickets for help on using tickets.