The use of a one-dimensional scanline and corner extensions to build two-dimensional geometric constraints in a shapes database.
Original Publication Date: 2004-Dec-14
Included in the Prior Art Database: 2004-Dec-14
Disclosed is a technique for discovering geometric relationships between shapes in the two-dimensional database. This technique uses one-dimensional scanline to construct a topological description of the data relative to the direction perpendicular to the scanline. It then uses the extension of previously viewed corners in combination with a shape-union data structure to build constraints in the direction parallel to the scanline, using information derived from relationships in the orthogonal direction. One embodiment of this idea describes how to form geometric constraints from the purpose of modeling design rules during VLSI layout optimization.