Editing Flood fill (section)

== Graph-theoretic filling ==

Some theorists applied explicit graph theory to the problem, treating spans of pixels, or aggregates of such, as nodes and studying their connectivity. The first published graph theory algorithm worked similarly to the span filling, above, but had a way to detect when it would duplicate filling of spans.<ref name="78Lieberman">{{Cite conference |title=How to Color in a Coloring Book |last=Lieberman |first=Henry |year=1978 |conference=SIGGRAPH '78: Proceedings of the 5th annual conference on Computer graphics and interactive techniques |pages=111–116 |doi=10.1145/800248.807380 }}</ref> Unfortunately, it had bugs that made it not complete some fills.<ref name="80Shani">{{Cite conference |title=Filling regions in binary raster images: A graph-theoretic approach |last=Shani |first=Uri |year=1980 |conference=SIGGRAPH '80: Proceedings of the 7th annual conference on Computer graphics and interactive techniques |pages=321–327 |doi=10.1145/800250.807511 }}</ref> A corrected algorithm was later published with a similar basis in graph theory; however, it alters the image as it goes along, to temporarily block off potential loops, complicating the programmatic interface.<ref name="80Shani" /> A later published algorithm depended on the boundary being distinct from everything else in the image and so isn't suitable for most uses;<ref name="81Pavlidis">{{Cite conference |title=Contour Filling in Raster Graphics |last=Pavlidis |first=Theo |year=1981 |conference=SIGGRAPH '81: Proceedings of the 8th annual conference on Computer graphics and interactive techniques |pages=29–36 |doi=10.1145/800224.806786 }}</ref><ref name="85Fishkin" /> it also requires an extra bit per pixel for bookkeeping.<ref name="85Fishkin" />

===Advantages===
* Suitable for pattern filling, directly, as it never retests filled pixels.<ref name="78Lieberman" /><ref name="80Shani" /><ref name="81Pavlidis" />
* Double the speed of the original span algorithm, for uncomplicated fills.<ref name="85Fishkin" />
* Access pattern is cache and bitplane-friendly.<ref name="82Levoy" /><ref name="85Fishkin" />

===Disadvantages===
* Regularly, a span has to be compared to every other 'front' in the queue, which significantly slows down complicated fills.<ref name="85Fishkin" />
* Switching back and forth between graph theoretic and pixel domains complicates understanding.
* The code is fairly complicated, increasing the chances of bugs.