A linear-time algorithm to compute the triangular hull of a digital object

A linear-time algorithm for determining the triangular hull of a digital object that is digitized with a uniform triangular-grid scan, is presented in this paper. A triangular hull consists of a sequence of edges on the underlying triangular grid T consisting of three sets of parallel grid lines that are inclined at 0°, 60°, and 120° w.r.t. the x-axis. The proposed algorithm determines the triangular hull of a given object on the basis of certain geometrical properties of the edge-sequence observed along its boundary. The approach is purely combinatorial in nature as opposed to other conventional algorithms used for computing the convex hull such as those based on divide-and-conquer or line-sweep. The running time of the algorithm is linear on the number of pixels on the perimeter of the object. Also, by using a more sparse grid, i.e., by increasing the grid unit, the number of perimeter-pixels, and in turn, the running time of the algorithm can be reduced proportionately. The algorithm is tested extensively on several test cases and experimental results and analysis are presented.