Arranging components in a two-dimensional area

Abstract

A system for arranging components in a two-dimensional area includes a component preparation module for providing a set of components for arrangement, determining rectangular covers for each component, and ordering components according to a predefined order preference, and a core layout module for mapping components in order to positions in the arrangement with a first width and in a first direction, including: a row module for positioning components in order in a first full row across the first direction of the first width aligning one of the top or bottom sides of the covers of adjacent components until the next component does not fit in the first width, and a sub-row module for positioning components in any available space within the height of the first full row to form one or more sub-rows in the first direction and extending a distance less than the first width.

We claim: 
     
         1 . A system for arranging components in a two-dimensional area, comprising:
 a component preparation module for providing a set of components for arrangement, determining rectangular covers for each component, and ordering components according to a predefined order preference; and   a core layout module for mapping components in order to positions in the arrangement with a first width and in a first direction, comprising:
 a row module for positioning components in order in a first full row across the first direction of the first width aligning one of the top or bottom sides of the covers of adjacent components until the next component does not fit in the first width; and 
 a sub-row module for, before starting a next row, positioning components in any available space within the height of the first full row to form one or more sub-rows in the first direction and extending a distance less than the first width, 
   wherein if the top sides of the covers are aligned any sub-rows and full rows are below a previous row, if the bottom sides of the covers are aligned any sub-rows and full rows are above a previous row.   
     
     
         2 . The system as claimed in  claim 1 , wherein the core layout module comprises:
 a first justifying module for justifying components horizontally within a full row and within a sub-row.   
     
     
         3 . The system as claimed in  claim 1 , wherein the core layout module comprises:
 a second justifying module for justifying components vertically within a sub-row.   
     
     
         4 . The system as claimed in  claim 1 , further comprising:
 an optimization module for, once all the components are positioned, optimizing an arrangement quality by altering the height and width of the area.   
     
     
         5 . The system as claimed in  claim 4 , wherein the optimization module comprises:
 a measure of arrangement quality determining module for determining the measure of arrangement quality for the first width and the resultant height;   a width replacement module for replacing the first width with a new width and repeating the method of mapping the components; and   an iteration module for repeating the replacing of the width with a new width until an optimization of the arrangement quality is obtained.   
     
     
         6 . The system as claimed in  claim 1 , wherein the core layout module comprises:
 a rotating module for rotating components so that they align with the axes of the arrangement.   
     
     
         7 . The system as claimed in  claim 1 , wherein the core layout module comprises:
 a super-component module for:   applying the method for non-singleton components to display the non-singleton components in a rectangular region to create a super-component; and   applying the method to the super-component and the excluded singleton components to create a final arrangement.   
     
     
         8 . A method for arranging components in a two-dimensional area, comprising:
 providing a set of components for arrangement;   determining rectangular covers for each component;   ordering components according to a predefined order preference; and   mapping components in order to positions in the arrangement comprising:
 defining a first width of the area and a first direction across the width; 
 positioning components in order in a first full row across the first direction of the first width aligning one of the top or bottom sides of the covers of adjacent components until the next component does not fit in the first width; 
 before starting a next row, positioning components in any available space within the height of the first full row to form one or more sub-rows in the first direction and extending a distance less than the first width; and 
 repeating the steps of positioning components in a next full row and one or more sub-rows, until all components are positioned, 
   wherein if the top sides of the covers are aligned any sub-rows and full rows are below a previous row, if the bottom sides of the covers are aligned any sub-rows and full rows are above a previous row.   
     
     
         9 . The method as claimed in  claim 8 , wherein the first direction is left to right or right to left. 
     
     
         10 . The method as claimed in  claim 8 , comprising:
 justifying components horizontally within a full row and within a sub-row.   
     
     
         11 . The method as claimed in  claim 8 , comprising:
 justifying components vertically within a sub-row.   
     
     
         12 . The method as claimed in  claim 8 , comprising:
 once all the components are positioned, determining a measure of arrangement quality, and determining an optimization of the arrangement quality;   replacing the first width with a new width and repeating the method of mapping the components;   determining the new measure of arrangement quality; and   repeating the replacing of the width with a new width until an optimization of the arrangement quality is obtained.   
     
     
         13 . The method as claimed in  claim 8 , wherein the arrangement quality is one of the group of:
 an aspect ratio of the area;   a packing efficiency of the area;   a size of the area;   any other user-defined measure of arrangement quality.   
     
     
         14 . The method as claimed in  claim 8 , wherein the predefined order preference is one of the group of:
 decreasing order of vertex count;   decreasing order of component height;
 decreasing order of the greater of component height or component width; decreasing order of any user-defined component measure; 
 alphabetically by vertex label; by vertex type and label. 
   
     
     
         15 . The method as claimed in  claim 8 , wherein positioning components in any available space for one or more sub-rows comprises:
 positioning components in a sub-row; and   positioning components in a subsequent sub-row in any available space within a height of a previous sub-row.   
     
     
         16 . The method as claimed in  claim 8 , including:
 rotating components so that they align with the axes of the arrangement.   
     
     
         17 . The method as claimed in  claim 8 , including:
 applying the method for non-singleton components to display the non-singleton components in a rectangular region to create a super-component; and   applying the method to the super-component and the excluded singleton components to create a final arrangement.   
     
     
         18 . The method as claimed in  claim 8 , wherein positioning components in any available space within the height of the first full row to form one or more sub-rows in the first direction and extending a distance less than the first width comprises:
 determining candidate insertion points within a row or sub-row;   smoothing the insertion list; and   placing a next component in a sub-row at a first insertion point in which the component's height fits in the first direction.   
     
     
         19 . The method as claimed in  claim 18 , comprising positioning components in a subsequent sub-row comprising:
 updating the insertion list; and   placing a next component in a sub-row at a first insertion point in which the component's height fits in the first direction.   
     
     
         20 . A method for arranging components in a two-dimensional area, comprising:
 providing a set of components for arrangement;   determining rectangular covers for each component;   ordering components according to a predefined order preference; and   mapping components in order to positions in the arrangement comprising:
 defining a first height of the area and a first direction along the height; 
 positioning components in order in a first full column along the first direction of the first height aligning one of the left or right sides of the covers of adjacent components until the next component does not fit in the first height; 
 before starting a next column, positioning components in any available space within the width of the first full column to form one or more sub-columns in the first direction and extending a distance less than the first height; and 
 repeating the steps of positioning components in a next full column and one or more sub-columns, until all components are positioned, 
   wherein if the left sides of the covers are aligned any sub-columns and full columns are to the right of a previous column, if the right sides of the covers are aligned any sub-columns and full columns are to the left of a previous column.