A new algorithm to compute an unbranched subset of the medial axis

Abstract

This paper introduces an innovative algorithm, The Curve of Incircles (IncirCu), designed to compute an unbranched subset of a shape’s medial axis (MA). The medial axis itself is a skeletal representation that encapsulates the shape’s interior, making it invaluable in various shape analysis applications. Traditionally, the medial axis is a branched structure, posing significant challenges for applications that rely on a single, unbranched curve. This new algorithm effectively overcomes these challenges by directly computing ordered set of vertices situated on the medial axis points. These vertices can then be transformed into a single polygonal chain that is unbranched and free of loops, effectively eliminating the need for removal of MA branches to obtain a single curve. Consequently, the
algorithm is highly applicable in any context that requires an unbranched input curve, such as cartography and land surveying. To validate its performance, the results of IncirCu were compared with those of existing algorithms such as Straight Skeleton, Medial Axis, and iCMR. Conducted tests showed the average distance between the IncirCu output and the reference Medial Axis to be near zero. While the axis comparison against iCMR and the Straight Skeleton revealed differences greater than zero, these discrepancies remained negligible when scaled against the input objects' overall size. It offers a practical solution to a longstanding problem of MA branch elimination, broadening the scope of possible applications and enhancing the efficiency and accuracy of shape analysis in various technical fields connected with civil engineering.