[regression] ST_CurveToLine and ST_LineToCurve are not symmetric

[mjurce]

Hi, from the version 1.5.X to 2.0 there is the difference in function behavior, especially in the st_linetocurve. I checked the code and whole part that try to build the cirucalr strings was removed.

Input geometry:

MULTICURVE((723097.524 117088.672,724308.441 117063.281),CIRCULARSTRING(724308.441 117063.281,724664.096 117359.505,725443.148 117452.604))

st_curvtoline old result:

MULTILINESTRING((723097.524 117088.672,724308.441 117063.281,724342.841215729 117105.022471112,724379.248151801 117 145.025724211,724417.57410072 117183.194387958,724457.726731918 117219.436510698,724499.609314188 117253.664781983,7 24543.120948721 117285.796742909,724588.15681218 117315.754984769,724634.608409223 117343.467335533,724682.363833886

117368.867033721,724731.308039167 117391.892889235,724781.323114189 117412.489430773,724832.288568255 117430.607039

462,724884.081621122 117446.202068396,724936.577498789 117459.236947784,724989.64973409 117469.680275461,725043.1704 7136 117477.506892534,725097.010774456 117482.697943997,725151.040937372 117485.240924154,725205.130796712 117485.12 9706743,725259.150045268 117482.364559695,725312.968545938 117476.952144492,725366.456645242 117468.905500116,725419 .485485661 117458.244011639,725443.148 117452.604))

st_curvetoline new result:

MULTILINESTRING((723097.524 117088.672,724308.441 117063.281),(724308.441 117063.281,724342.841215729 117105.022471 112,724379.248151801 117145.025724211,724417.57410072 117183.194387958,724457.726731918 117219.436510698,724499.6093 14188 117253.664781983,724543.120948721 117285.796742909,724588.15681218 117315.754984769,724634.608409223 117343.46 7335533,724682.363833886 117368.867033721,724731.308039167 117391.892889235,724781.323114189 117412.489430773,724832 .288568255 117430.607039462,724884.081621122 117446.202068396,724936.577498789 117459.236947784,724989.64973409 1174 69.68027546,725043.17047136 117477.506892533,725097.010774456 117482.697943997,725151.040937372 117485.240924154,725 205.130796712 117485.129706743,725259.150045268 117482.364559695,725312.968545938 117476.952144492,725366.456645242 117468.905500116,725419.485485661 117458.244011639,725443.148 117452.604))

Not big change.

st_linetocurve old result:

MULTICURVE((723097.524 117088.672,724308.441 117063.281),CIRCULARSTRING(724308.441 117063.281,724832.288568255 1174 30.607039462,725419.485485661 117458.244011639),(725419.485485661 117458.244011639,725443.148 117452.604))

The orginal shape is preserved with this small extra line segment.

st_linetocurve new behavior result:

MULTICURVE(COMPOUNDCURVE((723097.524 117088.672,724308.441 117063.281),CIRCULARSTRING(724308.441 117063.281,724457. 726731918 117219.436510698,724682.363833886 117368.867033721),CIRCULARSTRING(724682.363833886 117368.867033721,72498 9.64973409 117469.680275461,725366.456645242 117468.905500116),(725366.456645242 117468.905500116,725419.485485661 1 17458.244011639,725443.148 117452.604)))

Here there are 2 extra arcs.

The old behavior preserved the original shape of the geometry through conversion,the new one introduces extra arcs.

Why of this change, is possible to get also the old version of functions in newer version of postgis?

[strk]

Paul: can this be due to r8689 and around ?

[strk]

Oops, sorry for the noise, r8689 has nothing to do with curves, will need to bisect this.

Mario: I don't understand what's the input to ST_LineToCurve, because passing the output from ST_CurveToLine(your_input) to ST_LineToCurve gives me an exception in both trunk and 1.5.

The exception from trunk:

ERROR:  pta_desegmentize needs implementation for npoints < 4

The exception from 1.5:

