Opened 3 years ago

Closed 3 years ago

#3401 closed defect (fixed)

ST_ModEdgeSplit makes topology invalid

Reported by: strk Owned by: strk
Priority: blocker Milestone: PostGIS 2.2.2
Component: topology Version: trunk
Keywords: 32bit, arm64, ppc64el, ​s390x Cc: esseffe

Description

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.

Change History (27)

comment:1 Changed 3 years ago by 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');

comment:2 Changed 3 years ago by strk

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

comment:3 Changed 3 years ago by robe

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

comment:4 Changed 3 years ago by strk

Thanks, it would help

comment:5 Changed 3 years ago by 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)

comment:6 Changed 3 years ago by 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?

comment:7 Changed 3 years ago by 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.

comment:8 Changed 3 years ago by 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?

comment:9 Changed 3 years ago by 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.

comment:10 Changed 3 years ago by 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
-----------------------------------------------------------------------------
Last edited 3 years ago by strk (previous) (diff)

comment:11 Changed 3 years ago by strk

Keywords: 32bit added
Priority: mediumblocker

comment:12 Changed 3 years ago by strk

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

comment:13 Changed 3 years ago by 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?

comment:14 Changed 3 years ago by 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...

comment:15 Changed 3 years ago by strk

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

comment:16 Changed 3 years ago by 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

comment:17 Changed 3 years ago by 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).

comment:18 Changed 3 years ago by 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.

comment:19 Changed 3 years ago by strk

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

comment:20 Changed 3 years ago by 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.

comment:21 Changed 3 years ago by strk

Resolution: fixed
Status: newclosed

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

Fixes #3401 including unit and regress test for it.

comment:22 Changed 3 years ago by 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 :)

comment:23 Changed 3 years ago by strk

Keywords: arm64 ppc64el ​s390x added
Milestone: PostGIS 2.2.1PostGIS 2.2.2

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

comment:24 Changed 3 years ago by strk

Resolution: fixed
Status: closedreopened

comment:25 Changed 3 years ago by 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)

comment:26 Changed 3 years ago by 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)

comment:27 Changed 3 years ago by strk

Resolution: fixed
Status: reopenedclosed

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

Note: See TracTickets for help on using tickets.