bug-lilypond
[Top][All Lists]

## improved accidental algorithm (with images)

 From: Werner LEMBERG Subject: improved accidental algorithm (with images) Date: Thu, 25 Jul 2002 17:04:28 +0200 (CEST)

```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]

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