Le 16/11/2022 à 10:05, Werner LEMBERG a écrit :
I draw my idea from LaTeX, for example handling multi-page tables (see the 'longtable' package).
I looked at the documentation (https://distrib-coffee.ipsl.jussieu.fr/pub/mirrors/ctan/macros/latex/required/tools/longtable.pdf). The footnote on the first page says The new algorithm for aligning ‘chunks’ of a table used in version 4 of this package was devised coded and documented by David Kastrup. LOL. Obviously, David will be able to comment better than me. But skimming the documentation of the package, it looked more like the package had to use this technique to work around the limitations of the extremely limited TeX programming environment than to implement a smart algorithm. Am I wrong here?
* In the first pass, typeset everything without stuff marked for a follow-up pass.
Namely, typeset all notes? But how do you take into account the constraints from lyrics here? That is the whole problem. ---- For what it's worth, the optimization problem can be formulated as a springs&rods problem: Add a problem variable for each lyric word. For each lyric word W, if C is W's column, add a rod from C to W to ensure W is not too far on the left of W. Also add a rod from W to C to ensure W does not go too far to the right. Add all other rods in the usual way (with skylines). Now rods may involve both column variables and lyric variables. Leave springs as they are (between columns only). Issue: this is not a springs&rods problem that the existing Simple_spacer will be able to solve (I didn't try, but I'm pretty sure). Simple_spacer's algorithm starts by stretching the line a lot, and iteratively compresses it. This implicitly assumes that stretching the line a lot will make rod constraints satisfied, i.e., there are no "reverse rods" (columns are ordered, and all rods are from a column to a column with a higher rank). The problems in the form above do have reverse rods. So the problem is essentially finding a method to solve springs&rods problems with this kind of reverse rods allowed. Now, springs&rods optimization is close to quadratic programming, which is well-studied, but in my understanding so far, it is not exactly quadratic programming (?) due to the fact that springs are allowed to have different strengths for stretching and compressing. Maybe one can find a different algorithm for Simple_spacer. Potentially, its start could be stretching the columns and putting each lyric word exactly on the column. Then what? That remains to be seen. Maybe one can adapt existing QP algorithms (caveat: a comment in simple-spacer.cc claims that it's "much simpler and much much faster than full-scale constrained QP"). Maybe there are papers that I haven't read that provide solutions or ideas for this problem. Maybe I am just being blind to an obvious solution, too. Another idea: instead of using two rods for describing the relationship between a lyric word and its column, use a spring with a somewhat large force, which allows lyrics to be completely "disconnected" from their column but makes it unlikely. I may well have said wrong things and I am not seeing clearly in the frame of the problem yet. Also, adding variables for lyrics would be a deep change in the C++ core. Jean
OpenPGP_signature
Description: OpenPGP digital signature
