1
$\begingroup$

Which is better, Flood Fill or Scanline Fill algorithm in computer graphics? My thoughts says that both of them has the same efficiency in term of time and space complexity. Maybe you guys have another thinking? Thanks

$\endgroup$
1
  • $\begingroup$ Do you mean the Smith's algorithm for flood fill or intersection with polygon edges? (the both are called Scanline Fill). Either way the efficiency differs vastly. $\endgroup$
    – Evil
    Jul 14, 2017 at 5:39

1 Answer 1

1
$\begingroup$

They have different purposes.

Flood fill implies that you have a graph with neighbours and a starting node. You need a data structure to hold the frontier of nodes you still have to fill (and possible one for all the nodes you have visited). But each node is visited exactly once.

Whereas the scanline implies that you have points in a coordinate system. Each point you visit may add new points of interest further along. You need a data structure to hold the sorted points.

$\endgroup$
1
  • $\begingroup$ It might be about Smith's scanline, then it is about lower worst case complexity. $\endgroup$
    – Evil
    Jul 14, 2017 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.