ST_ModEdgeSplit makes topology invalid

[strk]

It has been reported by Alessandro Furieri (esseffe) that the following snippet creates an invalid topology on a 32bit Windows machine.

It has to be tested for confirmation on both windows and other 32bit systems.

The snippet:

SELECT CreateTopology('topotest', 0, 0, 0);
SELECT ST_AddIsoNode('topotest', 0, ST_MakePoint(-180, 0));
SELECT ST_AddIsoNode('topotest', 0, ST_MakePoint(0, 0));
SELECT ST_AddIsoEdge('topotest', 1, 2, 'LINESTRING(-180 0, 0 0)'::geometry);
SELECT ST_ModEdgeSplit('topotest', 1, MakePoint(-20, 0));

In order to test topology validity:

SELECT * FROM ValidateTopology('topotest');

While the topology is valid the ValidateTopology call should return no rows. Ideally it would be called before and after the ST_ModEdgeSplit call.

The report is based on current TRUNK version of liblwgeom.

[strk]

The updated test (with correct syntax):

SELECT CreateTopology('topotest');
SELECT ST_AddIsoNode('topotest', 0, ST_MakePoint(-180, 0)); 
SELECT ST_AddIsoNode('topotest', 0, ST_MakePoint(0, 0));
SELECT ST_AddIsoEdge('topotest', 1, 2, 'LINESTRING(-180 0, 0 0)'::geometry);
SELECT 'before', * FROM ValidateTopology('topotest');
SELECT ST_ModEdgeSplit('topotest', 1, ST_MakePoint(-20, 0));
SELECT 'after', * FROM ValidateTopology('topotest');

[strk]

Robe does winnie still build the "winnie" branch if I push tests there ?

[robe]

Not at moment but I can turn that job back on.

[strk]

Thanks, it would help

[strk]

Regina can you please let me know when winnie is setup to automatically test whatever is pushed to the "travis" branch on github.com or gitlab.com ? (you pick one)

[robe]

I have it setup against github.com winnie. Just manually triggered it now to make sure I didn't miss anything. It's only test 9.4. You want me to change it to a matrix to test all versions of PostgreSQL?

[strk]

Sorry I meant "winnie" branch, anyway, it's not a problem what the branch name is, just tell me what's enabled and I'll push there. PostgreSQL should not matter.

[robe]

Yah winnie branch was what I was talking about. I'm still struggling getting this to work again. Might take me a bit. Do you want to reset the repo? Or you wanna work with what's there already?

[robe]

As mentioned on IRC, I think I've resolved issues so winnie branch is good but only testing against 9.4 at the moment.

[strk]

I noticed winnie is only testing 64bit, do you confirm ? The bug was reported on 32bit instead. I've actually setup a virtual machine with a 32bit ubuntu 12.04 and can reproduce the problem:

-----------------------------------------------------------------------------
--- regress/st_modedgesplit_expected    2016-01-05 00:50:37.011051686 +0100
+++ /tmp/pgis_reg/test_1_out    2016-01-05 01:06:38.883010813 +0100
@@ -47,4 +47,6 @@
 t3401.N2|2
 t3401.L1|1
 t3401.split|3
+t3401.valid_after|edge start node geometry mis-match|2|3
+t3401.valid_after|edge end node geometry mis-match|1|3
 t3401.end|Topology 'bug3401' dropped
-----------------------------------------------------------------------------

[strk]

According to Alessandro ST_Split slightly moves the X ordinate of the cutter point

[nicklas]

strk

Quite long time ago there was some issue, and if I recall right it was about st_split, that was caused by the way the distance functions work.

Because distance functions use the same algorithms as st_closestpoint it calculates a point on a line that is truncated to double precision. Then the distance is calculated to that point.

That approach can give a slightly different distance than calculating the distance directly and truncating the distance itself to double precision.

Can this be the same issue?

[strk]

Here, test with only ST_Split:

