Article layout device for automatically making layout of multi-column documents

• US 5,926,825 A
• Filed: 09/03/1996
• Issued: 07/20/1999
• Est. Priority Date: 08/31/1995
• Status: Expired due to Term

• Current Assignee: NEC Personal Computers, Ltd. (Lenovo Group Ltd.)
• Original Assignee: NEC Corporation
• Inventors: Shirakawa, Takahisa
• Primary Examiner(s): Feild, Joseph H.
• Application Number:
  US08/707,031
• Time in Patent Office: 1,050 Days
• Field of Search: 707/517-525
• US Class Current: 715/273
• CPC Class Codes: G06F 40/106 Display of layout of documents; Previewing

Abstract

An article layout device comprises a layout execute section which virtually sets rectangular columns on an area where documents are arranged and searches for an unused sole column or compound column until the columns are filled with articles or all articles are completely arranged to attain a layout result on articles which can be arranged; an article entry priority output section which outputs the entry priority of each article to be entered, as required; a layout result evaluation section which gives an evaluation value based on the entry priority of the article to each of a plurality of layout results determined by the layout execute section; and a best layout result retrieval section which selects the layout result having the best evaluation value given by the layout result evaluation section among the plurality of layout results determined by the layout execute section.

Claims

1. An article layout device for automatically making a layout of articles onto a multi-column document comprising:

layout means for generating multiple layout candidates for said articles, each layout candidate being generated by continually searching for an unused sole column or compound column from a column group list and arranging said articles sequentially onto said unused sole column or unused compound column until all columns from the column group list have been used or all of said articles having a size that will fit within said unused sole column or unused compound column have been arranged;

article priority output means for outputting a priority of each of said articles;

layout result evaluation means for giving an evaluation value to each layout candidate based on the entry priorities of the articles that have been arranged on said each layout candidate; and

best layout result retrieval means for selecting a layout candidate having the best evaluation value as the layout for said articles.

2. An article layout device as set forth in claim 1, wherein said layout means generates each layout candidate in accordance with a column structure and an article processing order, at least one of the column structure and the article processing order being different for each layout candidate.

3. An article layout device as set forth in claim 1, further comprising:

article form restriction information output means for outputting form restriction information on each article,

wherein said layout means generates each layout candidate in accordance with a column structure and an article processing order, at least one of the column structure and the article processing order being different for each layout candidate, and arranges an article onto the unused sole column or unused compound column only if the unused column or compound column meets the form restriction information on said article and it is judged that said article can be arranged in the unused column or compound column, in accordance with the article processing order from the first article in the article processing order until all of the columns from the column group list have been used or the last article in the article processing order has been processed.

4. An article layout device as set forth in claim 1,

wherein said layout means arranges the articles sequentially onto the unused sole column or unused compound column in accordance with an article processing order from the first article in the article processing order until all of the columns from the column group list have been used or the last article in the article processing order has been processed, and

wherein said layout means searches for the unused sole column or unused compound column from the column group list, wherein the column group list that has been determined in accordance with a column processing order.

5. An article layout device as set forth in claim 1, wherein said layout means searches for the unused sole column or unused compound column from the column group list that has been determined in accordance with a column processing order and arranges the articles sequentially onto the unused sole column or unused compound column in accordance with an article processing order from the first article in the article processing order until all of the columns from the column group list have been used or the last article in the article processing order has been processed.

6. An article layout device as set forth in claim 1, further comprising:

article form restriction information output means for outputting form restriction information on each article,

wherein said layout means generates each layout candidate in accordance with a column structure, an article processing order, and a column processing order, at least one of the column structure, the article processing order, and the column processing order being different for each layout candidate, and arranges an article onto the unused sole column or unused compound column only if the unused column or compound column meets the form restriction information on said article and it is judged that said article can be arranged in the unused sole column or unused compound column, in accordance with the article processing order from the first article in the article processing order until all of the columns from the column group list have been used or the last article in the article processing order has been processed.

7. An article layout device as set forth in claim 1, further comprising:

article form restriction information output means for outputting form restriction information on each article,

wherein said layout means comprises;

column production means for generating a plurality of columns in accordance with a column structure,

column candidate group generating means for producing the column group list from the plurality of columns in accordance with a column processing order,

allocation judging means for judging whether an article can be arranged onto the unused sole column or unused compound column from the column group list with reference to said article form restriction information, and

article layout processing means for searching for the unused sole column or unused compound column and arranging said articles sequentially in accordance with the article processing order from the first article in the article processing order until all of the columns from the column group list have been used or the last article in the article processing order has been processed.

