improved accidental algorithm (with images)

[Werner LEMBERG]

Here my algorithm again, this time with images.

    Werner

======================================================================

  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.

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.

  . <d! eis gis d'!> (stem down) [chord1.png]

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

  . <ces des fes g! ces> (stem up) [chord2.png]

      <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) [chord3.png]

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

      LilyPond currently produces the same solution; anyway, the
      result has been achieved differently (I think); the lowest
      accidental has been added last; it should be moved into the
      `hole', shifting the upper accidentals to the left a bit.  I
      don't know whether LilyPond can do that...

  . <a! b! d! f! a!> (stem down) [chord4.png]

      <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> [chord5.png]

      <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).