Identification of faces in line drawings by edge decomposition

This paper presents a method to find the faces of objects in 2D line drawings, using an approach totally different from existing ones. It consists of two stages: decomposition and face forming. In decomposition, a drawing is decomposed into chains of connected edges. Each chain belongs to one face only, but may not yet form a closed loop. The decomposition is local to a vertex, and takes no account of the overall structure of the drawing. The algorithm ensures that there is a chain for every face in the object. The face forming stage completes the loop for each chain to form a face. Our method can deliver both the real faces and the internal faces separately. It depends only on the topology of the drawing and not on the geometry, and is therefore applicable to line drawings with curves and straight lines, and 3D wireframes. We implemented our algorithm and tested it with hundreds of objects, including objects used in previous publications. It always delivers the correct result. Comparison with the latest methods shows that it is faster often by tens of times and, in some cases, hundreds of times. Decompose a drawing into sub-loops of edges that belong to only one face.Form face by finding the missing edges of a sub-loop in a limited search space.Low computational complexity, more efficient than all existing methods.Handle manifolds and non-manifolds.Handle line drawings and 3D wireframes with straight and curved edges.