The computation of connected regions in interactive graphics

Abstract

This paper addresses the problem of automatically identifying and labeling the connected regions formed by sets of closed curves. This is a general problem encountered in interactive computer graphics, where an arbitrary pattern is transmitted via a digitizing device such as a data tablet and a stylus, or CRT and light pen. Area calculations for these connected regions are also briefly discussed. Two programmed algorithms are presented which accomplish these functions. The first operates on a completed pattern and is most efficiently applied to small patterns. The second is a dynamic generalization of the first. It permits segmentation of the original pattern and does identification and labeling of connected regions of any part of the pattern. It also permits modification of isolated parts of the pattern and accomplishes the necessary reidentification and relabeling. It is applicable to patterns which are many times the size of the original data tablet or screen. The paper also presents a specific application of this generalized algorithm to a problem requiring dynamic data handling.