8. An article layout device as set forth in claim 7, further comprising:

column split information generating means for producing the column structure;

column processing order generating means for producing the column processing order; and

article processing order generating means for producing the article processing order.

9. An article layout device as set forth in claim 1, wherein

said layout result evaluation means calculates for each layout candidate a ratio of empty areas on the layout area with respect to the whole layout area, and if said ratio exceeds a threshold value, decreases the evaluation value.

10. An article layout device as set forth in claim 1, wherein said layout result evaluation means calculates for each layout candidate a ratio of empty areas on the layout area with respect to the whole layout area, and decreases the evaluation value by a value corresponding to said ratio.

11. An article layout device for automatically making a layout of articles onto a multi-column document comprising:

column split information generating means for producing a column structure;

column processing order generating means for producing a column processing order;

article processing order generating means for producing an article processing order;

layout means for generating multiple layout candidates for said articles in accordance with the column structure, the article processing order, and the column processing order, at least one of the column structure, the article processing order, and the column processing order being different from for each layout candidate;

article priority output means for outputting a priority of each of said articles;

layout result evaluation means for giving the evaluation value to each layout candidate based on the entry priorities of the articles that have been arranged on said each layout candidate; and

best layout result retrieval means for selecting a layout candidate having the best evaluation value as the layout for said articles.

12. An article layout device as set forth in claim 11, further comprising:

article form restriction information output means for outputting form restriction information on each article;

wherein said layout means generates each layout candidate by searching for an unused sole column or unused compound column from a column group list that has been determined in accordance with the column structure and the column processing order and arranges said articles sequentially onto said sole column or compound column in accordance with the article processing order if it is judged that said article can be arranged in said column.

13. An article layout device as set forth in claim 11, further comprising:

article form restriction information output means for outputting form restriction information on each article;

wherein said layout means comprises column production means for generating a plurality of columns in accordance with the column structure;

column candidate group generating means for producing the column group list from the plurality of columns in accordance with the column processing order;

allocation judging means for judging whether an article can be arranged onto the unused sole column or unused compound column from the column group list with reference to said article form restriction information; and

article layout processing means for searching for the unused sole column or unused compound column and arranging said articles sequentially in accordance with the article processing order from the first article in the article processing order all of the columns from the column group list have been used or the last article in the article processing order has been processed.

14. A method of automatically laying out a plurality of articles on a multicolumn document area, said method comprising the steps of:

(a) assigning a priority to each of said articles;

(b) dividing the document area into a plurality of columns in accordance with a column structure;

(c) producing a column group list using the plurality of columns in accordance with a column processing order, wherein each entry in the column group list is either a sole column or a compound column;

(d) generating a layout candidate by arranging said articles sequentially onto an unused sole column or unused compound column from the column group list in accordance with an article processing order until all of said articles having a size that will fit within the unused sole column or unused compound column have been arranged;

(e) generating at least one more layout candidate by repeating at least one of steps (b), (c), and (d) using a different column structure, a different column processing order, or a different article processing order;

(f) evaluating each layout candidate based on the priority of the articles that were arranged on said document area to produce an evaluation result for the layout candidate; and

(g) selecting a best layout based on the evaluation results of the layout candidates.

15. A method as set forth in claim 14, wherein the step of evaluating includes the step of adjusting the evaluation result according to an amount of empty area present in the layout candidate.

16. A method as set forth in claim 14, further comprising the steps of inputting form restrictions for each article, wherein said articles are arranged sequentially onto the unused sole column or unused compound column subject to the form restrictions.

17. A method as set forth in claim 14, wherein the step of generating the layout candidates includes the step of judging, for each article to be arranged, whether a particular unused column or unused compound column is appropriate for that article, and if not, selecting another unused column or unused compound column from the column group list.

18. A method as set forth in claim 14, wherein the different column structure, the different column processing order, or the different article processing order is determined randomly.

19. A method as set forth in claim 14, wherein the step (c) of producing the column group list includes the steps of selecting as a first entry of the column group list, a sole column which is first in the column processing order, as a second entry of the column group list, a compound column including the sole column and one another column that is to the right or to the bottom of the sole column, and if there is no column that is to the right or to the bottom of the column that is first in the column processing order, selecting as the second entry of the column group list, a sole column which is second in the column processing order.

20. A method as set forth in claim 19, wherein the compound column of the column group list becomes used when any one column in the compound column becomes used.