ERROR:  getPoint4d_p: point offset out of range

The result of ST_CurveToLine in 1.5:

 MULTILINESTRING((723097.524 117088.672,724308.441 117063.281),(724308.441 117063.281,724342.841215728 117105.022471111,724379.2481518 117145.02572421,724417.574100719 117183.194387956,724457.726731915 117219.436510696,724499.609314185 117253.66478198,724543.120948718 117285.796742906,724588.156812175 117315.754984765,724634.608409218 117343.467335528,724682.36383388 117368.867033715,724731.30803916 117391.892889229,724781.323114181 117412.489430767,724832.288568246 117430.607039456,724884.081621113 117446.20206839,724936.57749878 117459.236947778,724989.649734079 117469.680275453,725043.170471349 117477.506892526,725097.010774444 117482.69794399,725151.040937359 117485.240924147,725205.130796698 117485.129706735,725259.150045253 117482.364559687,725312.968545923 117476.952144484,725366.456645225 117468.905500109,725419.485485643 117458.244011632,725443.148 117452.604))

The result of ST_CurveToLine with trunk:

 MULTILINESTRING((723097.524 117088.672,724308.441 117063.281),(724308.441 117063.281,724342.841215728 117105.022471111,724379.2481518 117145.02572421,724417.574100719 117183.194387956,724457.726731915 117219.436510696,724499.609314185 117253.66478198,724543.120948718 117285.796742906,724588.156812175 117315.754984765,724634.608409218 117343.467335528,724682.36383388 117368.867033715,724731.30803916 117391.892889229,724781.323114181 117412.489430767,724832.288568246 117430.607039456,724884.081621113 117446.20206839,724936.57749878 117459.236947778,724989.649734079 117469.680275453,725043.170471349 117477.506892526,725097.010774444 117482.69794399,725151.040937359 117485.240924147,725205.130796698 117485.129706735,725259.150045253 117482.364559687,725312.968545923 117476.952144484,725366.456645225 117468.905500109,725419.485485643 117458.244011632,725443.148 117452.604))

It would help to have a smaller input geometry still reproducing the problem.

[strk]

