Generation, Decomposition and Analysis of the Isothetic Polygon in Digital Geometric Paradigm
Dr. Arindam Biswas
Dr. Hafizur Rahaman
Department of Information Technology
Indian Institute of Engineering Science and Technology, Shibpur
Isothetic polygon has an important role in the eld of image processing and shape analysis. The generation of algorithms for construction of isothetic polygon is signicant in the domain of digital geometry. The isothetic polygon has applications in dierent elds, which leads to development of various algorithms for analysis of the isothetic polygon. It is an emerging area of interest among the researchers and engineers from Computer Science and Information Technology. Study of isothetic polygons may nd a special role in Robotics for path planning, object gripping etc. The algorithms discussed here are applied on digital objects for its shape analysis. The family of shortest isothetic paths (FSIP) between two grid points in a digital object A is the union of all possible shortest isothetic paths (SIPs) between them. A novel algorithm to compute the FSIP between two grid points of the inner isothetic cover P that inscribes the object A, is proposed here. The algorithm is based on certain combinatorial rules derived from the characterization of FSIP. A preprocessing is done at rst with the grid points comprising the border BP of P in O(n log n) time, n being the number of points in BP . Then, for any pair of grid points in P, the algorithm computes their FSIP in O(n) time. As shown in this chapter, the FSIP can be useful for dierent shape-related applications, such as nding a critical region inside an object. Experimental results show the eectiveness of the algorithm and its further prospects in shape analysis and related applications.