Unit II Line and circle Drawing:

DDA line drawing algorithm, Bresenham’s Line algorithm, Circle and elipse generating
algorithms- Midpoint Circle Algorithm, Midpoint Elipse Algorithm, Polynomials and spline
curves, Filling-Filed - Area Primitives, Scan-Line Polygon File Algorithm, Inside-Outside
Tests, Scan-Line File of Curved Boundary Areas, Boundary-File Algorithm, Flood-File
Algorithm.
= = = = = = == = == = = == = = = = = = = = = = = = = = = = == = = = = = = = = = = = = =
DDA line drawing algorithm (Digital Differential Analyzer)
• DDA stands for Digital Differential Analyzer.
• It is scanning conversion method to draw line.
• DDA (Digital Differential Analyzer) is a line drawing algorithm used in computer
graphics to generate a line segment between two specified endpoints.
• It is a simple and efficient algorithm that works by using the incremental difference
between the x-coordinates and y-coordinates of the two endpoints to plot the line.
✓ To draw a line between A and B intermediate floating-point value is used. That is
intermediate pixel.
✓ The straight-line equation is 𝑦 = 𝑚𝑥 + 𝑏. Here 𝑚 is the slope.
✓ Line has two end points namely 𝐴(𝑥1 , 𝑦1 ) and 𝐵(𝑥2 , 𝑦2 ).
𝑦 −𝑦
✓ Slope of the line is 𝑚 = 2 1
𝑥2 −𝑥1
∆𝑦 𝑑𝑦
𝑚= or 𝑚 =
∆𝑥 𝑑𝑥
✓ That is the slope of the line is difference in y-coordinate and difference in x-coordinate.

✓ DDA algorithm is based on the calculation of value of ∆𝑥 and ∆𝑦 .

✓ Given line has slope +ve (𝑚 > 0) or -ve (𝑚 < 0). If +ve, the ∆𝑥 and ∆𝑦 values are

increased (𝑚 > 0) else ∆𝑥 and ∆𝑦 values are decreased (𝑚 < 0).

Case 1: If 𝒎 < 𝟏 Case 2: if 𝒎 = 𝟏 Case 3: if 𝒎 > 𝟏

1
𝑥𝑛 = 1 + 𝑥𝑛 𝑥𝑛 = 1 + 𝑥1 𝑥𝑛 = 𝑚 + 𝑥𝑛

𝑦𝑛 = 𝑚 + 𝑦𝑛 𝑦𝑛 = 1 + 𝑦1 𝑦𝑛 = 1 + 𝑦𝑛
Algorithm
Step 1: Consider one point of the line as (𝑋0 , 𝑌0 ) and the second point of the line as (𝑋𝑛 , 𝑌𝑛 ).

1
Step 2: Calculate ∆𝑥 , ∆𝑦 , 𝑚
∆𝑥 = 𝑋𝑛 − 𝑋0
∆𝑦 = 𝑌𝑛 − 𝑌0
∆𝑦
𝑚=
∆𝑥
Step 3: Depending upon absolute value of∆𝑥 , ∆𝑦 ; choose number of steps to put pixel
between start point and end point
𝑖𝑓 𝑎𝑏𝑠(∆𝑥 ) > 𝑎𝑏𝑠(∆𝑦 )

𝑠𝑡𝑒𝑝𝑠 = 𝑎𝑏𝑠(∆𝑥 )
𝑒𝑙𝑠𝑒
𝑠𝑡𝑒𝑝𝑠 = 𝑎𝑏𝑠(∆𝑦 )

Step 4: current point is (𝑥𝑝 , 𝑦𝑝 ) and next point is (𝑥𝑝+1 , 𝑦𝑝+1 )

Find the next point by following 3 cases:
Case 1: If 𝒎 < 𝟏 Case 2: if 𝒎 = 𝟏 Case 2: if 𝒎 > 𝟏
1
𝑥𝑝+1 = 1 + 𝑥𝑝 𝑥𝑝+1 = 1 + 𝑥𝑝 𝑥𝑝+1 = 𝑚 + 𝑥𝑝

