A split and merge procedure for polygonal border detection of dot pattern

An approach to find the polygonal border of a dot pattern is proposed. The procedure starts with a convex hull of the dot pattern and obtains the fina l border by the process of splitting followed by merging. During splitting one or more sides of the convex hull are deleted and new sides are added to take care of the inherent concavity. To obtain a smooth polygonal border, two or more sides an merged into a single one. An advantage of the procedur e is that the user can set a priori the number of sides of the polygon. Als o, it works quite well if there is a gradual transition of dot density in t he pattern. Given the convex hull, the procedure can be executed in O(nm) t ime for a pattern consisting of n dots and an m-sided polygonal border. Mor eover, the procedure can be implemented in a parallel system as the operati ons on each side of the convex hull polygon are independent as well as loca lised. (C) 1999 Elsevier Science B.V. All rights reserved.