Efficient management of complex elements in physical IC design
F. Curatelli, M. Barzaghi, Giovanni Maria Bisio · 2002
An efficient data structure for the management of complex elements in physical design is described. The data structure is based on the use of low-level algorithms for the management of simple elements, such as rectangles and trapezoids. These algorithms constitute a generalization of those used for the management of the basic corner stitching data structure; the main enhancement is constituted by the possibility of managing simple elements with 45 degrees sides. At a higher level, a hierarchical structure is implemented which is able to manage more complex elements such as generic nonrectilinear polygons. This is performed by providing the user with a complete set of procedures for the creation and management of polygons. The algorithm is based on the decomposition of a polygon into a disjoint set of simple elements, managed through the use of the available low-level procedures.>