𝑦𝑝+1 = 𝑚 + 𝑦𝑝 𝑦𝑝+1 = 1 + 𝑦𝑝 𝑦𝑝+1 = 1 + 𝑦𝑝

Step 5: Repeat Step 4 until it reaches end -point.
The DDA algorithm is faster than the direct use of the line equation since it calculates points
on the line without any floating-point multiplication.
Example:
Start point (5,6) and End point (8,12)

∆𝑥 = 𝑋𝑛 − 𝑋0 ⟹8−5=3

∆𝑦 = 𝑌𝑛 − 𝑌0 ⟹ 12 − 6 = 6

∆𝑦 6
𝑚= ⟹ =2
∆𝑥 3

Therefore 𝑚 =2
Choose number of steps to put pixel between start point and end point
Therefore 𝑎𝑏𝑠(∆𝑥 ) < 𝑎𝑏𝑠(∆𝑦 ) = 3 < 6

2
𝑆𝑡𝑒𝑝𝑠 = ∆𝑦 = 6
As 𝑚 > 1; Case 3 is satisfied,
1
𝑥𝑝+1 = 𝑚 + 𝑥𝑝

𝑦𝑝+1 = 1 + 𝑦𝑝
𝑥0 , 𝑦0 𝑥𝑝+1 𝑦𝑝+1 Round off
5,6 5.5 7 6,7

Example 2

The coordinates of drawn line areP1 = (2, 8)

P2 = (3, 9)
P3 = (4, 10)
P4 = (5, 11)
3
P5 = (6, 12)
P6 = (7, 13)
P7 = (8, 14)
P8 = (9, 15)
P9 = (10, 16)
P10 = (11, 17)

Advantages of DDA Algorithm

1. Itis the simplest algorithm and it does not require special skills for implementation.
2. It is a faster method for calculating pixel positions than the direct use of equation
𝑦 = 𝑚𝑥 + 𝑏.
3. It eliminates the multiplication in the equation by making use of raster characteristics,
so that appropriate increments are applied in the x or v direction to find the pixel
positions along the line path.
Disadvantages of DDA Algorithm
1. Floating point arithmetic in DDA algorithm is still time-consuming.
2. The algorithm is orientation dependent. Hence endpoint accuracy is poor

= = = = = = = = = == = = = = = = = = = = == = = = = = = = = = = = = = = = = = = = = = =

Bresenham’s Line algorithm

It determines the point of n-dimensional raster that should be selected in order to form a close
approximation towards a straight line between two points. Line has two end points namely
𝐴(𝑥1 , 𝑦1 ) and 𝐵(𝑥2 , 𝑦2 ). It is efficient because it only performed integer addition, integer
subtraction and integer multiplication operation. These operations performed rapidly so the
lines can be generated quickly.
Algorithm
Step 1: Consider one point of the line as (𝑋0 , 𝑌0 ) and the second point of the line as (𝑋𝑛 , 𝑌𝑛 ).

Step 2: Calculate ∆𝑥 , ∆𝑦

∆𝑥 = 𝑋𝑛 − 𝑋0
∆𝑦 = 𝑌𝑛 − 𝑌0
Step 3: Calculate the decision parameter (to find exact point to draw a line)
𝑝𝑘 = 2∆𝑦 − ∆𝑥

