An improved and general approach to connected-component labeling of images is presented. The algorithm presented in this paper processes images in predetermined order , which means that the processing order depends only on the image representation scheme and not on specific properties of the image. The algorithm handles a wide variety of image representation schemes (rasters, run lengths, quadrees, bintrees, etc.). How to adapt the standard UNION-FIND algorithm to permit reuse of temporary labels is shown. This is done using a technique called age balancing , in which, when two labels are merged, the older label becomes the father of the younger label. This technique can be made to coexist with the more conventional rule of weight balancing , in which the label with more descendants becomes the father of the label with fewer descendants. Various image scanning orders are examined and classified. It is also shown that when the algorithm is specialized to a pixel array scanned in raster order, the total processing time is linear in the number of pixels. The linear-time processing time follows from a special property of the UNION-FIND algorithm, which may be of independent interest. This property states that under certain restrictions on the input, UNION-FIND runs in time linear in the number of FIND and UNION operations. Under these restrictions, linear-time performance can be achieved without resorting to the more complicated Gabow-Tarjan algorithm for disjoint set union.

An algorithm is presented to perform connected-component labeling of images of arbitrary dimension that are represented by a linear bintree. The bintree is a generalization of the quadtree data structure that enables dealing with images of arbitrary dimension. The linear bintree is a pointerless representation. The algorithm uses an active border which is represented by linked lists instead of arrays. This results in a significant reduction in the space requirements, thereby making it feasible to process three- and higher-dimensional images. Analysis of the execution time of the algorithm shows almost linear behavior with respect to the number of leaf nodes in the image, and empirical tests are in agreement. The algorithm can be modified easily to compute a (d-1)-dimensional boundary measure (e.g. perimeter in two dimensions and surface area in three dimensions) with linear performance.>

We present a global wiring algorithm used in a top-down physical design environment, i.e., macros are laid out after global wiring is done, and wires are allowed to pass through macros (the wiring-through model). The floorplan of the chip is in the form of a slicing structure. The algorithm is based on a hierarchical scheme. The final result is obtained through a series of refinement as the problem is recursively decomposed into a set of small-sized problems and then solved efficiently. The worst-case run-time for an arbitrary slicing tree (totally skewed) is O(M /sup 2/ N). When the floorplan is represented by a balanced slicing tree, the run-time of the overall algorithm is O(MN), where M is the number of macros and N the number of nets. The algorithm has been implemented in the C language and is used for chip designs. Experiments on both real and randomly generated designs show that the hierarchical router performs equally well as a flat global router in terms of wire length and wireability handling, but much faster in run-time (at least 10 times for an example with 100 macros and 1000 nets, and the gap being even larger for bigger-size problems).

A hidden surface algorithm is presented for viewing constructive solid geometry representations of solids (CSG trees) by converting them implicitly into a 3-d recursive spatial subdivision (bintree). The algorithm prunes the CSG tree to its minimal representation within each bintree block and does not evaluate it in regions of space (bintree nodes) that are totally hidden to the observer.

A discussion is presented of the relationship between two solid representation schemes: constructive solid geometry (CSG trees) and recursive spatial subdivision exemplified by the bintree, a generalization of the quadtree and octree. Detailed algorithms are developed and analyzed for evaluating CSG trees by bintree conversion, i.e., by determining explicitly which parts of space are solid and which empty. These techniques enable the addition of the time dimension and motion to the approximate analysis of CSG trees in a simple manner to solve problems such as dynamic interference detection. For "well-behaved" CSG trees, the execution time of the conversion algorithm is directly related to the spatial complexity of the object represented by the CSG tree (i.e., asymptotically it is proportional to the number of bintree nodes as the resolution increases). The set of well-behaved CSG trees includes all trees that define multidimensional polyhedra in a manner that does not give rise to tangential intersections at CSG tree nodes.

The region quadtree is a hierarchical data structure that finds use in applications such as image processing, computer graphics, pattern recognition, robotics, and cartography. In order to save space, a number of pointerless quadtree representations (termed linear quadtrees) have been proposed. One representation maintains the nodes in a list ordered according to a preorder traversal of the quadtree. Using such an image representation and a graph definition of a quadtree, a general algorithm to compute geometric image properties such as the perimeter, the Euler number, and the connected components of an image is developed and analyzed. The algorithm differs from the conventional approaches to images represented by quadtrees in that it does not make use of neighbor finding methods that require the location of a nearest common ancestor. Instead, it makes use of a staircase-like data structure to represent the blocks that have been already processed. The worst-case execution time of the algorithm, when used to compute the perimeter, is proportional to the number of leaf nodes in the quadtree, which is optimal. For an image of size 2n × 2n, the perimeter algorithm requires only four arrays of 2n positions each for working storage. This makes it well suited to processing linear quadtrees residing in secondary storage. Implementation experience has confirmed its superiority to existing approaches to computing geometric properties for images represented by quadtrees.

We present experiences and comparisons evaluating a fast algorithm for connected component labeling of quad- and octrees. The algorithm works without loss of efficiency on linear tree representations that may reside in external storage.

We present an algorithm for converting from the boundary representation of a solid to the corresponding octree model. The algorithm utilizes an efficient new connected components labeling technique. A novelty of the method is the demonstration that all processing can be performed directly on linear quad and octree encodings. We illustrate the use of the algorithm by an application to geometric mine modeling and verify its performance by analysis and practical experiments.

GWB/DMS is the data management subsystem of GWB, the Geometric Work-Bench. I t has been designed specifically for three-dimensional computeraided design applications. As the data definition and manipulation take place with extensions of high-level language constructs, GWB/DMS offers a direct migration from an independent "in-core" application to one using a database. Besides, the user can define additional access paths using geometric or conventional indices. The interactive nature of design is taken into account by including a simple transaction control mechanism. Transparency in ordinary programming and efficiency are the main design criteria of GWB/DMS. Its novelties are: 1) geometric indices facilitating access by location, 2) address calculation as the main access method and 3) tools for controlling the "physical closeness" of database objects.

Set operation algorithms form an important component of solid modeling systems. Their efficiency can be enhanced by localizing the search for geometric intersections to the region of overlap using a spatial directory. We present an algorithm that employs a three-dimensional extendible cell (EXCELL) directory to the set operation problem, and demonstrate by practical experiments the efficiency and the local nature of the algorithm.

The extendible cell (EXCELL) method provides a data structure for efficient geometric access. It stores geometric data into computer storage blocks corresponding to disjoint variable sized rectangular cells accessible by an address calculation type directory. We describe the method for point files and files of more complicated figures analyzing performance. We report algorithms for the nearest neighbour and point-in-polygon-network problems and describe applications to geographical data bases, hidden line elimination and geometric modeling.

We present a file organization scheme providing fast access to spatially referenced objects in a data base. The method utilizes a geometric file structure based on extendible cells together with a so-called topological representation of areas. It is shown to have O(1) expected access cost for the point-in-polygonnetwork-query in typical situations. The method can be used as a spatial directory to a data base. Performance indicators are reported.

Abstract The Extendible cell (EXCELL) method provides a data structure for efficient coordinate based access. It stores geometric data into computer storage blocks corresponding to disjoint variable sized rectangular cells accessible by an address calculation type directory. Two efficient hidden line algorithms utilizing an EXCELL structure are presented, both of which perform satisfactorily even if central memory is small compared to the total amount of data. The computation time is approximately proportional to the amount of input. An important aspect of the method is that the programs are contained within a “standard” general purpose graphics system.