=# with inp as ( SELECT 'LINESTRING(-180 0,0 0)'::geometry a, 'POINT(-20 0)'::geometry b ), op as ( select a,b,st_split(a,b) s from inp ), dumped as ( select a,b,(st_dumppoints(s)).* from op ) select path, st_astext(geom) endpoint, st_astext(b) split, st_equals(geom,b), st_contains(a,b) from dumped;
 path  |   endpoint    |    split     | st_equals | st_contains 
-------+---------------+--------------+-----------+-------------
 {1,1} | POINT(-180 0) | POINT(-20 0) | f         | t
 {1,2} | POINT(-20 0)  | POINT(-20 0) | f         | t
 {2,1} | POINT(-20 0)  | POINT(-20 0) | f         | t
 {2,2} | POINT(0 0)    | POINT(-20 0) | f         | t
(4 rows)

None of the endpoints of the split output equal the split point, although the split point is contained in the originally splitted line…

[strk]

This case is similar to the one in #2173, that is using ptarray_substring and "location" looses tolerance

[strk]

In other words, a point contained in a line does not yeld itself when its location is interpolated on the line:

$ with inp as ( SELECT 'LINESTRING(-180 0,0 0)'::geometry a, 'POINT(-20 0)'::geometry b ),
op as ( select a, b, ST_LineInterpolatePoint(a,ST_LineLocatePoint(a,b)) rt from inp )
select ST_AsText(a) a, ST_AsText(b) b, ST_AsText(rt), ST_Distance(b, rt), ST_Equals(b, rt) from op;
-[ RECORD 1 ]-----------------------
a           | LINESTRING(-180 0,0 0)
b           | POINT(-20 0)
st_astext   | POINT(-20 0)
st_distance | 7.105427357601e-15
st_equals   | f

[strk]

Nicklas botton line is the roundtrip locate/interpolate doesn't yeld the original point. It would be normal if the original point was NOT on the line, but it isn't if the original point _is_ on the line.

As long as the "location" is expressed as the fraction of total length the point is found at there will always be a truncation issue. I'm not sure this can be solved w/out changing how "location" is expressed (or completely avoiding to use locate/interpolate from ST_Split).

[nicklas]

From you example above, is this a truncate issue?

We have had something similar somewhere about 32 bit not behaving well with 64 bit values. But I cannot remember what the situation was.

But if I remember right you or Paul solved that one with changing something like round to lround or something like that. Could it be some corresponding thing here?

As you hear I have no clue, but something is ringing in my head.

[strk]

For now I'm working on a change that completely avoids using locate/interpolate from ST_Split.

[strk]

(In [14549]) Rewrite code to split a line by a (multi)point to improve robustness

References #3401 for 2.2 branch. Includes unit and regress test.

[strk]

(In [14550]) Rewrite code to split a line by a (multi)point to improve robustness

Fixes #3401 including unit and regress test for it.

[strk]

So we have this fixed in 2.2 branch (for 2.2.1) with r14549 and in trunk (for 2.3.0) with r14550. The split code was rewritten to avoid locate/interpolate and should also be somewhat faster now (not tested/profiled).

Alessandro your confirmation of the fix on your side would be welcome

[strk]

While the fix was good for 32bit systems, it's still not enough for other architectures: see #3422

[strk]

(In [14594]) Avoid any drift of cutter point on lines split

Should fix splitting operations on at least arm64, ppc64el and s390x. See #3422 and #3401

Also turn ASSERT_DOUBLE_EQUAL back to a tolerance-free check (better use a different name for tolerance-aware check, so caller can decide)

[strk]

(In [14595]) Avoid any drift of cutter point on lines split

Should fix splitting operations on at least arm64, ppc64el and s390x. See #3422 and #3401 (for 2.2 branch)

Also turn ASSERT_DOUBLE_EQUAL back to a tolerance-free check (better use a different name for tolerance-aware check, so caller can decide)

[strk]

Should now be fine as of r14595 in 2.2 branch (2.2.2) and r14594 in trunk (2.3.0).