4
Step 4: Suppose the current point is (𝑥𝑘 , 𝑦𝑘 ) and the next point is (𝑥𝑘+1 , 𝑦𝑘+1 ). To find the
next point depending on value of decision parameter 𝑝𝑘 .
Case 1: if 𝑝𝑘 < 0; 𝑝𝑘+1 = 𝑝𝑘 + 2∆𝑦 (next decision parameter)
𝑥𝑘+1 = 𝑥𝑘 + 1
𝑦𝑘+1 = 𝑦𝑘
Case 2: if 𝑝𝑘 ≥ 0; the next decision parameter is: ; 𝑝𝑘+1 = 𝑝𝑘 + 2∆𝑦 − 2∆𝑥
𝑥𝑘+1 = 𝑥𝑘 + 1
𝑦𝑘+1 = 𝑦𝑘 + 1
Step 5: Repeat Step 4 until end point is reached.
Example
Step 1: Start coordinate value (𝑋0 , 𝑌0 ) = (9,18) and End point(𝑋𝑛 , 𝑌𝑛 ) = (14,22)

Step 2: Calculate ∆𝑥 , ∆𝑦

∆𝑥 = 𝑋𝑛 − 𝑋0 ⟹ 14 − 9 = 5

∆𝑦 = 𝑌𝑛 − 𝑌0 ⟹ 22 − 18 = 4

Step 3: Calculate the decision parameter

𝑝𝑘 = 2∆𝑦 − ∆𝑥 ⟹ 2 ∗ 4 − 5 = 3

Now 𝑝𝑘 = 3
Step 4: 𝑝𝑘 = 3 is 𝑝𝑘 ≥ 0; Case 2 is satisfied
𝑝𝑘+1 = 𝑝𝑘 + 2∆𝑦 − 2∆𝑥
=3+2∗4−2∗5
= 11 − 10 = 1
𝑥𝑘+1 = 𝑥𝑘 + 1 ⟹ 9 + 1 = 10 // starting x-coordinate value
𝑦𝑘+1 = 𝑦𝑘 + 1 ⟹ 18 + 1 = 19 // starting y-coordinate value
Repeat Step 4; do process no 2
𝑝𝑘 = 1 is 𝑝𝑘 ≥ 0; Case 2 is satisfied
𝑝𝑘+1 = 𝑝𝑘 + 2∆𝑦 − 2∆𝑥
=1+2∗4−2∗5
= 9 − 10 = −1

5
𝑥𝑘+1 = 𝑥𝑘 + 1 ⟹ 10 + 1 = 11 // 10 is present x-coordinate value
𝑦𝑘+1 = 𝑦𝑘 + 1 ⟹ 19 + 1 = 20 // 19 is present y-coordinate value
Repeat Step 4; do process no 3
𝑝𝑘 = 1 is 𝑝𝑘 < 0; Case 1 is satisfied
𝑝𝑘+1 = 𝑝𝑘 + 2∆𝑦
= −1 + 2 ∗ 4 = 7
𝑥𝑘+1 = 𝑥𝑘 + 1
= 11 + 1 = 12
𝑦𝑘+1 = 𝑦𝑘 =20
Repeat Step 4; do process no 4
𝑝𝑘 = 7 is 𝑝𝑘 ≥ 0; Case 2 is satisfied
𝑝𝑘+1 = 𝑝𝑘 + 2∆𝑦 − 2∆𝑥
=7+2∗4−2∗5
= 15 − 10 = 5
𝑥𝑘+1 = 𝑥𝑘 + 1 ⟹ 12 + 1 = 13 // 12 is present x-coordinate value
𝑦𝑘+1 = 𝑦𝑘 + 1 ⟹ 20 + 1 = 21 // 20 is present y-coordinate value
Repeat Step 4; do process no 5
𝑝𝑘 = 5 is 𝑝𝑘 ≥ 0; Case 2 is satisfied
𝑝𝑘+1 = 𝑝𝑘 + 2∆𝑦 − 2∆𝑥
=5+2∗4−2∗5
= 13 − 10 = 3
𝑥𝑘+1 = 𝑥𝑘 + 1 ⟹ 13 + 1 = 14 //13 is present x-coordinate value
𝑦𝑘+1 = 𝑦𝑘 + 1 ⟹ 21 + 1 = 22 // 21 is present y-coordinate value

