Polygon Detection from a Set of Lines

Abstract

Detecting polygons defined by a set of line segments in a plane is an important step in the analysis of vectorial drawings. This paper presents an approach that combines several algorithms to detect basic polygons from a set of arbitrary line segments. The resulting algorithm runs in polynomial time and space, with complexities of O((N + M)4) and O((N + M)2) respectively, where N is the number of line segments and M is the number of intersections between line segments. Our choice of algorithms was made to strike a good compromise between efficiency and ease of implementation. The result is a simple and efficient solution to detect polygons from lines.