Finding Shortest Triangular Path and its Family inside a Digital Object

This article presents a combinatorial algorithm to find a shortest triangular path (STP) between two points inside a digital object imposed on triangular grid that runs in O ( n g log n g )time, where n is the number of pixels on the contour of the object and g is the grid size. Initially, the inner triangular cover which maximally inscribes the object is constructed to ensure that the path lies within the object. An appropriate bounding parallelogram is considered with those two points in diagonally opposite corners and then one of the semi-perimeters of the parallelogram is traversed. Certain combinatorial rules are formulated based on the properties of triangular grid and are applied during the traversal whenever required to shorten the triangular path. A shortest triangular path between any two points may not be unique. Another combinatorial algorithm is presented, which finds the family of shortest triangular path (FSTP) (i.e., the region containing all possible shortest triangular paths) between two given points inside a digital object and runs in O ( n g log n g ) time. Experimental results are presented to verify the correctness, robustness, and efficacy of the algorithms. STP and FSTP can be useful for shape analysis of digital objects and determining shape signatures. 1