Process no 𝑝𝑘 𝑝𝑘+1 𝑥𝑘+1 𝑦𝑘+1

Initial 9 18
1 3 1 10 19

6
 2 1 -1 11 20
3 -1 7 12 20
4 7 5 13 21
5 5 3 14 22

= = = = = = = = = == = = = = = = = = = = == = = = = = = = = = = = = = = = = = = = = = =

Midpoint Circle Algorithm

Introduction
We all know that a circle is defined by its centre and radius. It is not easy to display an arc on
the computer screen, because the screen is made up of pixels which are organized in the form
of matrix. So, for drawing a circle on screen we need to consider the nearest pixels from a
printed pixel. The main property of circle is its symmetry, we have to find points of circle only
for one octant, the other octants can be derived easily. Let's consider a circle and divide into 8
octants on 2D plane, We are going to calculate pixel locations for the octant x=0 to x=y. 2
octant is equal to 1 quadrant.

Mid-Point Circle Drawing Algorithm:

• Midpoint circle algorithm is used to determine the points needed for rasterizing a circle.
• It calculates all the perimeter points of the circle in the first octant and then print them
along with their mirror points in the other octants.

7
Algorithm:
Step 1: Consider a center coordinate (𝑥, 𝑦) as
𝑥=0
𝑦 = 𝑟 // r- radius
Therefore initial point (𝑥, 𝑦) is (0, 𝑟)
Step 2: Calculate the starting decision parameter 𝑝:
𝑝 = 1 − 𝑟;
Step 3: Case 1:
If 𝑝 < 0
then (𝑥𝑘 , 𝑦𝑘 ) = (𝑥 + 1, 𝑦)
𝑝 = 𝑝 + 2𝑥 + 3
Case 2:
If 𝑝 ≥ 0,
then (𝑥𝑘 , 𝑦𝑘 ) = (𝑥 + 1, 𝑦 − 1)
𝑝𝐾 = 𝑝 + 2(𝑥 − 𝑦) + 5
Step 5: If the center coordinate point (𝑋1 , 𝑌1 ) is not at the origin (0, 0) Then finding the points
as follow:
For x coordinate = 𝑋𝑐 + 𝑋1 ;
For y coordinate = 𝑌𝑐 + 𝑌1 {𝑋𝑐 and 𝑌𝑐 contains the current values of X and Y}
Step 6: Repeat step 4 and 5 till we get 𝑋 ≥ 𝑌
Advantages of midpoint circle drawing algorithm:
• It is an efficient algorithm.
• It is easy to implement.
• It is used to create curves on a raster display.

8
Disadvantages of midpoint circle drawing algorithm:
• Time-consuming algorithm.
• Sometimes the points of the circle are not accurate.
Example:

= = = = = === = = = = = = = = = = = = = = = = = = = = = = = = = = = == = = = = = = = = =

Midpoint Ellipse Drawing Algorithm

• Midpoint ellipse algorithm is a method for drawing ellipses in computer graphics.
• This method is modified from Bresenham’s algorithm.
• The advantage of this modified method is that only addition operations are required
in the program loops. This leads to simple and fast implementation in all processors.
• Let us consider one quarter of an ellipse.
• The curve is divided into two regions.
• In region I, the slope on the curve is greater than –1 while in region II the slope on
the curve is less than –1.
• The center of the ellipse at (0,0)
• To draw an ellipse, we will solve the algorithm for the first quadrant.
• Points on other coordinate will be mirrored from the first quadrant.

9
The equation of ellipse is

where 𝑟𝑥2 is the horizontal radius and 𝑟𝑦2 is the vertical radius, we can define an function
𝑓𝑒𝑙𝑙𝑖𝑝𝑠𝑒 (𝑥, 𝑦)

