Towards Analysis of Digital Objects using Combinatorial Algorithm on Orthogonal and Triangular Grids

Abstract

This thesis explores some combinatorial algorithms for constructing geometric figures to analyse digital objects in orthogonal and triangular grids. Orthogonal or triangular grids are typically used in grid digitization processes when digital objects are placed on the grid and analyzed. Grid spacing, often known as the separation between parallel lines, is a parameter that can be tuned to alter the behaviour of an algorithm. Two of the four problems addressed in this thesis are dealt in the orthogonal grid, and two are in a triangular grid. To ensure the accuracy and efficiency of the proposed algorithms, all of the algorithms presented in this thesis are tested on various data sets and real-world objects. The first problem addressed here is to construct the relative orthogonal convex hull of the inner cover with respect to the outer cover of the digital object where the digital object lies on an orthogonal grid. The proposed algorithm runs in O(m) time, where m is the total number of vertices on the inner and outer cover. The second algorithm deals with construction of the hull of the set of orthogonal polygons. The algorithm runs in linear time with respect to the number of vertices of the polygons and is combinatorial in nature. The algorithm is simple and uses arithmetic and logical operations to compute the orthogonal hull. The next problem is to construct the skull of a digital object lying on the triangular grid. Initially, the inner cover of the object is derived, and then a set of rules are used to remove the convex portion such that the resulting polygon is of maximum area. Let, n be the number of border points of the digital objects and g be the grid size then the algorithm takes O(n/g) time. The thesis is concluded with another work which locates the largest area parallelogram inscribing a digital object lying on the triangular grid. The algorithm takes O(k (n/g) log(n/g)) time where k is the number of concavities and n and g are as stated above. Initially, the triangular cover (inner) of the digital