Step by Step solution about How to resolve the algorithm Bitmap/Flood fill step by step in the Ruby programming language

The provided Ruby code implements a flood fill algorithm for a raster graphics image. Here's a detailed explanation:

Raster Graphics:

The RasterGraphics module, which is required at the beginning of the script, provides functionality for working with raster graphics images.

RGBColour Class:

The RGBColour class defines a simple color object with a == method to compare the color values of two instances.

Pixmap Class:

The Pixmap class represents a raster graphics image. It provides methods for drawing shapes, including lines and circles, and for performing image transformations.

Flood Fill Algorithm Implementation:

The flood_fill method in the Pixmap class implements the flood fill algorithm. It takes two arguments:

1. pixel: The pixel from which to start the fill.
2. new_colour: The color to fill the connected region with.

The algorithm works as follows:

1. It initializes a queue of pixels with the starting pixel.
2. It iterates over the queue until it's empty.
3. For each pixel in the queue, it checks if it has the same color as the pixel from which the fill started.
4. If the pixel has the same color, it draws a horizontal line from the westernmost border to the easternmost border of the connected region with the new color.
5. It then adds the pixels to the north and south of the current pixel to the queue if they have the same color.

Neighboring Pixels:

The neighbour method returns the pixel adjacent to the given pixel in a specified direction. The directions supported are north, south, east, and west.

Boundary Detection:

The find_border method finds the border of a connected region of pixels with a given color in a specified direction. It works by moving in the given direction until it encounters a pixel with a different color.

Usage of the Flood Fill Algorithm:

The script contains an example of using the flood fill algorithm on a bitmap image. It draws two circles on the image and then fills the area between the circles with a blue color. The filled image is then saved as a PNG file.

Processing Sketch Implementation:

The included Processing sketch provides a graphical user interface for interacting with the flood fill algorithm. It allows the user to load an image, click on it, and fill the connected region of pixels with a specified color.

Summary:

The provided Ruby code and Processing sketch demonstrate the implementation and use of a flood fill algorithm for raster graphics images. It allows you to fill connected regions of pixels with a specified color, and it's commonly used in image editing and graphics applications.

# frozen_string_literal: true

require_relative 'raster_graphics'

class RGBColour
  def ==(other)
    values == other.values
  end
end

class Pixmap
  def flood_fill(pixel, new_colour)
    current_colour = self[pixel.x, pixel.y]
    queue = Queue.new
    queue.enq(pixel)
    until queue.empty?
      p = queue.pop
      next unless self[p.x, p.y] == current_colour

      west = find_border(p, current_colour, :west)
      east = find_border(p, current_colour, :east)
      draw_line(west, east, new_colour)
      q = west
      while q.x <= east.x
        %i[north south].each do |direction|
          n = neighbour(q, direction)
          queue.enq(n) if self[n.x, n.y] == current_colour
        end
        q = neighbour(q, :east)
      end
    end
  end

  def neighbour(pixel, direction)
    case direction
    when :north then Pixel[pixel.x, pixel.y - 1]
    when :south then Pixel[pixel.x, pixel.y + 1]
    when :east  then Pixel[pixel.x + 1, pixel.y]
    when :west  then Pixel[pixel.x - 1, pixel.y]
    end
  end

  def find_border(pixel, colour, direction)
    nextp = neighbour(pixel, direction)
    while self[nextp.x, nextp.y] == colour
      pixel = nextp
      nextp = neighbour(pixel, direction)
    end
    pixel
  end
end

bitmap = Pixmap.new(300, 300)
bitmap.draw_circle(Pixel[149, 149], 120, RGBColour::BLACK)
bitmap.draw_circle(Pixel[200, 100], 40, RGBColour::BLACK)
bitmap.flood_fill(Pixel[140, 160], RGBColour::BLUE)
bitmap.save_as_png('flood_fill.png')


# holder for pixel coords
Pixel = Struct.new(:x, :y)

attr_reader :img, :fill_color, :queue, :value

def setup
  sketch_title 'Flood Fill'
  @img = load_image(data_path('image.png'))
  @fill_color = color(250, 0, 0)
end

def draw
  image(img, 0, 0, width, height)
  no_loop
end

def mouse_clicked
  img.load_pixels
  flood(mouse_x, mouse_y)
  img.update_pixels
  redraw
end

def flood(x, y)
  @queue = Queue.new
  queue.enq(Pixel.new(x, y))
  until queue.empty?
    pix = queue.pop
    next unless check(pix, color(255))

    queue.enq(Pixel.new(pix.x, pix.y - 1))
    queue.enq(Pixel.new(pix.x, pix.y + 1))
    queue.enq(Pixel.new(pix.x - 1, pix.y))
    queue.enq(Pixel.new(pix.x + 1, pix.y))
  end
end

def check(pix, target_color)
  unless (1...width).include?(pix.x) && (1...height).include?(pix.y)
    return false
  end

  value = img.pixels[pix.x + (pix.y * img.width)]
  return false if target_color != value

  img.pixels[pix.x + (pix.y * img.width)] = fill_color
  true
end

def settings
  size(256, 256)
end