Affiliations: [a] Department of Computer Science and Technology, Indian Institute of Engineering Science and Technology, Shibpur, India. [email protected] | [b] Department of Information Technology, Indian Institute of Engineering Science and Technology, Shibpur, India. [email protected] | [c] Department of Computer Science and Engineering, St. Thomas College of Engineering and Technology, Kolkata, India. [email protected] | [d] Department of Computer Science and Engineering, Indian Institute of Technology, Madras, India. [email protected]
Correspondence:
[*]
Address for correspondence: Department of Information Technology, IIEST Shibpur, India.
Note: [1] A preliminary version of the paper appeared in 19th IAPR International Conference on Discrete Geometry for Computer Imagery, DGCI-2016.
Abstract: 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(nglogng) 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(nglogng) 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
