[Xmlgraphics-fop Wiki] Update of "TableLayout/KnuthElementsForTables/SteppingAlgorithmDerivation" by SimonPepping

[Apache Wiki <wi...@apache.org>]

Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Xmlgraphics-fop Wiki" for change notification.

The following page has been changed by SimonPepping:
http://wiki.apache.org/xmlgraphics-fop/TableLayout/KnuthElementsForTables/SteppingAlgorithmDerivation

New page:
== Derivation of the stepping algorithm ==

The stepping algorithm was devised by Luca Furini, and is described on
the page TableLayout/KnuthElementsForTables. On this page we show how
the algorithm can be derived.

We step through the table from one possible breakpoint to the
next. This algorithm specifies how to assign Knuth elements at each
possible breakpoint.

We define the following quantities:

 * `noBreakHeight` is the height without page breaks
 * `stepHeight-i` is the height before the page break at step ''i''
 * `maxRemainingHeight-i` is the height after the page break at step ''i''

 * `penaltyHeight-i` is the height of the penalty at step ''i''
 * `boxHeight-i` is the height of the box at step ''i''

 * `totalBoxHeight-i` = `Sum`(''j''=1 .. ''i'') `boxHeight-j`
 * `prevTotalBoxHeight-i` = `totalBoxHeight-(i-1)`
 * `prevMaxRemainingHeight-i` = `maxRemainingHeight-(i-1)`

Note that `maxRemainingHeight-0` = `noBreakHeight`.

The assigned Knuth boxes and penalties together make up the step
height:{{{
totalBoxHeight-i + penaltyHeight-i = stepHeight-i
}}}

The strategy of the algorithm is to split the step height between the
boxes and a penalty as follows: the penalty is equal to the extra
height that is caused by this page break. That is:{{{
penaltyHeight-i = stepHeight-i + maxRemainingHeight-i - noBreakHeight
}}}

Therefore: {{{
totalBoxHeight-i = noBreakHeight - maxRemainingHeight-i
}}}

This means that the total box height is that part of the no-break
height that at this step definitely appears before the page break.

The penalty height at each step can be calculated from the above
formula. The box height at each step can be calculated as follows:

{{{
boxHeight-i
	= totalBoxHeight-i - totalBoxHeight-(i-1)
	= noBreakHeight - maxRemainingHeight-i
	  - (noBreakHeight - maxRemainingHeight-(i-1))
	= maxRemainingHeight-(i-1) - maxRemainingHeight-i
	= prevMaxRemainingHeight-i - maxRemainingHeight-i
}}}

or as follows:

{{{
boxHeight-i + totalBoxHeight-(i-1)
	= noBreakHeight - maxRemainingHeight-i
=>
boxHeight-i
	= noBreakHeight - maxRemainingHeight-i - totalBoxHeight-(i-1)
	= noBreakHeight - maxRemainingHeight-i - prevTotalBoxHeight-i
}}}

The algorithm can also be derived by reverting the logic of the
derivation: The strategy of the algorithm is to split the step height
between the boxes and a penalty as follows: The total box height is
equal to that part of the height that definitively appears before the
page break. That is:{{{
totalBoxHeight-i = noBreakHeight - maxRemainingHeight-i
}}}

Therefore: {{{
penaltyHeight-i = stepHeight-i + maxRemainingHeight-i - noBreakHeight
}}}

---------------------------------------------------------------------
To unsubscribe, e-mail: fop-commits-unsubscribe@xmlgraphics.apache.org
For additional commands, e-mail: fop-commits-help@xmlgraphics.apache.org