### Thinning-free Polygonal Approximation of Thick Digital Curves Using Cellular Envelope

#### Resum

Since the inception of successful rasterization of curves and objects in the digital space, several algorithms

have been proposed for approximating a given digital curve. All these algorithms, however, resort to

thinning as preprocessing before approximating a digital curve with changing thickness. Described in this

paper is a novel thinning-free algorithm for polygonal approximation of an arbitrarily thick digital curve,

using the concept of “cellular envelope”, which is newly introduced in this paper. The cellular envelope,

defined as the smallest set of cells containing the given curve, and hence bounded by two tightest (inner and

outer) isothetic polygons, is constructed using a combinatorial technique. This envelope, in turn, is analyzed

to determine a polygonal approximation of the curve as a sequence of cells using certain attributes of digital

straightness. Since a real-world curve=curve-shaped object with varying thickness, unexpected disconnectedness,

noisy information, etc., is unsuitable for the existing algorithms on polygonal approximation, the

curve is encapsulated by the cellular envelope to enable the polygonal approximation. Owing to the implicit

Euclidean-free metrics and combinatorial properties prevailing in the cellular plane, implementation

of the proposed algorithm involves primitive integer operations only, leading to fast execution of the algorithm.

Experimental results that include output polygons for different values of the approximation parameter

corresponding to several real-world digital curves, a couple of measures on the quality of approximation,

comparative results related with two other well-referred algorithms, and CPU times, have been presented to

demonstrate the elegance and efficacy of the proposed algorithm.

have been proposed for approximating a given digital curve. All these algorithms, however, resort to

thinning as preprocessing before approximating a digital curve with changing thickness. Described in this

paper is a novel thinning-free algorithm for polygonal approximation of an arbitrarily thick digital curve,

using the concept of “cellular envelope”, which is newly introduced in this paper. The cellular envelope,

defined as the smallest set of cells containing the given curve, and hence bounded by two tightest (inner and

outer) isothetic polygons, is constructed using a combinatorial technique. This envelope, in turn, is analyzed

to determine a polygonal approximation of the curve as a sequence of cells using certain attributes of digital

straightness. Since a real-world curve=curve-shaped object with varying thickness, unexpected disconnectedness,

noisy information, etc., is unsuitable for the existing algorithms on polygonal approximation, the

curve is encapsulated by the cellular envelope to enable the polygonal approximation. Owing to the implicit

Euclidean-free metrics and combinatorial properties prevailing in the cellular plane, implementation

of the proposed algorithm involves primitive integer operations only, leading to fast execution of the algorithm.

Experimental results that include output polygons for different values of the approximation parameter

corresponding to several real-world digital curves, a couple of measures on the quality of approximation,

comparative results related with two other well-referred algorithms, and CPU times, have been presented to

demonstrate the elegance and efficacy of the proposed algorithm.