A FAST SCAN-LINE ALGORITHM FOR TOPOLOGICAL FILLING OF WELL-NESTED OBJECTS IN 2.5D DIGITAL PICTURES

摘要

A 2.5D digital picture is an array each cell of which is related to a list of color values; in other words, it can belong to several objects simultaneously. Classical notions of inside and outside being insufficient, we need to introduce nesting notions among objects: encasement and distance. We then define what a family of well-nested and significant objects is, to which it is possible to associate one and only one nesting tree. The concept of the nesting tree is closely related to that of topological filling, which consists in coloring the cells of a picture in accordance with their topological status; thus, the filling domain of a connected object may not be connected. We present and prove a scan-line algorithm which fills and constructs the tree of a family. Finally, we indicate how some slight modifications of this algorithm makes it possible to check whether a given set of objects is or is not a family. [References: 12]