Finding the Orthogonal Convex Hull(A linear-time combinatorial algorithm)AlgorithmA. Biswas, P. Bhowmick, M. Sarkar, and B. B. Bhattacharya,A Linear-time Combinatorial Algorithm to Find the Orthogonal Hull of an Object on the Digital Plane, Information Sciences, Vol. 216, pp. 176-195, 2012. What's it?The orthogonal convex hull of a digital object S, denoted by OH(S), is the smallest-area orthogonal polygon such that:(i) each point p∈S lies lies inside OH(S) and (ii) intersection of OH(S) with any horizontal or vertical line is either empty or exactly one line segment. | |
Our ContributionExisting algorithms on finding the convex hull are based on divide and conquer strategy, sweep-line approach, etc., whereas the proposed algorithm is combinatorial in nature and its time complexity is linear on the object perimeter instead of the object area. It computes the orthogonal (convex) hull of a digital object imposed on a background grid. The resolution and complexity of the orthogonal hull can be controlled by varying the grid size, which may be used for a multi-resolution shape analysis. For a larger grid size, the perimeter of an object decreases in length in terms of grid units, and hence the runtime of the algorithm reduces significantly. The algorithm uses only comparison and addition in the integer domain, thereby making it amenable to usage in real-world applications where speed is a prime factor. Extensive experimentation demonstrate the elegance and efficacy of the algorithm.Shown above: Demo on a small 2D object (grid size = 8). Each image shows the result after removal of the concave parts (yellow) in successive steps. The final orthogonal hull is reported in less than 1 millisecond. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
©Partha Bhowmick (June 2012) |