Note that the WKT you report as the "old result" is invalid, could you re-paste it wrapping it within three curly brackets (it's the syntax for preformatted text) ?

My results of 1.5 are specifically from 1.5.9-svn. The number of points in the result are the same (so same number of arcs). The coordinates aren't all the same, but the furthest points (hausdorff distance) are 1e-10 apart.

Difference in length of the two results is computed to be around 4e-12.

[strk]

I think I found how to interpret the reported result for 1.5.x (removing some space padding):

MULTILINESTRING((723097.524 117088.672,724308.441 117063.281,724342.841215729 117105.022471112,724379.248151801 117145.025724211,724417.57410072 117183.194387958,724457.726731918 117219.436510698,724499.609314188 117253.664781983,724543.120948721 117285.796742909,724588.15681218 117315.754984769,724634.608409223 117343.467335533,724682.363833886 117368.867033721,724731.308039167 117391.892889235,724781.323114189 117412.489430773,724832.288568255 117430.607039462,724884.081621122 117446.202068396,724936.577498789 117459.236947784,724989.64973409 117469.680275461,725043.1704 7136117477.506892534,725097.010774456 117482.697943997,725151.040937372 117485.240924154,725205.130796712 117485.129706743,725259.150045268 117482.364559695,725312.968545938 117476.952144492,725366.456645242 117468.905500116,725419.485485661 117458.244011639,725443.148 117452.604))

The reported geometry indeed has only 26 vertices while the one I obtained with 1.5.9-svn and the one with trunk (2.2) has 27 vertices. Did the behavior maybe change already in the 1.5 branch ? I'll try to obtain the 26 vertices with an older version.

[strk]

Bah, can't confirm my spaces removal was correct as it results in huge Y values. Still in need of the exact WKT for the "old" behavior, which I'm missing.

[strk]

Ok, here's the correct padding:

MULTILINESTRING((723097.524 117088.672,724308.441 117063.281,724342.841215729 117105.022471112,724379.248151801 117145.025724211,724417.57410072 117183.194387958,724457.726731918 117219.436510698,724499.609314188 117253.664781983,724543.120948721 117285.796742909,724588.15681218 117315.754984769,724634.608409223 117343.467335533,724682.363833886 117368.867033721,724731.308039167 117391.892889235,724781.323114189 117412.489430773,724832.288568255 117430.607039462,724884.081621122 117446.202068396,724936.577498789 117459.236947784,724989.64973409 117469.680275461,725043.17047136 117477.506892534,725097.010774456 117482.697943997,725151.040937372 117485.240924154,725205.130796712 117485.129706743,725259.150045268 117482.364559695,725312.968545938 117476.952144492,725366.456645242 117468.905500116,725419.485485661 117458.244011639,725443.148 117452.604))

The geometry still only has 26 vertices rather than the 27 obtained with any recent version (including 1.5.9-svn). The Hausdorff distance between the one obtained with 1.5.9 and the reported one is in the order of 1e-8 over a rough total length of 2500 units. Not a big difference.

Now, the big difference is that you _can_ covert back the 26-vertices result (old one) using ST_LineToCurve while you get an exception when you try to convert back the 27-vertices one. Looking to spot the problem. I'm still interested in knowing the exact version of postgis producing the so called "old" result.

[strk]

Spotted another, probably important, difference: the _old_ result is a multilinestring with a single element (linestring with 26 points); the _new_ result is a multilinestring with _two_ elements (linestring with 2 points + linestring with 25 points).

[strk]

The additional element (missing from the _old_ result) is the linear (non-curved) element of the input. The _old_ behavior is to merge the linear component with the curved component, the new behavior keeps them separated. Does it sound ?

[strk]

So, Olivier, Paul, Regina: do you know anything about this behavioral change ? Was it on purpose ? There's no trace of it in the manual ? Should it be considered a bug ?

[strk]

Update: PostGIS 1.5.4 also gives the 2-components result. Will wait for Mario to report which version of PostGIS returned the single-component result before proceeding (sounds like a very very old behavioral change… 1.5.4 is from May 2011)

[robe]

strk,

I think this was an accidental behavior change related to all those others I complained about such as this Issue: #2165

[strk]

This one doesn't seem to be related to ST_NumPoints. Actually, I believe a MULTICURVE is indeed a collection and as such should really be threated the new way, not the old one. Irreversibility of the segmentization could be an unfortunate side-effect (could probabily be fixed by returning a collection of curves and lines)

[strk]

See also #2410 for another 1.5 → 2.0 behavioral change

[strk]

I couldn't find any version of PostGIS that was able to given an answer to this query:

select st_linetocurve(st_curvetoline('MULTICURVE((723097.524 117088.672,724308.441 117063.281),CIRCULARSTRING(724308.441 117063.281,724664.096 117359.505,725443.148 117452.604))'));

Tried from 1.5.3 up to 2.2.0, all versions raise an exception.

But passing the result of ST_CurveToLine to an ST_LineMerge make them able to given an answer, and indeed 1.5 answer is half the length of 2.0 answer. Was LineMerge the missing bit ?

ST_LineMerge(ST_CurveToLine(g)) returns a single linestring of 26 points with a total length of 2479 units in all versions from 1.5 to 2.2 now, so maybe the problem is _only_ in the ST_LineToCurve function. The input to ST_LineToCurve:

LINESTRING(723097.524 117088.672,724308.441 117063.281,724342.841215728 117105.022471111,724379.2481518 117145.02572421,724417.574100719 117183.194387956,724457.726731915 117219.436510696,724499.609314185 117253.66478198,724543.120948718 117285.796742906,724588.156812175 117315.754984765,724634.608409218 117343.467335528,724682.36383388 117368.867033715,724731.30803916 117391.892889229,724781.323114181 117412.489430767,724832.288568246 117430.607039456,724884.081621113 117446.20206839,724936.57749878 117459.236947778,724989.649734079 117469.680275453,725043.170471349 117477.506892526,725097.010774444 117482.69794399,725151.040937359 117485.240924147,725205.130796698 117485.129706735,725259.150045253 117482.364559687,725312.968545923 117476.952144484,725366.456645225 117468.905500109,725419.485485643 117458.244011632,725443.148 117452.604)

Turning the above to a curve in 1.5 returns a 7 points curve, in 2.0 and 2.2 returns a 28 points curve

I updated the ticket summary to only mention ST_LineToCurve

[strk]

Paul: it looks like you've been the actor of the refactoring introducing this change. I'm looking at r8948 as the version that removed the "append_segment" function and added the pt_continues_arc one. Any idea about this behavioral change ?

[strk]

I seem to understand that the algorithm in 1.5 used to compare angles between consecutive points while the algorithm in 2.0.x and up compares the distance from circle center. The tolerance used is the same but evidently the distance calculation introduces more error than the angle one, which results in not considering all of the curve points equidistant from the center. We're talking about an hard-coded tolerance of 1e-8. I guess we'd want this tolerance to possibly be specifiable by the user, btw.

[strk]

It takes a tolerance of 3e-7 for this case to be considered a curve.

[strk]

I changed the summary again because I think the real problem here is being unable to go from curve to line and back to curve in a consistent way. This is a regression because there are known case in which 1.5.x succeeded in doing it.

Here's an example small test input:

CIRCULARSTRING(718006.92 114480.27, 718006.381 114478.609, 718004.78 114477.91)

Passing the above to ST_CurveToLine and then to ST_LineToCurve produces a COMPOUNDCURVE in 1.5 and a LINESTRING (the _same_ linestring generated by ST_CurveToLine) in 2.0.

The 1.5 final output (curve):

 COMPOUNDCURVE(CIRCULARSTRING(718006.92 114480.27,718006.396201402 114478.625952602,718004.826280993 114477.909987011),(718004.826280993 114477.909987011,718004.78 114477.91))

[strk]

I shall note that translating the input curve to the origin fixes the 2.0 round-trip behavior, pushing this bug in the class of "precision/robustness" issues.

The offsetting query:

WITH 
-- The offending input geometry
inp AS ( SELECT '
CIRCULARSTRING(718006.92 114480.27, 718006.381 114478.609, 718004.78 114477.91)
'::geometry as g
),
-- The smallest ordinate values (offset)
off AS (
  SELECT ST_XMin(g) as x, ST_YMin(g) as y from  inp
)
SELECT ST_AsText(ST_Translate(ST_LineToCurve(ST_CurveToLine(ST_Translate(g,-off.x,-off.y))), off.x,off.y))
FROM inp, off;

Gives the very good result:

 CIRCULARSTRING(718006.92 114480.27,718006.396205029 114478.625955407,718004.78 114477.91)

The biggest error (computed by linearizing the curves again and computing max distance between any vertices of the two geometries) is around 2e-06 units. Sounds very good to me!

We should maybe simply "tweak" the tolerance used by the curve detector based on the magnitude of the ordinate values. The floating point grid is of irregular size, can't use the same tolerance when working with arcs near the origin or 10^{6 away from it…}

[pramsey]

I haven't looked at this case in detail, but I'd just note for the record that the 1.5 code was full of different failure cases, and the 2.0 code is vastly better both in simplicity and in non-trivial case coverage. So no changing back

[strk]

We don't necessarely need to fully revert to the old behavior, but some of the approaches should probably get back, like checking angle between arc segments. See #2423 for a clear such case.

It would help to have a more comprehensive testsuite for curves. I've only found 4 _disabled_ tests for ST_LineToCurve in regress/sql-mm-circularstring.sql

[pramsey]

I would tend to close those out. The behaviour ain't perfect, but it ain't killing anyone.

[robe]

Milestone renamed