Starting at (0, 𝑟𝑦 ) (0, ry) we take unit steps in the x direction until we reach the boundary
between region 1 and region 2. Then we take unit steps in the y direction over the remainder
of the curve in the first quadrant.
𝑑𝑦
𝑆𝑙𝑜𝑝𝑒 = = −1 = 2𝑟𝑦2 𝑥 = 2𝑟𝑥2 𝑦
𝑑𝑥
therefore, we move out of region 1 whenever 2𝑟𝑦2 𝑥 ≥ 2𝑟𝑥2 𝑦

10
Decision parameter for region 1

Decision parameters are incremented by:

11
Region 2
Over region 2, step in the negative y direction and midpoint is taken between horizontal pixels
at each step.

Decision parameter of region 2

12
13
14
= = = = = === = = = = = = = = = = = = = = = = = = = = = = = = = = = == = = = = = = = = =

Polynomials and spline curves

In computer graphics, we often need to draw different types of objects onto the screen. Objects
are not flat all the time and we need to draw curves many times to draw an object. A curve is
an infinitely large set of points. Each point has two neighbours except endpoints. Polynomials
and spline curves play crucial roles in computer graphics, particularly in representing and
manipulating curves and surfaces.
Polynomial Curves
• Polynomial curves are represented by polynomial equations of one variable (usually
denoted as 𝑡).
• The simplest form of polynomial curves is the Bézier curve, which is widely used
due to its simplicity and versatility.

15
 • Bézier curves are defined by a set of control points and are evaluated using Bernstein
polynomials.
• They are used extensively in 2D and 3D graphics for shape design and animation.
• Higher-degree polynomial curves, such as B-splines (Basis splines), offer more
control and flexibility over curve shape. They are used in applications where finer
control over curvature and continuity is required.

Bezier Curves
• Bezier curves are widely used in computer graphics for drawing smooth curves
between control points.
• These curves are defined by a set of control points, and the curve itself lies within the
convex hull of these points.

P1,p2,p3,p4 are control points. curve is drawn between p1 and p4 with a support of p2
and p3.
• P2 and p3 points are not always in the curve. But it presents some distance from the
curve.
• Bezier curves are easy to compute and offer intuitive control over the shape of the curve.
• Bezier curve is discovered by the French engineer Pierre Bézier.
• These curves can be generated under the control of other points. so it is global control.
That is degree of polynomial depends on control point.
• The simplest Bézier curve is the straight line from the point P0 to P1.
• A quadratic Bezier curve is determined by three control points.
• A cubic Bezier curve is determined by four control points.

16
 • The curve order equals the 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑝𝑜𝑖𝑛𝑡𝑠 − 1.
Simple curve or linear curve
• The simplest Bézier curve is the straight line from the point P0 to P1. It contains 2
control points.
• A quadratic Bezier curve or parabolic curve is determined by three control points.
degree is 2. That is 𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐𝑜𝑛𝑡𝑟𝑜𝑙 𝑝𝑜𝑖𝑛𝑡𝑠 − 1. That is 3 − 1 = 2.
• A cubic Bezier curve is determined by four control points. The degree is 3.
𝑛𝑢𝑚𝑏𝑒𝑟 𝑜𝑓 𝑐𝑜𝑛𝑡𝑟𝑜𝑙 𝑝𝑜𝑖𝑛𝑡𝑠 − 1. That is 4 − 1 = 3.

In this curve, the starting point p1 and ending point p4 are called as anchors. p2, p3 are
called as handles.

Properties of Bezier curve

• They always pass through the first and last control points.
• They are contained in the convex hull of their defining control points. (convex hull
means boundary around the control point)

17
 • The degree of the polynomial in defining the curve segment is one less than the number
of defining polygon point.
• The shape of defining polygon is usually followed by Bezier Curve
• Bezier Curves are tangent to then first & last Edges of control polyline.
• Bezier Curves Exhibit global control point alters the shape of whole curve.
Mathematical representation of Bezier Curve
• Bezier Curve’s function is called as blending function or basis function.
• Approximate tangents by using control points are used to generate curve.
• The Bezier curve can be represented mathematically as –
𝑛

