Flood Fill Algorithm?

Snap! has a perfectly good Fill code block (available under the Pen block palette). However, areas filled using this code block evidently cannot be exported as SVG (scalable vector graphic) files (unless I'm missing something).

So, can anyone recommend an implementation of a Flood Fill algorithm in Snap! that fills an area by using the turtle to draw within an area enclosed by a bounded black outline? For example, here's the outline of a fish (on the left) that I would like to fill with color (in the manner shown in the image on the right):


I would then like to export the outline of the fish filled with color as an ".svg" file and reimport it to use as a sprite costume. Can anyone recommend a straightforward method for accomplishing this?

Note: I would like to do this using turtle drawing commands rather than in the paint editor. Tks

pen trails

Is your code drawing the picture in the first place? If so, keep a lot of turtle motion and use it to recapitulate the drawing.

In this instance, the figures were drawn with a marker on a sheet of paper, and then imported.

Oh. Maybe before importing you should fill those regions in Illustrator or Inkscape or something.

I could certainly use an external graphics program such as Inkscape to fill the figures. However, in this instance, several students are exploring the possibility of creating a paint program in Snap! They're aware that Snap! has a built-in paint editor, but they thought it might be fun to create their own version.

They have created their own version of a basic paint program in Snap!. (I suspect that this has likely been done many times before.) Now they are investigating the possibility of creating a Fill option in their Snap! paint program.

Their initial approach consisted of randomly positioning the turtle at various points in the area, and drawing a colored dot if the area under the turtle is not black. This method works, but is not very efficient.

On a completely different topic, I'm not aware of a cross-platform open source image editor that is comparable to Audacity for audio editing. Inkscape has the advantage of being free, but the learning curve is steep, especially for younger students. There have been quite a few really good image editors in the past - such as Picassa, for example - but the ones that I have used have been bought by large companies, left to languish without updates, and eventually taken off the market so that they're no longer available. If there's an open-source image editor that is both cross-platform and easy to use, I would love to have any recommendations that might be suggested.

GIMP is cross-platform, open-source and beginner-friendly.

In that case, does it have to be vector-based? If you're scanning in an image it's pixels anyway. And I think it's easier to design a floodfill algorithm than to find the edges and use polygonal fill.

I did this exercise once a long time ago (in Atari Logo!) and the basic algorithm was this:

  1. Determine the color under the turtle. Pixels that color are eligible for coloring.

  2. Go by horizontal lines. First fill the line where the turtle is, starting at the turtle position and moving left and right until you hit a different color.

  3. FIll the region above that line, one line at a time, until you run out of points to color. (For each line, you can start at any point in the region; for example, pick the midpoint of the colored region on the line you just filled.)

  4. Same for the region below the line.

I would implement and debug that much before continuing. All that's left is to deal with the (messy) case of a U-shaped region in which you start in one of the vertical parts, straightforwardly fill the area above the first line, and then start downward. The problem is that you have to notice an opportunity to reverse direction -- to scan upward from the height at which the two verticals come together.

(The program is in LogoWorks if you want to look it up.)

Perfect! This suggestion is exactly what is needed, and a good starting place. Thanks!

I just began exploring LogoWorks. What an incredible resource!

However, I did encounter a small snag. I can't seem to locate the power cord for my Atari. [grin]



The reason I had to program a fill program is that Atari software was delivered on 16K ROM cartridges, and that wasn't enough for Logo, so we had to leave things out. FILL has a high ration of code size to benefit.

What about a line follower algorithm. At Snapcon where was a session of "racer" challenge. Slightly modified car with few colorful sensor can trace over the line. Then after smoothing the polygon, canvas fill() can be used.