Layout apparatus for laying out objects in space and method thereof

Abstract

A layout system manages a designated layout space with a set of inscribed rectangles. Whenever an object is input, the layout system determines a layout position of the object in the layout space according to a designated priority rule. The layout system simulates the layout process for various conditions so as to optimize the layout of objects

1 . A layout apparatus laying out objects, comprising: 
 a storing unit storing a placement rule including information of a direction designated by a vector in a coordinate system for a layout space and specifying at least one layout position in the layout space; and    a layout unit in communication with the storing unit and generating an object layout result representing the objects laid out in the layout space by successively receiving, as an object, information of each object from an input unit in communication with the layout unit and for each object received from the input unit determining a layout position in the layout space by repeatedly applying the placement rule according to a priority order based on the placement rule and by repeatedly selecting a farthest position in the designated direction among positions in the layout space.    
     
     
         2 . The layout apparatus as set forth in  claim 1 , wherein said layout unit lays out a new object not overlapping with other objects that have been laid out and without need to move the other objects.  
     
     
         3 . The layout apparatus as set forth in  claim 1 , further comprising: 
 a space managing unit in communication with the layout unit and managing the layout space and laying out a designated object to a designated position, and    wherein said layout unit determines the layout position with reference to the layout space managed by said space managing unit and instructs said space managing unit to lay out the object received from the input unit as the designated object in the layout position as the designated position.    
     
     
         4 . The layout apparatus as set forth in  claim 3 , wherein said space managing unit manages the initial space composed of at least one closed figure surrounded by vertical sides and horizontal sides with a set of inscribed rectangles inside the closed figure, all sides of each of the inscribed rectangles partially congruent with corresponding sides of the closed figure, respectively, and treats as the layout space an area generated by excluding from the initial space a space of an object that has been laid out in the initial space.  
     
     
         5 . The layout apparatus as set forth in  claim 1 , 
 wherein said storing unit stores information of the initial space that is generated by replacing a figure of an arbitrary shape with a figure represented by vertical and horizontal sides with a predetermined accuracy, and    wherein said layout unit treats as the layout space an area generated by excluding from the initial space a space of an object that has been laid out in the initial space.    
     
     
         6 . The layout apparatus as set forth in  claim 1 , wherein said layout unit designates an initial space, lays out at least one object according to the placement rule at a predetermined position having highest priority, and lays out other objects according to the placement rule.  
     
     
         7 . The layout apparatus as set forth in  claim 1 , wherein said layout unit treats a blank area as an object to be laid out and lays out the blank area in the layout space generating a desired blank area in the object layout result.  
     
     
         8 . The layout apparatus as set forth in  claim 1 , wherein said layout unit attaches a blank area around an object generating a desired blank area in the object layout result.  
     
     
         9 . The layout apparatus as set forth in  claim 1 , wherein said layout unit treats a circumscribed rectangle of a generated object layout result as an object to be newly laid out and lays out the circumscribed rectangle in a new layout space generating a hierarchical two-dimensional layout.  
     
     
         10 . The layout apparatus as set forth in  claim 1 , 
 wherein said storing unit stores information of a main direction and a sub direction as the information of the direction, and    wherein if there are a plurality of farthest positions in the main direction, said layout unit lays out each object at a farthest position in the sub direction among the farthest positions in the main direction.    
     
     
         11 . A layout apparatus laying out objects in a layout space, comprising: 
 a storing unit storing a placement rule specifying at least one layout position in the layout space, the layout space corresponding to an initial space having corners at an initial state and the storing unit storing, as the placement rule one of the corners in the initial space and a position on the outer periphery thereof to specify a layout position; and    a layout unit in communication with the storing unit and generating an object layout result representing the objects laid out in the layout space by successively receiving, as an object, information of each object from an input unit in communication with the layout unit and for each object received from the input unit determining a layout position in the layout space by repeatedly applying the placement rule according to a priority order based on the placement rule, the layout unit using, as the priority order to select from among one or more layout positions, the criteria of laying out each object in the vicinity of the layout position.    
     
     
         12 . The layout apparatus as set forth in  claim 11 , wherein said storing unit stores as the placement rule a layout position with a short distance to one of the outer peripheral sides of the initial space and for each object determining the layout position according to a predetermined priority order of four corners and four sides when there are two or more layout positions with the same distance.  
     
     
         13 . The layout apparatus as set forth in  claim 11 , wherein said short distance is shortest normalized distance generated by normalizing a distance from one of outer peripheral sides of the initial space with a predetermined ratio in a vertical direction and a horizontal direction of the initial space, and for each object determining the layout position according to a predetermined priority order of the corners and sides of the initial space when there are two or more layout positions with the same normalized shortest distance.  
     
     
         14 . The layout apparatus as set forth in  claim 1 , 
 wherein said storing unit stores a rule for rotating the designated direction by a predetermined angle as the placement rule, and    wherein said layout unit lays out each object by determining the layout position of each object by repeatedly applying the rotated layout direction of the object according to a criteria of laying each object.    
     
     
         15 . The layout apparatus as set forth in  claim 1 , wherein said layout unit lays out each object in an available blank space in the designated direction.  
     
     
         16 . An analysis apparatus, comprising: 
 a storing unit storing a placement rule specifying at least one layout position in a layout space; and    an analyzing unit analyzing a layout result of objects in the layout space by generating a layout order of the objects that reproduces the layout result according to the placement rule by repeatedly extracting, using the layout result, the objects laid out in the layout space by applying the placement rule in a priority order based on the placement rule and laying out the objects in the layout space according to the placement rule applied to each object in the priority order.    
     
     
         17 . The analysis apparatus as set forth in  claim 16 , wherein said analyzing unit extracts the objects and blank areas in the layout result according to the placement rule and generates a layout order of the objects and the blank areas that reproduces the layout result.  
     
     
         18 . The analysis apparatus as set forth in  claim 17 , wherein said analyzing unit generates a layout order that reproduces a layout result of the objects, the layout result having least number of blank areas.  
     
     
         19 . The analysis apparatus as set forth in  claim 16 , wherein said analyzing unit generates the layout order which reproduces at least a part of the layout result.  
     
     
         20 . A layout evaluating apparatus designing a layout of objects, comprising: 
 an inputting unit successively inputting information of the objects;    a layout unit in communication with the inputting unit and generating a layout result representing the objects laid out in a layout space by repeatedly determining a layout position in the layout space according to a placement rule including information of a direction designated by a vector in a coordinate system for the layout space and specifying at least one layout position in the layout space, the placement rule applied in a priority order based on the placement rule for laying out each object in the layout space and a farthest position selected in the designated direction among positions in the layout space; and    an evaluating unit in communication with the layout unit and evaluating the layout result.    
     
     
         21 . The layout evaluating apparatus as set forth in  claim 20 , wherein said evaluating unit evaluates the layout result according to at least one of information of the entire size of the layout result, information of a layout position of a particular object, information of relative layout positions of two or more particular objects, information of a distribution of the layout of the objects, and information of a layout of blank spaces between the objects.  
     
     
         22 . A layout optimizing apparatus designing a layout of objects, comprising: 
 a storing unit storing a placement rule including information of a direction designated by a vector in a coordinate system for a layout space and specifying at least one layout position in the layout space;    an inputting unit successively inputting information of the objects; and    a layout unit in communication with the storing unit and the inputting unit and generating a layout result of the objects representing the objects laid out in the layout space by repeatedly for each object determining a layout position in the layout space by applying the placement rule according to a priority order based on the placement rule and by selecting a farthest position in the designated direction among positions in the layout space, the layout space generated by excluding from an initial layout space in which objects have been laid out, space of the objects laid out; and    an evaluating unit in communication with the layout unit and evaluating layout results generated by the layout unit by varying at least one of a layout order of the objects, the placement rule, and the initial layout space, and selecting a most compact layout result.    
     
     
         23 . The layout optimizing apparatus as set forth in  claim 22 , wherein said layout unit includes layout units generating layout results in parallel.  
     
     
         24 . The layout optimizing apparatus as set forth in  claim 22 , 
 wherein said storing unit stores placement rules; and    said layout unit generates one of the layout results according to one of the placement rules.    
     
     
         25 . The layout optimizing apparatus as set forth in  claim 22 , wherein said layout unit generates the layout results using initial spaces having different shapes or sizes.  
     
     
         26 . A layout optimizing apparatus designating a layout of objects, comprising: 
 a storing unit storing at least one placement rule including information of a direction designated by a vector in a coordinate system for a layout space and specifying at least one layout position in the layout space;    a layout unit in communication with the storing unit and generating an object layout result representing the objects laid out in the layout space by successively receiving, as an object, information of each object from an input unit in communication with the layout unit and for each object received from the input unit determining a layout position in the layout space by repeatedly applying the placement rule according to a priority order based on the placement rule and by repeatedly selecting a farthest position in the designated direction among positions in the layout space;    an evaluating unit evaluating the object layout result generated by said layout unit; and    a searching unit representing a layout order of objects as gene data, performing a genetic operation for a gene group including data of at least one gene according to a genetic algorithm, and obtaining a layout result corresponding to an obtained layout order.    
     
     
         27 . The layout optimizing apparatus as set forth in  claim 26 , wherein said searching unit further represents the priority rule for layout positions as the gene data and performs the genetic operation for the gene group.  
     
     
         28 . The layout optimizing apparatus as set forth in  claim 26 , wherein said searching unit further represents an orientation of an object as the gene data and performs the genetic operation for the gene group.  
     
     
         29 . A layout optimizing apparatus, comprising: 
 storing means for storing at least one placement rule for layout positions;    input means successively inputting information of objects;    layout means for generating an object layout result representing the objects laid out in a layout space by successively receiving, as an object, information of each object from the input means and for each object received from the input means designating a layout position of each object in the layout space according to the placement rule for layout positions every time information of each object is input;    evaluating means for evaluating a layout result generated by said layout means;    searching means for representing a layout order of objects as gene data, performing a genetic operation for a gene group including data of at least one gene according to a genetic algorithm, and automatically obtaining a layout result;    analyzing means for analyzing a layout result obtained by said layout means, and obtaining a predetermined layout order of objects reproducing the layout result by laying out the objects according to a predetermined placement rule for layout positions, and    wherein said searching means substitutes the predetermined layout order with the gene data and performs a process corresponding to the predetermined placement rule for layout position.    
     
     
         30 . The layout optimizing apparatus as set forth in  claim 29 , 
 wherein said analyzing means obtains a layout order which reproduces at least a part of the layout result obtained by said layout means according to the predetermined priority rule for layout positions, and    wherein said searching means substitutes the obtained layout order with the gene data.    
     
     
         31 . The layout optimizing apparatus as set forth in  claim 26 , wherein said searching unit exchanges order positions of two objects that are successively included in a layout order and have been randomly designated by performing the genetic operation for the gene data.  
     
     
         32 . The layout optimizing apparatus as set forth in  claim 26 , wherein said searching unit exchanges order positions of two objects each of which has been randomly designated by performing the genetic operation for the gene data.  
     
     
         33 . The layout optimizing apparatus as set forth in  claim 26 , wherein said searching unit moves objects at and after an order position that has been randomly designated in the gene data to a top position of the gene data by performing the genetic operation for the gene data.  
     
     
         34 . The layout optimizing apparatus as set forth in  claim 26 , wherein said searching unit selects one order position with respect to two genes and interchanges gene data of the two genes with respect to the selected order position by performing the genetic operation for the gene data.  
     
     
         35 . A computer-readable storage medium used to direct a computer and including a process of successively receiving information of objects and generating an object layout result representing layout of the objects in a layout space by determining a layout position of each object in the layout space according to a placement rule including information of a direction designated by a vector in a coordinate system for the layout space and specifying at least one layout position in the layout space, for each object the placement rule being applied repeatedly in a priority order based on the placement rule and a farthest position in the designated direction among positions in the layout space being selected.  
     
     
         36 . A computer-readable storage medium used to direct a computer to perform a process comprising: 
 representing an area of a two-dimensional space composed of at least one closed figure surrounded by vertical sides and horizontal sides with a set of inscribed rectangles inside the closed figure, all sides of each of the inscribed rectangles partially congruent with corresponding sides of the closed figure, respectively; and    managing the space with the set of inscribed rectangles by laying out a designated rectangular object in a designated position of the space, generating an area by excluding a rectangle of the rectangular object from the space, and representing the generated area with a set of inscribed rectangles.    
     
     
         37 . A computer-readable storage medium used to direct a computer to perform a process comprising: 
 analyzing a layout result of objects in a layout space; and    generating a layout order of the objects that reproduces the layout result layout position in the layout space by repeatedly laying out the objects according to a placement rule specifying at least one layout position in the layout space.    
     
     
         38 . A computer-readable storage medium used to direct a computer for designating a layout of a plurality of objects to perform a process comprising: 
 receiving successively information of the objects;    generating object layout results representing the objects laid out in a layout space by repeatedly determining a layout position in the layout space according to a placement rule including information of a direction designated by a vector in a coordinate system for the layout space and specifying at least one layout position in the layout space, for each object the placement rule being applied repeatedly in a priority order based on the placement rule and a farthest position in the designated direction among positions in the layout space being selected, and the layout space generated by excluding spaces of objects that have been laid out from an initial space; and    evaluating the object layout results by varying at least one of a layout order of the objects, the placement rule, and the initial space, so as to select one of the object layout results.    
     
     
         39 . A layout method designing a layout of objects, comprising: 
 receiving successively information of the objects; and    generating an object layout result representing the objects laid out in a layout space by repeatedly determining a layout position in the layout space according to a placement rule including information of a direction designated by a vector in a coordinate system for the layout space and specifying at least one layout position in the layout space, for each object the placement rule being applied repeatedly in a priority order based on the placement rule and a farthest position in the designated direction among positions in the layout space being selected.    
     
     
         40 . A space managing method, comprising: 
 representing an area of a two-dimensional space composed of at least one closed figure surrounded by vertical sides and horizontal sides with a set of inscribed rectangles inside the closed figure, all sides of each of the inscribed rectangles partially congruent with corresponding sides of the closed figure, respectively; and    managing the space with the set of inscribed rectangles by laying out a designated rectangular object in a designated position of the space, generating an area by excluding a rectangle of the rectangular object from the space, and representing the generated area with a set of inscribed rectangles.    
     
     
         41 . An analysis method, comprising: 
 analyzing a layout result of objects in a layout space; and    generating a layout order of the objects that reproduces the layout result by repeatedly laying out the objects in the layout space according to a placement rule specifying at least one layout position in the layout space.    
     
     
         42 . A layout optimizing method designing a layout of objects, comprising: 
 receiving successively information of the objects;    generating object layout results representing the objects laid out in a layout space by determining a layout position in the layout space according to a placement rule including information of a direction designated by a vector in a coordinate system for the layout space and specifying at least one layout position in the layout space, for each object the placement rule being applied repeatedly in a priority order based on the placement rule and a farthest position in the designated direction among positions in the layout space being selected, and the layout space being generated by excluding spaces of objects that have been laid out from an initial space;    varying at least one of a layout order of the objects, the placement rule, and the initial space; and    evaluating the object layout results to select one of the object layout results.    
     
     
         43 . A computer system laying out objects in an initial space, comprising: 
 a processor, successively receiving information of the objects, and to generate, using the information of the objects, an object layout result representing layout of each object in the initial space by repeatedly determining an area in the initial space as a layout space and determining a layout position of each object in the layout space without moving other objects in the initial space, the layout position being determined according to a placement rule including information of a direction designated by a vector in a coordinate system for the layout space and specifying at least one layout position in the layout space, for each object the placement rule being repeatedly applied according to a priority order based on the placement rule and the priority order being determined by selecting a closest position to the designated direction among positions in the layout space.    
     
     
         44 . A layout optimizing apparatus, comprising: 
 a storing unit storing at least one placement rule for layout positions;    an inputting unit in communication with the storing unit and successively inputting information of objects;    a layout unit in communication with the storing unit and generating an object layout result representing the objects laid out in the layout space by successively receiving, as an object, information of each object from the inputting device and for each object received from the inputting device determining a layout position of each object in the layout space according to the placement rule for layout positions every time information of each object is input;    an evaluating unit in communication with the layout unit and evaluating a layout result generated by said layout unit;    an analyzing unit in communication with the layout unit and analyzing a layout result generated by said layout unit, and obtaining a predetermined layout order of objects reproducing the layout result by laying out the objects according to a predetermined placement rule for layout positions; and    a searching unit in communication with the analyzing unit and searching a layout order of objects while varying the layout order by a probability operation according to a simulated annealing method, and obtaining a layout result by the probability operation, wherein the searching unit further searches for the predetermined layout order of the objects using the predetermined placement rule for layout positions.    
     
     
         45 . A layout optimizing apparatus, comprising: 
 a storing unit storing at least one placement rule for layout positions;    an inputting unit in communication with the storing unit and successively inputting information of objects;    a layout unit in communication with the storing unit and generating an object layout result representing the objects laid out in a layout space by successively receiving, as an object, information of each object from the inputting device and for each object received from the inputting device designating a layout position of each object in the layout space according to the placement rule for layout positions every time information each object is input;    an evaluating unit in communication with the layout unit and evaluating a layout result generated by said layout unit;    an analyzing unit in communication with the layout unit and analyzing a layout result generated by said layout unit, and obtaining a predetermined layout order of objects reproducing the layout result by laying out the objects according to a predetermined placement rule for layout positions; and    a searching unit in communication with the analyzing unit and representing a layout order of objects as gene data, performing a genetic operation for a gene group including data of at least one gene according to a genetic algorithm, and automatically obtaining a layout result, wherein the searching unit substitutes the standard layout order with the gene data and performs a process corresponding to the predetermined placement rule for layout position.