Skeletonization

UPDATE: no more needed! :)

We need an algorithm to transform a thin polygon into a polyline by collapsing its edges. Thin polygon here means that it's a polygon whose width doesn't exceed a given known value.

In the following example, the input polygons (defined as XY points) are in black and the desired output is in orange. We do not care about the exact position of the resulting skeleton polyline, so there's large tolerance there.

One option is to compute the straight skeleton of the polygon and then remove all the leafs (lines going to vertices). This could be accomplished using one of the following options:

• make Perl bindings for CGAL unfortunately, CGAL license is not compatible with GPL
• make a Perl or C or C++ port of the camp skeleton Java library
• make a new straight skeleton implementation (could this be easier since we're dealing with a subset of polygons?)

Other ideas include:

• Voronoi diagrams but I didn't get much far there
• find a way to split the polygons in their sides (halves) and only use one (we don't care much that the result isn't in the very middle)

This problem is known as skeletonization or topological skeleton or medial axis. It is a common problem for GIS applications (for example, to find the axis of a river). The Internet is full of theoretical papers, but they don't provide any code implementation or they talk about bitmaps.

---

An idea by Arcol

Here is my idea:

Do at each vertex a bisector line and connect their midpoints.

Allowed area: The area of polyline

Algorithm:

1. Iterate through vertices and draw a bisector line, the length is where it reach the perimeter of the allowed area.
2. Determine the midpoints of each bisector line
3. Connect the midpoints to its nearest neighboor, if and only if the connecting line travels within the allowed area only. Here are a python example] and the original site with many useful 2D math solution.
4. Cleanup. Remove segments which are under a threshold. The threshold may be coming from physical experiment of printing (lets say: no segment under 0.1mm) OR the threshold is the shortest segment of the original polyline

To test the idea, I drew several testcases in qcad. Here is a dump of the pictures:

Approximation a curved line (make a polyline first):

More corner cases:

A really tricky corner case:)

A really steril testcase: