On the Minimal Perimeter Polygon for Digital Objects in the Triangular Tiling

The present work proposes an algorithm to determine the minimum perimeter polygon (MPP) of digital objects given as edge-adjacency-connected sets of tiles, in the plane tiling of regular triangles. As input data, it uses a canonical boundary path of tiles obtained via boundary tracing. The MPP algorithm finds the ordered sequence of vertices of the MPP frontier, being the shortest polygonal curve which visits the entire boundary. It relies on the construction and iterative restriction of cones of visibility through boundary tiles. The algorithm is illustrated by examples, and a correctness proof is outlined for digital objects with simple boundary paths, that is, whose boundaries are digital Jordan curves.