Layout apparatus for laying out objects in space and method thereof

• US 6,374,200 B1
• Filed: 08/12/1997
• Issued: 04/16/2002
• Est. Priority Date: 02/03/1997
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Nakagawa, Toru
• Primary Examiner(s): Teska, Kevin J.
• Assistant Examiner(s): Jones, Hugh
• Application Number:
  US08/909,095
• Time in Patent Office: 1,708 Days
• Field of Search: 395/500.09, 395/500.1, 395/500.11, 703/8-10
• US Class Current: 703/8
• CPC Class Codes: G06F 40/106 Display of layout of documents; Previewing

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.

Claims

1. A space managing apparatus, comprising:

a space representing unit 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

a managing unit managing the closed figure by laying out a rectangular object in a designated position of the closed figure, generating a new closed figure in the closed figure by excluding from the closed figure a space of the rectangular object laid in the closed figure, and instructing said space representing unit to represent a space of the new closed figure area with a set of inscribed rectangles.

2. The space managing apparatus as set forth in claim 1, wherein said managing unit includes:

an adding unit adding a rectangle of an arbitrary size to an arbitrary position on a side of the closed figure; and

a removing unit removing a rectangle of an arbitrary size from an arbitrary position of the closed figure.

3. The space managing apparatus as set forth in claim 1, wherein said managing unit includes:

an adding unit adding to an arbitrary position on a side of the closed figure at least one closed figure surrounded by vertical sides and horizontal sides; and

a removing unit removing from an arbitrary position of the closed figure of the two-dimensional space at least one closed figure.

4. A layout optimizing apparatus designing 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 searching for 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.

5. The layout optimizing apparatus as set forth in claim 4, wherein said searching unit further searches for a placement rule while varying the placement rule.

6. The layout optimizing apparatus as set forth in claim 4, wherein said searching unit further searches for an orientation of an object with respect to the layout space while varying the orientation corresponding to an obtained layout order.

7. The layout optimizing apparatus as set forth in claim 4, wherein said searching unit exchanges order positions of two successive objects that have been randomly designated to vary the layout order.

8. The layout optimizing apparatus as set forth in claim 4, wherein said searching unit substitutes order positions of two objects each of which has been randomly designated to vary the layout order.

9. 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 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;

evaluating means for evaluating a layout result generated by said layout means;

searching means for searching a layout order of the objects while varying the layout order by a probability operation according to a simulated annealing method, and generating a layout result by the probability operation;

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 searches for the predetermined layout order of the objects using the predetermined placement rule for layout positions.

10. The layout optimizing apparatus as set forth in claim 9,

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 placement rule for layout positions, and

wherein said searching means searches for the layout order which reproduces at least a part of the layout result.