∑ 𝑃𝑖 𝐵𝑖𝑛 (𝑡)
𝐾=0

Where 0 ≤ 𝑡 ≤ 1,
𝑃𝑖 is the set of points and 𝐵𝑖𝑛 (𝑡) represents the Bernstein polynomials which are given
𝑛
by 𝐵𝑖𝑛 (𝑡) = ( ) (1 − 𝑡)𝑛−𝑖 𝑡 𝑖
𝑖
Where 𝑛 is the polynomial degree, 𝑖 is the index and 𝑡 is the variable.

B-Spline Curves:
• B-spline curves are another important class of curves used in computer graphics.
• They offer more flexibility than Bezier curves, allowing for smoother curves and local
control.
• Local control means that, it does not depend on control points.
• But it depends on order of the polynomial. That is if the order of control point changes
if affects that portion only not whole structure of the curve.
• B-splines are defined by a set of control points and a set of basis functions.
• They are widely used in modeling and animation applications.

18
Properties
• The sum of B-Spline basis function at any parameters ′𝑢′ equal to 1.
i.e ∑𝑛+1
𝑖=1 𝑁𝑖 𝑘 (𝑢) = 1

𝑛 + 1 is the number of control point

𝑘 is the order of B-Spline curve
• The basis function is +ve or zero for all parameter values. i.e 𝑁𝑖 𝑘 (𝑢) ≥ 0. Except for
𝑘 = 1. Each basis function has one maximum value.
• The maximum order of the curve is equal to the number of vertices of defining polygon.
• The degree of B-Spline polynomial is independent on the number of vertices of
defining polygon.
• B-Spline allow the control (i.e local Control points) over the curve surface.
• The curve lies within the convex hull of its defining polygon.
A B-spline curve is defined as a linear combination of control points Pi and B-spline basis
function Ni, k t given by
𝑛

𝑐(𝑡) = ∑ 𝑃𝑖 𝑁𝑖,𝑘 (𝑡), 𝑛 ≥ 𝑘 − 1, 𝑡 ∈ [𝑡𝑘 − 1, 𝑡𝑛 + 1]

𝑖=0

Where,
𝑃𝑖 , 𝑖 = 0,1,2, … , 𝑛 are the control points
𝑘 is the order of polynomial segments of the B-spline curve. Order k means that the curve is
made up of piecewise polynomial segments of degree k - 1,
𝑁𝑖,𝑘 (𝑡) are the “normalized B-spline blending functions”. They are described by the order k
and by a non-decreasing sequence of real numbers normally called the “knot sequence”.
= = = = = == = = = = = == = = = = = = = = = = == = = = = = = = = = = = = = == ======

Filling-Filed

19
 • In computer graphics, the term "filling" or "filling algorithm" typically refers to the
process of determining which pixels or regions should be colored or shaded to create a
solid area, often within the boundaries of a defined shape.
• "Filled" or "filling" algorithms are commonly used in rendering and drawing to fill
closed shapes, such as polygons or curves, with a specific color or pattern.
• Polygon is a closed figure made up of the line segment on 2D plane.
• The word “poly” means “many” and “gons” means sides.
• So polygon is a close shape having many sides.
Example: Square, Triangle, hexagon etc
Types of Polygon Filling Algorithm
The closed shape made up of the line segment is called polygon and the pixels that present on
border and pixels that fall inside polygon are determined for coloring the polygon.
1. Scanline fill algorithm
2. Boundary fill algorithm
3. Flood fill algorithm

San Line fill algorithm

• It fills the polygon using horizontal lines.
• This algorithm works by intersecting scanline with polygon edges and fills the polygon
between pairs of intersections.
For each scan-line:
1. Locate the intersection of the scan- line with the edges.
2. Sort the intersection points from left to right.
3. Draw the interiors intersection points pairwise i.e. (a-b), (c-d)

