Derivation of Mid Point Ellipse Algorithm.

Derivation:

                     Assume that a ellipse with center at origin with major and minor axis a and b. Than the equation of ellipse will be

X2/a2 + Y2/b2 = 1

X2/a2 + Y2/b2 – 1 = 0

b2X2 + a2Y2 – a2b2

Over Region R1

F(X,Y) = b2X2 + a2Y2 – a2b2

F(Xmid , Ymid) = (Xk+1 , Yk – 1/2)

                                        

                                              < 0 midpoint is inside

                                         

F(Xmid , Ymid)=                  = 0 midpoint is on the ellipse

                          

                                              > 0 midpoint is outside

F(Xmid , Ymid) = b2(Xk+1)2 + a2(Yk - 1/2)2 – a2b2

P’k = b2(Xk+1)2 + a2(Y2k + ¼ - Yk) – a2b2

P’k = b2(X2k + 1 + 2Xk) + a2(Y2k + ¼ -Yk) – a2b2

P’k+1 = b2(X2k+1 + 1 + 2Xk+1) + a2(Y2k+1 + ¼ -Yk+1) – a2b2

Initial decision parameter of Region 1 (0 , b)

P’o=b2(0+1+0) + a2(b2 + ¼ -b) – a2b2

P’o = b2 + a2b2 + a2/4 –a2b – a2b2

P’o= b2 + a2/4 – a2b

P’o= a2/4 – a2b + b2

This is the initial decision parameter of region 1

P’k+1 – P’k = b2(X2k+1 – X2k) +2b2(Xk+1-Xk) + a2(Y2k+1 – Y2k) + a2(Yk+1 - Yk)

P’k+1 – P’k = b2(Xk+1 – Xk)(Xk+1 + Xk) +2b2(Xk+1-Xk) + a2(Yk+1 – Yk)(Yk+1 + Yk) -a2(Yk+1 - Yk)

If P is negative

Xk+1 – Xk = 1

Yk+1 – Yk = 0

P’k+1 = P’k + 2b2 Xk+1 + b2

This is the decision parameter for less than zero of region 1.

If P is positive

Xk+1 – Xk = 1

Yk+1 – Yk = -1

 

P’k+1 = P’k +b2(Xk+1 + Xk) + 2b2 + a2(-1)(Yk+1 + Yk) –a2(-1)

P’k+1 = P’k + 2b2 Xk+1 + b2 – 2a2 Yk+1

This is the decision parameter for greater than zero of region 1

Over Region R2

F(X,Y) = b2X2 + a2Y2 – a2b2

F(Xmid , Ymid) = (Xk+1/2 , Yk – 1)

F(Xmid , Ymid) = b2(Xk + 1/2)2 + a2(Yk - 1)2 – a2b2

P’’k = b2(Xk + 1/2)2 + a2(Y2k - 1) – a2b2

P’’k = b2(X2k + 1/4 + Xk) + a2(Y2k + 1 -2Yk) – a2b2

P’’k+1 = b2(X2k+1 + 1/4 + Xk+1) + a2(Y2k+1 + 1 -2Yk+1) – a2b2

Initial decision parameter of Region R2 (Xo , Yo)

P’’o = b2(xo + 1/2)2 + a2( Yo - 1)2 – a2b2

This is the initial decision parameter of region R2

P’k+1 – P’k = b2(X2k+1 – X2k) +b2(Xk+1-Xk) + a2(Y2k+1 – Y2k) -2a2(Yk+1 - Yk)

P’k+1 – P’k = b2(Xk+1 – Xk)(Xk+1 + Xk) +b2(Xk+1-Xk) + a2(Yk+1 – Yk)(Yk+1 + Yk) -2a2(Yk+1 - Yk)

If P is positive

Xk+1 – Xk = 0

Yk+1 – Yk = -1

P’’k+1 = P’’k – 2a2 Yk+1 + a2

This is the decision parameter for greater than zero of region 2.

If P is negative

Xk+1 – Xk = 1

Yk+1 – Yk = -1

P’’k+1 = P’’k + 2b2 Xk+1 -2a2 Yk+1 + a2

This is the decision parameter for less than zero of region 2.