Question:

Published on: 24 June, 2024

Answer:

Scan-Converting a circle using Bresenham's algorithm works as follows: Points are generated from 90° to 45°, moves will be made only in the +x & -y directions as shown in fig:

The best approximation of the true circle will be described by those pixels in the raster that falls the least distance from the true circle. We want to generate the points from

90° to 45°. Assume that the last scan-converted pixel is P_{1} as shown in fig. Each new point closest to the true circle can be found by taking either of two actions.

- Move in the x-direction one unit or
- Move in the x- direction one unit & move in the negative y-direction one unit.

Let D (S_{i}) is the distance from the origin to the true circle squared minus the distance to point P_{3} squared. D (T_{i}) is the distance from the origin to the true circle squared minus the distance to point P_{2} squared. Therefore, the following expressions arise.

D (S_{i})=(x_{i-1}+1)^{2}+ y_{i-1}^{2} -r^{2}

D (T_{i})=(x_{i-1}+1)^{2}+(y_{i-1} -1)^{2}-r^{2}

Since D (S_{i}) will always be +ve & D (T_{i}) will always be -ve, a decision variable d may be defined as follows:

d_{i}=D (S_{i} )+ D (T_{i})

Therefore,

d_{i}=(x_{i-1}+1)^{2}+ y_{i-1}^{2} -r^{2}+(x_{i-1}+1)^{2}+(y_{i-1} -1)^{2}-r^{2}

From this equation, we can drive initial values of d_{i} as

If it is assumed that the circle is centered at the origin, then at the first step x = 0 & y = r.

Therefore,

d_{i}=(0+1)^{2}+r^{2} -r^{2}+(0+1)^{2}+(r-1)^{2}-r^{2}

=1+1+r^{2}-2r+1-r^{2}

= 3 - 2r

Thereafter, if d_i<0,then only x is incremented.

x_{i+1}=x_{i+1} d_{i+1}=d_{i}+ 4x_{i}+6

& if d_{i}≥0,then x & y are incremented

x_{i+1}=x_{i+1} y_{i+1} =y_{i}+ 1

d_{i+1}=d_{i}+ 4 (x_{i}-y_{i})+10

**Step1:** Start Algorithm

**Step2:** Declare p, q, x, y, r, d variables

p, q are coordinates of the center of the circle

r is the radius of the circle

**Step3:** Enter the value of r

**Step4:** Calculate d = 3 - 2r

**Step5:** Initialize x=0

&nbsy= r

**Step6:** Check if the whole circle is scan converted

If x > = y

Stop

**Step7:** Plot eight points by using concepts of eight-way symmetry. The center is at (p, q). Current active pixel is (x, y).

putpixel (x+p, y+q)

putpixel (y+p, x+q)

putpixel (-y+p, x+q)

putpixel (-x+p, y+q)

putpixel (-x+p, -y+q)

putpixel (-y+p, -x+q)

putpixel (y+p, -x+q)

putpixel (x+p, -y-q)

**Step8:** Find location of next pixels to be scanned

If d < 0

then d = d + 4x + 6

increment x = x + 1

If d ≥ 0

then d = d + 4 (x - y) + 10

increment x = x + 1

decrement y = y - 1

**Step9:** Go to step 6

**Step10:** Stop Algorithm

Subjects

Trending

Random questions

What is linear searching?

23 January, 2022

24 June, 2024

Write short notes: B tree

24 June, 2024

**What do you mean by software crisis & its solution.**

24 June, 2024

**Write a C program to find the value of Sine(X).**

24 June, 2024