Some time ago, I did some experiments on music line breaking algorithms
and finally I found a solution which was astonishingly easy to implement,
gave stable and nice looking results (as far as I tested it) and was
pretty fast. I didn't dig into the PMX source for finding out how it does
the job. Here's the outline of the idea [inspired by TeX's line breaking
algorithm (the way I understood it :-)]
* Quality of lines is given by
1) stretching or shrinking them as less as possible, best fit could be
sum of absolute differences or least square or any other method
2) neighboured lines should match, i.e.
a) their stretching shouldn't be too different, quantification as
above
b) outstanding symbols from the both lines should not come too close
or even crash into each other.
* Consider now bar n and all possible lines ending at this bar. Suppose
that we knew already for each line i out of these lines how to optimally
break the chunk from bar 1 to n under the condition that it ends with
that line i. Consider now all possible lines starting with bar n+1.
Using the information already collected about the lines ending at bar n
we may easily get the optimal break of the chunk bar 1 to m(j) where
m(j) is the end of the jth line starting at bar n+1 (got it? wow!).
* The rest is recursion and book keeping about line starts and ends.
* The advantages are:
- both cpu-time and memory consumption scale linearly with the number of
bars. In order to test the performance I tried it once with a score
containing about 700 bars and didn't notice a difference to trials of
just some pages.
- The algorithm can account for "soft" linebreaks, i.e. not only 'do
what you want/force here' but something inbetween like TeX's
\linebreak[n].
- It is easily extensible to page and even movement breaking.
- The method of how to find the "optimal solution" is rather easy
exchangable.
However, before having performed tests on a lot of other special
situations, I cannot tell anything quantitative about usability and
quality of results.
Bernhard
Bernhard Lang | Physical Chemistry Departement, Sciences II
21, Avenue du Denantou | University of Geneva; 30, Quai Ernest Ansermet
CH-1006 Lausanne, Suisse | CH-1211 Geneva 4, Switzerland
TEL/FAX: +41(0)21 601 3657 | TEL +41(0)22 702-6535, FAX -6518
email: [EMAIL PROTECTED]
_______________________________________________
TeX-music mailing list
[EMAIL PROTECTED]
http://sunsite.dk/mailman/listinfo/tex-music
