Computing the minimal perimeter polygon for sets of rectangular tiles based on visibility cones
Petra Wiederhold · Research Square · 2023
Abstract In the context of digital image modelling and convexity analysis of digital objects, the minimum perimeter polygon (MPP) was defined in the 1970s in several articles by Sklansky, Chazin, Hansen, and Kibler, where sets of pixels were identified with plane mosaics or polygonal tilings, and, the Sklansky-Chazin-Hansen algorithm (1972) and the Sklansky-Kibler algorithm (1976) were proposed for determining the MPP vertices. Both algorithms rely on constructing and iteratively restricting visibility cones, the MPP vertices result as special vertices of the tiles. This paper reviews both classical algorithms for regular complexes which are special sets of rectangular tiles, and an adaptation to square tiles recommended in widely used modern digital image analysis text books (2018, 2020), to construct approximations of simple digital 4-contours. We show that these three algorithms are erroneous, specially, that the Sklansky-Chazin-Hansen algorithm has numerous types of errors, and that their mathematical foundation contains incorrect details. After analysing and correcting these errors, a new version of MPP algorithm for certain sets of rectangular tiles is presented, its correctness is proved, and the classical algorithms are corrected.