CGAL failed to create straightSkeleton

[StyXman]

Another issue, similar to #111. I simplified the polygon using this code:

https://gist.github.com/StyXman/174df434435529fb73e8edc014ea52ac

I got down to a 14-node Polygon:

POLYGON ((4.6496243000000002 43.5206941000000000, 4.6525242999999996 43.5138711000000029, 4.6538323000000004 43.5135961000000009, 4.6575601000000004 43.5140630000000002, 4.6610893000000004 43.5289111000000020, 4.6611813000000000 43.5289641000000032, 4.6613262999999998 43.5290541000000033, 4.6616742999999996 43.5292700999999980, 4.6662613000000004 43.5319630999999987, 4.6694462999999997 43.5364300999999969, 4.6773002999999997 43.5426701000000023, 4.6773223000000002 43.5500510999999975, 4.6770063000000004 43.5516341000000011, 4.6727913000000001 43.5583450999999968, 4.6499202999999998 43.5215560999999980, 4.6496243000000002 43.5206941000000000))

This is the tests I did on it:

gis=> select ST_StraightSkeleton ('POLYGON ((4.6496243000000002 43.5206941000000000, 4.6525242999999996 43.5138711000000029, 4.6538323000000004 43.5135961000000009, 4.6575601000000004 43.5140630000000002, 4.6610893000000004 43.5289111000000020, 4.6611813000000000 43.5289641000000032, 4.6613262999999998 43.5290541000000033, 4.6616742999999996 43.5292700999999980, 4.6662613000000004 43.5319630999999987, 4.6694462999999997 43.5364300999999969, 4.6773002999999997 43.5426701000000023, 4.6773223000000002 43.5500510999999975, 4.6770063000000004 43.5516341000000011, 4.6727913000000001 43.5583450999999968, 4.6499202999999998 43.5215560999999980, 4.6496243000000002 43.5206941000000000))');
NOTICE:  During straight_skeleton(A) :
NOTICE:    with A: POLYGON((5235011566223201/1125899906842624 3062496589557271/70368744177664,1309569168988261/281474976710656 3062016463615747/70368744177664,5239749353031195/1125899906842624 1530998556105549/35184372088832,5243946482703923/1125899906842624 61240
ERROR:  CGAL failed to create straightSkeleton

And according to GEOS (python-shapely uses it internally), the polygon is valid:

In [1]: import shapely.wkt
In [2]: sh= shapely.wkt.loads ('POLYGON ((4.6496243000000002 43.5206941000000000, 4.6525242999999996 43.5138711000000029, 4.6538323000000004 43.5135961000000009, 4.6575601000000004 43.5140630000000002, 4.6610893000000004 43.5289111000000020, 4.6611813000000000 43.5289641000000032, 4.6613262999999998 43.5290541000000033, 4.6616742999999996 43.5292700999999980, 4.6662613000000004 43.5319630999999987, 4.6694462999999997 43.5364300999999969, 4.6773002999999997 43.5426701000000023, 4.6773223000000002 43.5500510999999975, 4.6770063000000004 43.5516341000000011, 4.6727913000000001 43.5583450999999968, 4.6499202999999998 43.5215560999999980, 4.6496243000000002 43.5206941000000000))')
In [3]: sh.is_valid
Out[3]: True

I hope the test case is ok, I'm not really convinced my simplification algorithm makes sense.

[Entara]

i also have some problems using straight skeleton crashing for some of my test geometries.
the funny thing is sometimes it works if i use other coordinate systems (st_transform before and after st_straightskeleton) :
select st_transform(st_straightskeleton( st_transform(poly, xxxx)), yyyyy);
for all of my test geometries srid 900913 works like a charm. i tried with srid 4258 and st_straightskeleton crashes on different geometries:

with x as (select '0106000020E61000000100000001030000000100000019000000B9FFD379B05B224038A2CDFA21644840D0C73CC7A95B2240C06A978422644840763500EEA75B2240E8E4D0F32264484080112E5CB45B2240391D743F25644840414BD3F3B45B2240A7D8CA5225644840C5FF62C7B85B2240025BB6CF2564484032B85EB9BD5B2240AF8A21FA2664484047BB35DCD45B224045CA6789256448407BF78AA9D65B2240223F825D256448406CF3536ADB5B22406A3B91F924644840CCF3536ADB5B2240623B91F9246448402AC1BAD8DE5B22401EAB6B9824644840581AFC28DB5B22406FB5399023644840CF573AC2E75B22408C9A923F22644840EB8072873A5C22403EC9E52D1A6448408A57C0534A5C22401256A1A31864484087DA609F4F5C2240FA5E791F186448407BE41943905C2240BB6061F91064484007BD14C48D5C2240E73444321064484066A3B5B7475C2240980AE4BF16644840BFCE68AD445C224044F6B30817644840DF9653FF1E5C224054181F8F1A64484092403337CA5B224097AD9A7D2264484092125BB6BD5B224069640DA923644840B9FFD379B05B224038A2CDFA21644840'
::geometry as poly1) 
select st_straightskeleton(poly1) from x;
-- no transformation: crashes

with x as (select '0106000020E61000000100000001030000000100000019000000B9FFD379B05B224038A2CDFA21644840D0C73CC7A95B2240C06A978422644840763500EEA75B2240E8E4D0F32264484080112E5CB45B2240391D743F25644840414BD3F3B45B2240A7D8CA5225644840C5FF62C7B85B2240025BB6CF2564484032B85EB9BD5B2240AF8A21FA2664484047BB35DCD45B224045CA6789256448407BF78AA9D65B2240223F825D256448406CF3536ADB5B22406A3B91F924644840CCF3536ADB5B2240623B91F9246448402AC1BAD8DE5B22401EAB6B9824644840581AFC28DB5B22406FB5399023644840CF573AC2E75B22408C9A923F22644840EB8072873A5C22403EC9E52D1A6448408A57C0534A5C22401256A1A31864484087DA609F4F5C2240FA5E791F186448407BE41943905C2240BB6061F91064484007BD14C48D5C2240E73444321064484066A3B5B7475C2240980AE4BF16644840BFCE68AD445C224044F6B30817644840DF9653FF1E5C224054181F8F1A64484092403337CA5B224097AD9A7D2264484092125BB6BD5B224069640DA923644840B9FFD379B05B224038A2CDFA21644840'
::geometry poly1) 
select st_transform(st_straightskeleton(st_transform(poly1, 4258)), 4326) from x;
-- same geometry, using transformation to 4258 and back to 4326: works!

with x as (select '0106000020E6100000010000000103000000010000003F000000C72B2C6B565822401F38E6AA296348407488F267555822401F5E05522D6348407E9724ECB758224084D3FCA54563484097D3298DBE5822409F4EC632476348404D8EE210C958224089B306A0496348405FB494BBD258224080169CDC4B634840B2092E7EDB5822403D378FE34D634840BB8E7025E35822406FE275A84F6348400EB2A371E758224024406A1C5163484009275762E95822404A8E67C451634840F508DDE4F9582240FE54F6CF55634840C5B4E1A90D5922405C3B18235A6348406FC3FAF71A592240BCECFD0B5D6348408EF918C52A592240F6766E8060634840696A1D172E592240677B948E6163484059B34DAF35592240AD45E0F3636348409FD12A2F3C5922403A31988965634840F3582A6849592240FE3070C26863484023ED6E744A59224028698FF9686348409FC46CAF5059224013866C756A6348407E3C2ED155592240D9F44EAE6B634840D443412F5959224057E3E57B6C634840EE58031E5D59224057DDBE6C6D6348402824F7FE6659224027199AC86F634840CEC3132E70592240C768BEFA71634840218E90E373592240C27C30DD726348404BE53E477559224005CA008A736348401157C73278592240DD8DC486746348402040F0A27B5922403300E19975634840F4E7140FD0592240BD355D3E85634840EA7870539F592240E56DD95C776348402D0DD2DA91592240A79E6F257463484046BEC7DC8C592240FE8F861A726348404D821405795922402E921CCE6C634840E6A66238765922404BB341226D63484007A01E156C592240C93D5FCA6A6348401C9491935D5922401AA8436F67634840381E51514F59224050598E22646348401FB0E53944592240F9610E9261634840CE0CB9A43C592240D3BF23D05F63484095CCE1D037592240C78819B25E6348400DB176413D5922407BB577EA5D6348408F2B7F3B2F592240CE34E9865A63484063A26A6129592240FADEC22E5B63484048028C6520592240171E92025963484007EFDE1715592240FCDF5B4756634840CFAE14B209592240564233845363484079F5A194FE5822402647E9D350634840B7E7FF71F75822409BF728F94E6348403EAAB46AF1582240B5EC66684D634840DF6BFFA5DE582240F3F4F9CB486348409329A140CC582240A904465D44634840C2838E87C058224061672D8A41634840F001A7E7B058224086C09ADD3D63484035156E11AF5822404D5C56723D634840963D0498AA582240AC0FA06C3C6348402F740B7CA6582240DF82C37C3B63484040ABE19A9B582240DD5188C23863484006D5E4D182582240EE09BF3333634840B8E331D8755822408620391130634840F492EBEE8B582240FB8B0E962D63484037F445EB88582240105D1EB12C634840C72B2C6B565822401F38E6AA29634840'
::geometry poly2)
select st_transform(st_straightskeleton(st_transform(poly2, 4258)), 4326) from x;
-- another geometry but the same transformations as above: crash..


with x as ((select '0106000020E61000000100000001030000000100000019000000B9FFD379B05B224038A2CDFA21644840D0C73CC7A95B2240C06A978422644840763500EEA75B2240E8E4D0F32264484080112E5CB45B2240391D743F25644840414BD3F3B45B2240A7D8CA5225644840C5FF62C7B85B2240025BB6CF2564484032B85EB9BD5B2240AF8A21FA2664484047BB35DCD45B224045CA6789256448407BF78AA9D65B2240223F825D256448406CF3536ADB5B22406A3B91F924644840CCF3536ADB5B2240623B91F9246448402AC1BAD8DE5B22401EAB6B9824644840581AFC28DB5B22406FB5399023644840CF573AC2E75B22408C9A923F22644840EB8072873A5C22403EC9E52D1A6448408A57C0534A5C22401256A1A31864484087DA609F4F5C2240FA5E791F186448407BE41943905C2240BB6061F91064484007BD14C48D5C2240E73444321064484066A3B5B7475C2240980AE4BF16644840BFCE68AD445C224044F6B30817644840DF9653FF1E5C224054181F8F1A64484092403337CA5B224097AD9A7D2264484092125BB6BD5B224069640DA923644840B9FFD379B05B224038A2CDFA21644840'
::geometry polys) UNION
(select '0106000020E6100000010000000103000000010000003F000000C72B2C6B565822401F38E6AA296348407488F267555822401F5E05522D6348407E9724ECB758224084D3FCA54563484097D3298DBE5822409F4EC632476348404D8EE210C958224089B306A0496348405FB494BBD258224080169CDC4B634840B2092E7EDB5822403D378FE34D634840BB8E7025E35822406FE275A84F6348400EB2A371E758224024406A1C5163484009275762E95822404A8E67C451634840F508DDE4F9582240FE54F6CF55634840C5B4E1A90D5922405C3B18235A6348406FC3FAF71A592240BCECFD0B5D6348408EF918C52A592240F6766E8060634840696A1D172E592240677B948E6163484059B34DAF35592240AD45E0F3636348409FD12A2F3C5922403A31988965634840F3582A6849592240FE3070C26863484023ED6E744A59224028698FF9686348409FC46CAF5059224013866C756A6348407E3C2ED155592240D9F44EAE6B634840D443412F5959224057E3E57B6C634840EE58031E5D59224057DDBE6C6D6348402824F7FE6659224027199AC86F634840CEC3132E70592240C768BEFA71634840218E90E373592240C27C30DD726348404BE53E477559224005CA008A736348401157C73278592240DD8DC486746348402040F0A27B5922403300E19975634840F4E7140FD0592240BD355D3E85634840EA7870539F592240E56DD95C776348402D0DD2DA91592240A79E6F257463484046BEC7DC8C592240FE8F861A726348404D821405795922402E921CCE6C634840E6A66238765922404BB341226D63484007A01E156C592240C93D5FCA6A6348401C9491935D5922401AA8436F67634840381E51514F59224050598E22646348401FB0E53944592240F9610E9261634840CE0CB9A43C592240D3BF23D05F63484095CCE1D037592240C78819B25E6348400DB176413D5922407BB577EA5D6348408F2B7F3B2F592240CE34E9865A63484063A26A6129592240FADEC22E5B63484048028C6520592240171E92025963484007EFDE1715592240FCDF5B4756634840CFAE14B209592240564233845363484079F5A194FE5822402647E9D350634840B7E7FF71F75822409BF728F94E6348403EAAB46AF1582240B5EC66684D634840DF6BFFA5DE582240F3F4F9CB486348409329A140CC582240A904465D44634840C2838E87C058224061672D8A41634840F001A7E7B058224086C09ADD3D63484035156E11AF5822404D5C56723D634840963D0498AA582240AC0FA06C3C6348402F740B7CA6582240DF82C37C3B63484040ABE19A9B582240DD5188C23863484006D5E4D182582240EE09BF3333634840B8E331D8755822408620391130634840F492EBEE8B582240FB8B0E962D63484037F445EB88582240105D1EB12C634840C72B2C6B565822401F38E6AA29634840'
::geometry polys)) 
select st_transform(st_straightskeleton(st_transform(polys, 900913)), 4326) from x;
-- using 900913 for the inner transformation on both geometries: works \o/

but let's make it even weirder!
at first i wanted to use EWKT representation here but then i noticed reading the same geometries as above from ewkt and using this in st_straightskeleton works perfectly fine. also for all of my test geometries, not only the two i used above:

with x as ((select '0106000020E61000000100000001030000000100000019000000B9FFD379B05B224038A2CDFA21644840D0C73CC7A95B2240C06A978422644840763500EEA75B2240E8E4D0F32264484080112E5CB45B2240391D743F25644840414BD3F3B45B2240A7D8CA5225644840C5FF62C7B85B2240025BB6CF2564484032B85EB9BD5B2240AF8A21FA2664484047BB35DCD45B224045CA6789256448407BF78AA9D65B2240223F825D256448406CF3536ADB5B22406A3B91F924644840CCF3536ADB5B2240623B91F9246448402AC1BAD8DE5B22401EAB6B9824644840581AFC28DB5B22406FB5399023644840CF573AC2E75B22408C9A923F22644840EB8072873A5C22403EC9E52D1A6448408A57C0534A5C22401256A1A31864484087DA609F4F5C2240FA5E791F186448407BE41943905C2240BB6061F91064484007BD14C48D5C2240E73444321064484066A3B5B7475C2240980AE4BF16644840BFCE68AD445C224044F6B30817644840DF9653FF1E5C224054181F8F1A64484092403337CA5B224097AD9A7D2264484092125BB6BD5B224069640DA923644840B9FFD379B05B224038A2CDFA21644840'
::geometry polys) UNION
(select '0106000020E6100000010000000103000000010000003F000000C72B2C6B565822401F38E6AA296348407488F267555822401F5E05522D6348407E9724ECB758224084D3FCA54563484097D3298DBE5822409F4EC632476348404D8EE210C958224089B306A0496348405FB494BBD258224080169CDC4B634840B2092E7EDB5822403D378FE34D634840BB8E7025E35822406FE275A84F6348400EB2A371E758224024406A1C5163484009275762E95822404A8E67C451634840F508DDE4F9582240FE54F6CF55634840C5B4E1A90D5922405C3B18235A6348406FC3FAF71A592240BCECFD0B5D6348408EF918C52A592240F6766E8060634840696A1D172E592240677B948E6163484059B34DAF35592240AD45E0F3636348409FD12A2F3C5922403A31988965634840F3582A6849592240FE3070C26863484023ED6E744A59224028698FF9686348409FC46CAF5059224013866C756A6348407E3C2ED155592240D9F44EAE6B634840D443412F5959224057E3E57B6C634840EE58031E5D59224057DDBE6C6D6348402824F7FE6659224027199AC86F634840CEC3132E70592240C768BEFA71634840218E90E373592240C27C30DD726348404BE53E477559224005CA008A736348401157C73278592240DD8DC486746348402040F0A27B5922403300E19975634840F4E7140FD0592240BD355D3E85634840EA7870539F592240E56DD95C776348402D0DD2DA91592240A79E6F257463484046BEC7DC8C592240FE8F861A726348404D821405795922402E921CCE6C634840E6A66238765922404BB341226D63484007A01E156C592240C93D5FCA6A6348401C9491935D5922401AA8436F67634840381E51514F59224050598E22646348401FB0E53944592240F9610E9261634840CE0CB9A43C592240D3BF23D05F63484095CCE1D037592240C78819B25E6348400DB176413D5922407BB577EA5D6348408F2B7F3B2F592240CE34E9865A63484063A26A6129592240FADEC22E5B63484048028C6520592240171E92025963484007EFDE1715592240FCDF5B4756634840CFAE14B209592240564233845363484079F5A194FE5822402647E9D350634840B7E7FF71F75822409BF728F94E6348403EAAB46AF1582240B5EC66684D634840DF6BFFA5DE582240F3F4F9CB486348409329A140CC582240A904465D44634840C2838E87C058224061672D8A41634840F001A7E7B058224086C09ADD3D63484035156E11AF5822404D5C56723D634840963D0498AA582240AC0FA06C3C6348402F740B7CA6582240DF82C37C3B63484040ABE19A9B582240DD5188C23863484006D5E4D182582240EE09BF3333634840B8E331D8755822408620391130634840F492EBEE8B582240FB8B0E962D63484037F445EB88582240105D1EB12C634840C72B2C6B565822401F38E6AA29634840'
::geometry polys)) 
select st_straightskeleton(st_geomfromewkt(st_asewkt(polys))) from x;
-- same geometries as before. no st_transform - simply writing and reading from ewkt: works!

i will use this as a workaround for now. let's hope it works in the field later on.

for the sake of completeness:
SELECT PostGIS_Full_Version();

POSTGIS="2.2.2 r14797" 
GEOS="3.5.0-CAPI-1.9.0 r4090" 
SFCGAL="1.3.0" 
PROJ="Rel. 4.9.1, 04 March 2015" 
GDAL="GDAL 2.0.2, released 2016/01/26" 
LIBXML="2.7.8" 
LIBJSON="0.12" RASTER

[smnorris]

I have the same issue, for certain polygons, ST_ApproximateMedialAxis renders postgres unresponsive. Wrapping the geometry in ST_GeomFromEWKT(ST_AsEWKT(geom)) is an effective workaround for me too (thanks @Entara !)

SELECT PostGIS_Full_Version();

POSTGIS="2.3.0 r15146" 
GEOS="3.6.1-CAPI-1.10.1 r0" 
SFCGAL="1.3.0" 
PROJ="Rel. 4.9.3, 15 August 2016" 
GDAL="GDAL 1.11.5, released 2016/07/01" 
LIBXML="2.9.4" 
LIBJSON="0.12" 
TOPOLOGY RASTER

As an aside, I was previously creating the medial axis lines with FME's CenterLineReplacer transformer. It worked in FME2013 but more recent versions crash. I haven't investigated to see if the FME crash is on the same features as postgis/sfcgal.

[lbartoletti]

Problem confirmed with SFCGAL 1.3.7 and CGAL 5.0. Error: CGAL failed to create straightSkeleton

cc @sloriot