Patent ID: 6161078
Filing Date: 2000-12-12
Classification: G06F

Abstract:
A computer implemented, graph based method of determining the orientation of objects which can assume a plurality of orientations relative to a default orientation, including being rotated 90.degree. clockwise, mirrored about an X axis, or mirrored about a Y axis, where the X axis and the Y axis are orthogonal to each other, and having a plurality of orientation constraints, including a fixed orientation constraint which requires an object to have one of eight predefined orientations, a same orientation constraint which requires that every object in a set of two or more objects must have the same orientation, a mirrored orientation constraint, which requires that a pair of objects have a mirrored orientation about the X axis or the Y axis, and a same or mirrored orientation constraint, which requires that every object in a set of two or more objects must have either the same orientation or the mirrored orientation, the method comprising the steps of:(a) building R, X and Y interference graphs, corresponding to a 90.degree. clockwise rotation operation, a mirror about the X axis operation, or a mirror about the Y axis operation, respectively, each of the R, X and Y interference graphs having a plurality of vertices and a plurality of edges, each object corresponding to one of the vertices in each of the R, X and Y interference graphs and each edge corresponding to a constraint between the objects represented by the vertices connected by the edge, two of the vertices being considered neighbors if connected by an edge, and with no neighbor vertices being allowed to have the same color;(b) then placing an intermediate vertex between each pair of vertices in each of the R, X and Y graphs which represent a pair of objects having a same constraint limitation and connecting each intermediate vertex by an edge with each vertex of the pair of vertices;(c) then placing an edge between each pair of vertices in one of the X graph or the Y graph which represent a pair of objects having a mirror constraint about either the X axis or the Y axis, respectively;(d) then coloring each vertex of each pair of objects having a fixed orientation constraint to either a first color indicative that no operation is to be performed or a second color indicative that a respective one of the 90.degree. clockwise rotation operation, the mirror about the X axis operation, or the mirror about the Y axis operation is to be performed, as may be required to implement the fixed orientation constraint relative to a default orientation and, if there are no vertices for objects having a fixed orientation, then coloring an arbitrary vertex as either the first color or the second color;(e) beginning from a vertex colored in step 1(d), sequentially coloring all of the remaining vertices with either the first color or the second color subject to the condition that no neighbor vertices are to have the same color;(f) for each colored vertex in the graphs R, X, and Y, not performing or performing on the object corresponding to that colored vertex, a 90.degree. clockwise rotation operation, a mirror about the X axis operation, and a mirror about the Y axis operation, respectively, depending upon whether that vertex is the first color or the second color, respectively.