Parallel algorithms for identifying convex and non-convex basis polygons in an image

In this paper, we propose two novel parallel algorithms for identifying all the basis polygons in an image formed by n straight line segments each of which is represented by its two end points. The first algorithm is designed to tackle the simple situation where all basis polygons are convex. The second one deals with the general situation when the basis polygons can be both convex and non-convex. These algorithms are based on an idea of traversal along the periphery of the basis polygons in a well-defined manner so that each of these needs only O(n) time using an n × n processor array. Simulation results on various test input sets of intersecting line segments have also been found satisfactory.