Efficient flood filling (seed filling)
Following comments by @EvilJS which restarted a bibliographic search, here is relevant material that improves upon the initial algorithm by Alvy Ray Smith, which I called "scanline" in the OP.

It seems that the number of pixel visits was lowered from 2 to 1.5 in the worst case. It also seems that the minimum achievable rate depends on the topology of the filled area. The '85 article by Fishkin &amp; Barsky is the most theory-oriented resource.


Computer Graphics And Geometric Modelling : Implementation &amp; Algorithms
Max K. Agoston , Springer (2005), ISBN 10: 1852338180 ISBN 13: 9781852338183. See 2.4 Fill Algorithms.
Smith, A. Ray, Tint Fill, Computer Graphics, Vol 13, No 2, Aug 1979, 276-283 (SIGGRAPH 79 Conference Proceedings).
Fishkin, K.P., and Barsky, B.A., “An Analysis and Algorithm for Filling Propagation,” Proc. Graphics Interface 1985, 203–212.
Fishkin, Ken, “Filling a Region in a Frame Buffer,” in [Glas90], 278–284.
Heckbert, Paul S., “A Seed Fill Algorithm,” in [Glas90], 275–277.
[Glas90] is Glassner, A.S., editor, Graphics Gems, Academic Press, 1990.