when the scan line passes from the vertex consider the following rules:
1. If the edges of the polygon lie on different side, count it only once. (see case A)
2. If edges of the polygon lie on the same side, count it twice (see case B)

20
As shown in below figure, Point a, b, c and d are intersected by 2 line segments each. Count b,
c twice but a and d once.

Algorithm steps

1. Assume scan line start from the left and is outside the polygon.
2. When intersect an edge of polygon, start to color each pixel (because now we're inside the
polygon), when intersect another edge, stop coloring.
3. Odd number of edges: inside or interior point
4. Even number of edges: outside or exterior point

= = = = = == = = = = = == = = = = = = = = = = == = = = = = = = = = = = = = == ======

Inside-Outside Tests
This method is also known as counting number method. While filling an object, we often
need to identify whether particular point is inside the object or outside it. There are two methods
by which we can identify whether particular point is inside an object or outside
• . Scan line Algorithm

21
 • Nonzero winding number rule
Non-Zero Winding Number Method:
• In non-zero winding number method we need to know the direction of each edge in the
polygon, ie whether the edge is clockwise or counter-clockwise.
• The winding number is the number of times the polygon edges wind around a particular
point in the counterclockwise direction.
How Does the Non-Zero Winding Number Method Work?
1. To apply non zero winding number rule, first we keep the initial value of winding
number=0
2. Then we imagine drawing a line from point P to outside the polygon which does not
pass through any vertex.
3. Now we add 1 to the winding number every time we intersect a polygon edge that
crosses the line from right to left and we subtract 1 every time we intersect an edge
that crosses from left to right.
4. If the winding number is nonzero then P is defined to be an interior point
Else P is taken to be an exterior point ie Zero
Example 1:

Example 2:

22
= = = = = == = = = = = == = = = = = = = = = = == = = = = = = = = = = = = = == ======

Boundary Fill Algorithm

• It fills the area star at a point inside a region and paints the interior outward toward the
boundary.
• This algorithm picks a point inside an object and starts to fill until it hits the boundary
of the object.
• If the boundary is specified in a single color, the fill algorithm proceeds outward pixel
by pixel until the boundary color encountered.
• This method is called boundary fill algorithm.
• In this algorithm, we assume that color of the boundary is same for the entire object.
• The boundary fill algorithm can be implemented by 4-connected pixels or 8- connected
pixels.
• Boundary Fill Algorithm is also called as recursive algorithm.
How Does the Flood Fill Algorithm Work?
• The algorithm starts checking the color of (x, y).
• Suppose, if the found color is not equal to the fill color and boundary color then it is
painted with the fill color and function is calls all the neighbors of (x, y).
• If a point is found to be of fill or boundary, then the function does not call its neighbors
and returns.
• In boundary fill there is a seed point which is fixed, and the remaining neighboring
pixels are checking to match with the boundary color.
• color filling is done till boundary is reached.

4-Connected
void boundaryFill4(int x, int y, int fill_color, int boundary_color)
{

23
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill4(x + 1, y, fill_color, boundary_color);
boundaryFill4(x, y + 1, fill_color, boundary_color);
boundaryFill4(x - 1, y, fill_color, boundary_color);
boundaryFill4(x, y - 1, fill_color, boundary_color);
}
}
8-Connected
void boundaryFill8(int x, int y, int fill_color,int boundary_color)
{
if(getpixel(x, y) != boundary_color &&
getpixel(x, y) != fill_color)
{
putpixel(x, y, fill_color);
boundaryFill8(x + 1, y, fill_color, boundary_color);
boundaryFill8(x, y + 1, fill_color, boundary_color);
boundaryFill8(x - 1, y, fill_color, boundary_color);
boundaryFill8(x, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y - 1, fill_color, boundary_color);
boundaryFill8(x - 1, y + 1, fill_color, boundary_color);
boundaryFill8(x + 1, y - 1, fill_color, boundary_color);
boundaryFill8(x + 1, y + 1, fill_color, boundary_color);
}
}
= = = = = == = = = = = == = = = = = = = = = = == = = = = = = = = = = = = = == ======

