Hacker News
points by voidUpdate 2 days ago | 0 comments
How does this deal with one pixel gaps? The algorithm can enter it just fine but there's no space to go back out again, and there doesn't seem to be a system for backtracking, unless I've misunderstood the algorithm
[–] Jtsummers 2 days ago
It backtracks using the origin direction. As it traces back to the original starting pixel, before filling the current pixel it attempts to scan the remaining directions for each pixel (which may be none). If those lead to further pixels needing to be filled it'll start going forward again, and eventually hit a dead end and trace back to the branch point and continue to scan around it, eventually discovering is itself a dead end and go to its own predecessor.

Basically, a pixel will go through states like:

  (U,R) ;; came from up, went right
  (U,D) ;; came from up, went down
  (U,L) ;; came from up, went left
  (U,U) ;; came from up, went up
Each of the neighboring pixels will be checked (that last one is superfluous and could be skipped for efficiency). Once all have been checked the pixel will be filled, and the current pixel will be set by using its predecessor direction.
Hacker News