As you may read on wikipedia, Straight Skeleton is method of representing a polygon by topological skeleton [1]. Well, this is not self describing words but let's see usage examples as it's widely used. First time I've heard about this algorithm when I was trying to visualize gabled roofs in 3D [2] from OSM buildings data and it looks like this algorithm is right way to construct roof shape:
Next time, I found that it is also useful for indoor environment generating [3] as it produces quite good results for typical building footprint:
However, I was surprised that there was no working .NET implementation. Hopefully, I found some good Java implementation done by kendzi:
"Implementation of straight skeleton algorithm for polygons with holes. It is based on concept of tracking bisector intersection with queue of events to process and circular list with processed events called lavs. This implementation is highly modified concept described by Petr Felkel and Stepan Obdrzalek [1]. In compare to original this algorithm has new kind of event and support for multiple events which appear in the same distance from edges. It is common when processing degenerate cases caused by polygon with right angles." [4]
I decided to port it to .NET taking into account language specific idioms. Original Java code depends on external libraries which provide some primitives: vector, line, ray, etc. My port has no dependencies as I ported all needed classes as well. You can find it on my github page [5].
[1] Wikipedia
[2] OpenStreetMap Simple 3D Buildings
[3] Alexander Dahl, Lars Rinde "Procedural Generation of Indoor Environments"
[4] Straight Skeleton by kendzi
[5] Github repository
Next time, I found that it is also useful for indoor environment generating [3] as it produces quite good results for typical building footprint:
However, I was surprised that there was no working .NET implementation. Hopefully, I found some good Java implementation done by kendzi:
"Implementation of straight skeleton algorithm for polygons with holes. It is based on concept of tracking bisector intersection with queue of events to process and circular list with processed events called lavs. This implementation is highly modified concept described by Petr Felkel and Stepan Obdrzalek [1]. In compare to original this algorithm has new kind of event and support for multiple events which appear in the same distance from edges. It is common when processing degenerate cases caused by polygon with right angles." [4]
I decided to port it to .NET taking into account language specific idioms. Original Java code depends on external libraries which provide some primitives: vector, line, ray, etc. My port has no dependencies as I ported all needed classes as well. You can find it on my github page [5].
[1] Wikipedia
[2] OpenStreetMap Simple 3D Buildings
[3] Alexander Dahl, Lars Rinde "Procedural Generation of Indoor Environments"
[4] Straight Skeleton by kendzi
[5] Github repository
Thank you guys, I will a look at your Api in order to use it on a CSharp app for 3D roof generate ;-)
AntwortenLöschenThanks for your work! Can you imagine an easy way to triangulate the skeleton on the fly so that it can be used in a 3d application? I'm not sure if Distances and Edges as property of the skeleton object provide enough information to identify each face when thinking about a roof.
AntwortenLöschenAnd seconds later I found out that each edge object contains a polygon object which again contains all points belonging to each face. My bad :)
LöschenHello,
AntwortenLöschenI am using your implementation also for OSM buildings (and other things), and I found it quite fast compared to the CGAL implementation (without further benchmarking)!
However I am getting quite some exceptions thrown, both on simple and apparently quite regular / 90° polygons, as well as on more complex polygons (like characters from fonts).
In one exception you write, "...it could be correct, but need some test data to check." Would you be interested in getting those polygon data?
Though a great library, thanks for that!
Playing with the code, and I believe that in your test, SkeletonTestC1 the resulting polygon 18 points 0 and 9 are wrong.
AntwortenLöschenThis is what I'm seeing: https://pasteboard.co/Ww5YcBRV7Vp4.png
Löschen