Flood Fill Algorithm

Flood fill algorithm is useful in cases where there no single color boundary for the polygon,
i.e. the boundary has multiple colors.

24
Note: (The flood fill algorithm is particularly useful when there isn't a single color boundary
to define the region to be filled. In such cases, the boundary might consist of multiple colors,
making it impractical to use a boundary fill algorithm that relies on a single boundary color.
For example, consider a hand-drawn sketch where the outline of a shape is not a solid color but
consists of varying shades and colors due to artistic effects or shading. Using a single color to
define the boundary in such cases would be impractical.)//
How it works:
• The process in this method is that first a point is selected which lies within the region
under consideration. This point is also called seed, and hence the name seed fill
algorithm.
• After this step, we have two methods, one is four connected and other is eight
connected approaches. Using any of the two we can fill the color.

• In many ways it is similar to boundary fill, but in this method, we can fill multiple
colors to the boundary, and we can fill one color in the interior.
How Does the Flood Fill Algorithm Work?
The algorithm starts at a point, let us assume (x,y), and then assign all the interior color to the
desired color. The flood fill algorithm works by starting with a given pixel in an image and
systematically examining neighboring pixels to determine whether they should be filled with a
new color or pattern.

25
Step 1: Picking Starting Pixels: The algorithm begins by choosing a starting pixel (x,y),
within the image that needs to be filled.
Step 2: Changing the Color of the Starting Pixel: Then, the starting pixel’s color is changed
to the new desired color.
For example, if the interior color is blue and the desired fill color is red, all blue pixels
within the region are replaced with red.
Step 3: Traversal of Neighboring Pixels either four connected or eight connected: Then, it
will examine the neighboring pixels of the starting pixel. For each neighbor, it checks if it’s
within the bounds of the image and has the same color as the starting pixel’s original color.
Step 4: Changing the Color of Neighboring Pixels: If a neighboring pixel meets the criteria
(same color as the starting pixel’s original color and within image bounds), it’s colored with
the new color.
Step 5: Repetition of Step 4: This process continues recursively (using a stack or recursive
function calls) or iteratively (using a queue or loop) for all eligible neighboring pixels.
Step 6: Final Filling of All Pixels: The algorithm keeps expanding outward and examines the
neighboring pixels of the newly filled pixels. This process is continued until all pixels within
the enclosed area with the original color have been filled with the new color.
4-Connected
procedure floodFill(x, y, newColor, originalColor):
begin
if pixel (x, y) is within image bounds and has originalColor:
begin
set pixel (x, y) to newColor
floodFill(x + 1, y, newColor, originalColor) // Check right neighbor
floodFill(x - 1, y, newColor, originalColor) // Check left neighbor
floodFill(x, y + 1, newColor, originalColor) // Check bottom neighbor
floodFill(x, y - 1, newColor, originalColor) // Check top neighbor
end
end
8-Connected
Void floodfill8(int x, int y, int fillcolor, int oldcolor)
{
getPixel(x,y,color);

26
if(color != oldcolor)
{
setPixel(x,y);
floodfill8(x + 1, y, newColor, originalColor) ; // Check right neighbor
floodfill8(x - 1, y, newColor, originalColor) ; // Check left neighbor
floodfill8(x, y+1, newColor, originalColor) ; // Check bottom neighbor
floodfill8(x, y-1, newColor, originalColor) ; // Check top neighbor
floodfill8(x-1, y-1, newColor, originalColor) ;
floodfill8(x-1, y+1, newColor, originalColor) ;
floodfill8(x+1, y-1, newColor, originalColor);
floodfill8(x+1, y+1, newColor, originalColor) ;
}
}
= = = = = == = = = = = == = = = = = = = = = = == = = = = = = = = = = = = = == ======

27