[postgis-users] [postgis-devel] Problem in st_StriaghtSkeleton - Hangs!

[Stephen Woodbridge]

On 1/18/2018 3:54 AM, Martijn Meijers wrote:
> Hi,
> 
> I think the problem with this input is that there is *a lot* of parallel 
> lines, meaning that in the algorithm of skeleton construction many 
> things happen at exactly the same time (if you see it as a wavefront 
> propagation). I also tried with my Python implementation [1], but this 
> also crashes (-:
> 
> One option I'd try is to slightly perturb/add some randomness to your 
> input coordinates (to take away the lines being exactly parallel) and 
> see if that goes through...

This data is generated from a scan of a building floor plan by passing 
it through st_dumpaspolygons(rast, 1, true) so it will always have lots 
of parallel lines. This is just one of ten similar drawings but its the 
only one that fails. I'll be running a larger set today and may have 
some additional failures.

I tried Regina's suggestion of using ST_ApproximateMedialAxis and 
ST_SubDivide but that also seems to hang in my work flow. I'll take 
another look through my queries to make sure I incorporated it correctly.

How would you go about perturbing the input coordinates?

Thanks,
   -Steve

> Martijn
> 
> 
> [1] https://bitbucket.org/bmmeijers/grassfire/
> 
> On 18-01-18 02:21, Stephen Woodbridge wrote:
>> Hi Regina,
>>
>> Thanks, this is a great idea. I rework my queries to work in 
>> ST_ApproximateMedialAxis and ST_SubDivide and see how that does.
>>
>> -Steve
>>
>> On 1/17/2018 8:13 PM, Regina Obe wrote:
>>> Steve,
>>>
>>> One more thought.  Can you try this and see if it works.  I think 
>>> ST_StraightSkeleton and ST_ApproximateMedialAxis are having issues, 
>>> because in this case your holes are so big that it almost cuts into 
>>> another.
>>>
>>> So to work around the issue, you can subdivide the polygon and then 
>>> do the analyze like this:
>>>
>>> SELECT  ST_ApproximateMedialAxis(ST_SubDivide('POLYGON((256 760,518 
>>> 760,518 630,674 630,674
>>> 239,673 239,127 239,127 240,126 240,126 513,127 513,127 514,126 514,126
>>> 630,255 630,256 630,256 760),(128 629,128 423,270 423,270 422,271
>>> 422,271 240,672 240,672 629,128 629),(258 759,258 631,516 631,516
>>> 759,258 759),(128 421,128 240,269 240,269 421,128 421))'::geometry, 
>>> 12));
>>>
>>> You might need to tweak with the subdivide param.
>>>
>>> http://postgis.net/docs/manual-dev/ST_Subdivide.html
>>>
>>> The subdivide cuts right into the holes turning them not into holes 
>>> so you end up with simple polygons that approximate medial axis can 
>>> handle.
>>>
>>> Once you are done you can run ST_Union on your set of Linestrings.
>>>
>>>
>>>
>>>
>>>
>>> -----Original Message-----
>>> From: postgis-devel [mailto:postgis-devel-bounces at lists.osgeo.org] On 
>>> Behalf Of Stephen Woodbridge
>>> Sent: Wednesday, January 17, 2018 2:47 PM
>>> To: PostGIS Development Discussion <postgis-devel at lists.osgeo.org>
>>> Subject: [postgis-devel] Problem in st_StriaghtSkeleton - Hangs!
>>>
>>> Hi all,
>>>
>>> I have run into a problem using st_StraightSkelton() where it appears 
>>> to hang at 100 cpu. Maybe an endless loop?
>>>
>>> select st_straightskeleton('POLYGON((256 760,518 760,518 630,674 630,674
>>> 239,673 239,127 239,127 240,126 240,126 513,127 513,127 514,126 514,126
>>> 630,255 630,256 630,256 760),(128 629,128 423,270 423,270 422,271
>>> 422,271 240,672 240,672 629,128 629),(258 759,258 631,516 631,516
>>> 759,258 759),(128 421,128 240,269 240,269 421,128 421))'::geometry);
>>>
>>> POSTGIS="2.3.3 r15473" GEOS="3.5.1-CAPI-1.9.1 r4246" SFCGAL="1.2.2"
>>> PROJ="Rel. 4.9.2, 08 September 2015" GDAL="GDAL 1.11.3, released 
>>> 2015/09/16" LIBXML="2.9.3" LIBJSON="0.11.99" RASTER
>>>
>>> Can anyone reproduce this?
>>> Any idea how to work around it?
>>>
>>> Is there a non-CGAL version of skeleton?
>>>
>>> Thanks,
>>>     -Steve
>>>
>>> ---
>>> This email has been checked for viruses by Avast antivirus software.
>>> https://www.avast.com/antivirus
>>>
>>> _______________________________________________
>>> postgis-devel mailing list
>>> postgis-devel at lists.osgeo.org
>>> https://lists.osgeo.org/mailman/listinfo/postgis-devel
>>>
>>> _______________________________________________
>>> postgis-users mailing list
>>> postgis-users at lists.osgeo.org
>>> https://lists.osgeo.org/mailman/listinfo/postgis-users
>>>
>>
>> _______________________________________________
>> postgis-users mailing list
>> postgis-users at lists.osgeo.org
>> https://lists.osgeo.org/mailman/listinfo/postgis-users
> 
> _______________________________________________
> postgis-users mailing list
> postgis-users at lists.osgeo.org
> https://lists.osgeo.org/mailman/listinfo/postgis-users