Suggestion to add skeleton algorithm module

[morganherlocker]

straight skeleton algorithm, which forms the basis for most polygon offset curve algorithms

https://www.cgal.org/UserWorkshop/2004/straight_skeleton.pdf

The general idea is this:

CGAL implementation

[morganherlocker]

Interestingly, this algorithm can be used for computing road centerlines.

[satellite imagery] => [opencv detected polygon vectors] => [polylines]

[TimMcCauley]

This would actually be pretty grand. To my knowledge there is now Straight Skeleton JS Library out there, I've been using SFCGAL on PostGIS to do this.

[morganherlocker]

Noting here for reference, floating point weighted skeleton (we want straight skeleton) implementation: http://twak.blogspot.com/2010/06/weighted-straight-skeleton-source.html

twak has been working on this stuff for several years, and his site is a great resource:

• dynamic procedural parcel generation http://twak.blogspot.com/2011/12/procedural-generation-of-parcels-in.html
• polygon simplification http://twak.blogspot.com/2011/01/straight-skeleton-for-polygon.html
• dynamic 3d building generation http://twak.blogspot.com/2009/12/skeleton-project-progress.html
• n-dimensional skeletons http://twak.blogspot.com/2009/11/higher-dimensional-skeletons.html

[TimMcCauley]

This pySkeleton implementation merely works for screen coordinates:

http://vision.mas.ecp.fr/Personnel/teboul/pySkeleton.php

And this is the PostGIS extension I have been working with lately:

http://oslandia.github.io/SFCGAL/

[gmaclennan]

There's also https://github.com/migurski/Skeletron

[morganherlocker]

@gmaclennan Skeletron no longer uses a straight skeleton, but I was able to dig through the repo and find a commit where it still had the code around. No idea how robust the implementation is, but it might be a good reference. https://github.com/migurski/Skeletron/blob/74103e06c726f953db50b9dad98718d4bff05cdf/Skeletron/__init__.py

[vlasvlasvlas]

nice, love the different approaches.

[tremby]

Interestingly, this algorithm can be used for computing road centerlines.

This is what I'm looking for. In particular right now I have some polygonal data for the position a new pipeline will be in, and the things I need to do with this data would be far easier if it were a line rather than a polygon.