improved accidental algorithm

[Werner LEMBERG]

I think I've found an algorithm for the placement of accidentals in
piano music.  I checked many editions (mainly Breitkopf and Henle); of
course, there were some accidentals set differently (yielding more
compact results horizontally), but I didn't find serious deficiencies.

It works fine for up to 5 notes in a chord; this covers about 99% of
the chords in piano music, I think.  Non-repetitive chords with 6 or 7
notes will work well also in most cases (repetitive examples are <cis
dis fis cis' dis fis> or <cis dis eis b!' cis dis>).


  Preliminaries:

    The input order is the accidentals from top to down, subject to
    some reordering in rule 0.

    In the following, a `second' interval is counted only if the stem
    goes down.

    `Attaching' means to shift an accidental from the left to the
    right as much as possible (but still typographically correct),
    using a skyline/tile algorithm.  This includes moving an
    accidental nearer to the notes than accidentals above if possible;
    if the horizontal space is just a bit too small (say, 10 to 20
    percent) to place an accidental into a hole, the other accidentals
    should be moved to the left to increase the space.

  <0> Reordering rules.

      <0a> If the first three notes with accidentals are (from top to
           bottom) a second followed by a (real) second or third,
           exchange the second and third accidental.  Mark them to be
           processed in sequence in step <1>.

      <0b> If the last three notes with accidentals are (from bottom
           to top) a second followed by a third not followed by a
           second, exchange the lowest with the third-lowest
           accidental.  Mark them to be processed in sequence in step
           <3>.

      <0c> This subrule is executed only if neither <0a> nor <0b> has
           been applied.

           If there are five or more accidentals within the lowest
           octave of a chord, exchange the second-bottom with the
           third-bottom accidental.

  <1> Attach the first accidental (or the accidentals marked in <0a>).

  <2> Attach the accidentals one octave, two octaves, ... below.  Only
      executed for accidentals not marked by <0b>.

      <2a> Exception (only executed if <0c> hasn't been applied): If
           the accidental one octave ... below is part of a second
           which contains the lowest note of the chord, and where both
           notes have an accidental, and where no other second is in
           the chord, first attach the upper accidental, then the
           lower one.

  <3> Attach the last accidental (or the accidentals marked in <0b>).

      <3a> Exception (only executed if neither <0b> nor <0c> has been
           applied): If the accidental is part of a second where both
           notes have an accidental, first attach the upper
           accidental, then the lower one.

  <4> Attach accidentals which don't overlap vertically.

  Repeat this, starting with <1>, omitting steps <2a> and <3>, until
  input is exhausted.

[I can't produce images with LilyPond since it is apparently
impossible to shift a single accidental!  At least I couldn't find a
way to do it.]

In the following examples, I use e.g. (des' 1) to indicate where the
accidental is positioned horizontally; position 1 is nearest to the
chord.  Please use a note sheet to test the algorithm, otherwise it is
probably hard to understand.

  . <des e! g! des'> (stem down)

      <0a> doesn't fit; <0b> does.  So we start with <1>, producing
      (des' 1), followed by <3> which yields (g! 2), (e! 3), and
      (des 4).

  . <ces des fes g! ces> (stem up)

      <0a> and <0b> don't fit (there is no `second' if the stem goes
      up), but <0c> does, exchanging the processing order for des and
      fes.  <1> gives us the top accidental (ces 1).  <2> makes the
      lowest accidental (ces 1).  Then comes again <1> which produces
      (g! 2), followed by (des 3) -- due to reordering -- followed by
      (fes 4).

  . <f! bes c! d!> (stem down)

      <0a> fits.  <1> thus gives (d! 2), (bes 3), and (c! 4).  <3>
      finally produces (f! 1).

  . <a! b! d! f! a!> (stem down)

      <0b> fits.  <1> makes the top (a! 1), <3> makes (d! 2), (b! 3),
      and the bottom (a! 4).  Finally, <1> again makes (f! 5).

      The optimal solution is this something different: (a! 2) (a! 2)
      (f! 1) (d! 3) (b! 4).

  . <c! bes' e! as>

      <1> makes (as 1), <3> makes (c! 1), <4> produces (bes' 1), and
      <1> again gives (e! 2).


Usually, this algorithm should be applied for all notes which occur at
the same time in a staff; it makes sense to add an option to handle
chords grouped by stem direction (this should also cover the case
where a single stem connects notes from different staves).

I forgot to put Wanske's book into my travelling baggage -- can
someone please test my algorithm against her collected devils?

As soon as I know how to shift accidentals, I will provide images.


    Werner