Premium
On finding an orthogonal convex skull of a digital object
Author(s) -
Dutt Mousumi,
Biswas Arindam,
Bhowmick Partha,
Bhattacharya Bhargab B.
Publication year - 2011
Publication title -
international journal of imaging systems and technology
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.359
H-Index - 47
eISSN - 1098-1098
pISSN - 0899-9457
DOI - 10.1002/ima.20266
Subject(s) - regular polygon , convex polygon , computer science , boundary (topology) , polygon (computer graphics) , algorithm , object (grammar) , time complexity , set (abstract data type) , traverse , mathematics , artificial intelligence , geometry , mathematical analysis , telecommunications , frame (networking) , geodesy , programming language , geography
A combinatorial algorithm to compute an orthogonal convex skull of a digital object imposed on the background grid is presented in this paper. The proposed algorithm has the time complexity of O(n log n) , which improves the earlier method of O(n 2 ) time complexity for finding the convex skull of a simple orthogonal polygon. A set of rules is formulated first and then an orthogonal convex skull is derived by applying these rules while traversing along the boundary of the inner orthogonal polygon that tightly inscribes the given digital object. The algorithm uses only comparison and addition in the integer domain, which makes it amenable to fast real‐world applications. Experimental results on different shapes have also been presented to demonstrate the efficacy and elegance of the proposed technique. © 2011 Wiley Periodicals, Inc. Int J Imaging Syst Technol, 21, 14–27, 2011.