Poor accidental layout on large / complex chords

Ick. I suspect this will turn out to be one or two unrelated issues, and it doesn't really relate to stacking per se as I'm talking about in this issue (which has to do with multiple accidentals). Would you mind posting this as a separate issue, and including the MSCZ file? Looks like the voice assignment is rather odd here - judging by the colors, I'm thinking you're forcing voice 1 stems down and voice 2 stems up? My code doesn't deliberately make assumption about which voices have which stem directions so I'm not saying that's why it doesn't work, but I want to be sure I'm reproducing your case correctly.

FWIW, I'm assuming the trigger will turn out to be the fact that there is a second and a unison conflict on the same note.

https://github.com/musescore/MuseScore/pull/782

Here are the results for the vtest I added for this:

It should be noted that no algorithm is ideal for all chords; there are some where this still does not do so well. But I think we've hit the point of diminishing returns.

FWIW, the fix that was just merged is actually better than what is shown above. Check out the further improved version of the bottom two chords (top two should be the same):

In case it isn't apparent, the leftmost accidentals that were otherwise kind of hanging off in space have been tucked in.

I'm thinking maybe our posts crossed - I actually fixed exactly those cases after submitting the PR but before it was merged:-).

I have found this whole experience fascinating, and I certainly welcome discussion.

Octaves are special, according to both Gould and Spreadbury, and should always be aligned where possible (and it pretty much always is). So we want notes an octave apart to be in the same column. The only question is whether or not we fit anything else along with them.

What I do now is first set up columns for the octaves to the right, with the columns themselves zig zagging (highest top note, then lowest bottom note, etc). If there are notes that have no octave match, I try to squeeze them into the existing columns (working right to left), and only ones I cannot squeeze in hang off to the left, using the same basic zig zag algorithm used for chords under an octave.

What has become clear from my investigation is that no single algorithm is going to yield optimal results always. If you haven't already, see http://blog.steinberg.net/accidental-stacking-comparison/ to get an idea of just how much variety these is between programs here. No program wins on all of chords used in the comparison, but pretty much all of the first five as a group are better than either of the last two as a group. MuseScore 1.3 is E, probably dead worst of the bunch.

Here's how we do now:

I'd say we're squarely in the group with the first five at this point, and that's good enough for me. Any "holes" you see here where it appears we could have fit another accidental in, there is just barely *not* enough room given the default style setting of forcing 0.22sp space between accidentals. If I reduce that to zero, I can plug the hole in the very last (bottom right) chord, but it's not an improvement overall.

Now, there *are* still opportunities for further improvement of course. There always are. For example, there are cases where the octave columns themselves can be combined - two accidentals an octave apart in one column, neither of which conflict with either of the accidentals an octave apart in another column. But detecting these opportunities would require quite a bit of looping and a whole bunch more floating point comparisons. And this actually won't happen in real life unless the accidentals in question are either double sharps or else if each column actually consists of accidentals that are actually *two* octaves apart. And the latter case isn't playable by a human being on any instrument I can think of :-). So it just isn't worth it, IMHO.

What you are showing here is a good example of the specific remaining opportunity for improvement I mentioned being possible but expensive to check for, and it would only pay off in cases too rate to worry about. That is, your circled accidentals are all in the octave columns themselves - they aren't the unmatched accidentals that I do insert into earlier columns where possible.

Yes, merging of the octave columns themselves would save space in this particular example, although I note we couldn't do it for *both* pairs of notes in your example - it would be one or the other. So we'd only save one column worth of space. And as I wrote, this only likely to work if the notes in each column are actually *two* octaves apart rather than one, which is indeed the case here. Furthermore, the notes between the columns have to basically be a seventh apart for it to be likely to work. And when you see there being opportunities to do this in many of the examples - that's actually not true if you want to keep the columns intact. That is, you might be able to merge one note of an octave pair into a different column, but you can't move them both in any of the Steinberg examples.

That said, I could see it happening in cases where both hands in a piano part are playing identical chords two octaves apart and for whatever reason, both hands are notated in one staff in separate voices. I don't know, I'll think about it. Maybe there would be a way to detect that type of situation without having to do an exhaustive set of comparisons of all notes in all columns. But I'm still betting not one chord in a thousand would end up benefiting from this.