Algorithm for footnote layout with columns

I have implemented a basic page layout algorithm for footnote placement. Basically:

1. Layout a line of body text.
2. If it contains footnote references, lay out footnotes line by line.
3. Go to 1.

At every step, I check to see if the total height (body text + footnote text + gap) exceeds page height. If it does, I remove the most recently laid out line and the page is complete.

My question is: How do I deal with a situation where the body text is in two columns?

I would essentially need to know the total allowed body text height in advance in order to properly lay out the columns, but that cannot be known until I know the height of the footnote text.

I also can't just take the accumulated height of body text lines and divide by 2, due to varying line heights,开发者_运维百科 line spacing, paragraph spacing, etc.

You have 3 blocks – two for the columns and one for footnotes. Obviously (height of the column + height of the footnotes + gap) has to be lower than page height.

You can use your old algorithm for the first column. For the second column, when you add a footnote and it causes the first column to be too long, move lines from the end of the first column to the beginning of the second. If this makes the second column too long, move the line(s) back to the first column and remove the last footnote line.

Interesting problem. (Read: You ought to get more upvotes.)

How do I deal with a situation where the body text is in two columns?

I don't think there is a straight forward answer to that. The answer really depends on the aesthetic ideal that you set for your documents.

I would modify your algorithm only slightly so that:

• Primary content area is fixed for a given page
• Footnotes and friends wouldn't appear in the primary content area.

In that case, choose the amount of text that you can fit in a multi-column layout. Next, identify all footnotes in that section of the text. Renumber the footnotes (e.g. if you are squeezing in a couple of pages into one). Now, layout the footnotes in a single-column in the designated area.

Problems/questions:

• If the total text of the footnotes cannot be fit in the footnote section: From what I have seen you will probably need to carry over your footnote text on to the next page.

• Should your footnotes be multi-column? I have never seen a document where footnotes where multi-column but this is up to you.

• If there is a hard requirement that all footnote text should lie within the same page as the content that refers to it: You will need to figure out algorithmically (dynamic programming comes to mind) how much you can fit under the given page constraints, chuck the rest out, and layout only as much as you can and then fiddle with the text so that there isn't a lot of whitespace to bother the reader.