Topology population regression

[strk]

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)

[strk]

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

[strk]

overview of topo created by 2.1.9

[strk]

That "shared" edge between the 3 polygons, does not seem to be really equal…

[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+

[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).

[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                   

[strk]

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

[strk]

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

[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

[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.

[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)

[strk]

empirically find min tolerance

[strk]

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

[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 …

[aperi2007]

image-before-intersection

[aperi2007]

package reduce to produce the intersection issue

[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:

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

[aperi2007]

image-after-intersection

[strk]

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)