Important: Brevity disclaimer.

Intro

2D Center Line calculation task is often encountered when processing polygons as in some sense center line “captures” the essential information about polygon structure and thus allows easier subsequent polygon processing.

Examples of higher level algorithms that heavily rely on center line calculation are:

• Polygons offsetting.
• Filtering out noisy parts of polygons.

The mathematical construction which represents center line for polygon is well-known: it is called “medial axis” and can be produced by 2D Voronoi diagram construction algorithm for segments.

Here is one example of center line construction:

However, getting “raw” center line is typically not enough for practical applications, as medial axis construction is extremely sensitive to the noise - thus, special filtering should be performed to extract only essential information and leave out noisy parts of center line.

During implementation, a lot of different filters were considered and implemented, ultimately resulting in the set of filters that produced good results for the tasks the center line is used for in Materialise.