MIDPOINT ELLIPSE ALGORITHM
1. Read rx
and ry.
2. Initialise
starting point
x = 0
y = ry
3. Calculate the initial value of decision
parameter in region I as
d1
= ry2 - rx2ry + 1/4 rx2
4. Initialize dx
and dy as
dx = 2ry2 x
dy = 2rx2y
5. do
{
plot(x,y)
if(d1 < 0)
{
x = x+ 1
y = y
dx = dx + 2ry2
d1 = d1 + dx+ ry2
}
else
x = x + 1
y = y - l
dx = dx + 2ry2
dy = dy - 2rx2
d1 = d1 + dx - dy + ry2
}
while (dx < dy)
6. Calculate the initial value of decision
parameter in region II as
d2 = ry2
(x + 1/2) 2 + rx2 (y - 1) 2 - rx2
ry2
7. do
{
plot(x,y)
if (d2 > 0)
{
x = x
y = y – 1
dy = dy - 2r x2
d2 = d2 - dy
+ rx2
}
Else
{
x = x+ 1
y = y – 1
dx = dx + 2ry2
dy =
dy - 2rx2
d2 = d2 + dx
- dy + rx2
}
while (y > 0)
8. Determine symmetrical points in other three
quadrants.
9. Stop.
Example
Given ellipse parameters rx = 8 and ry
= 6. Determine raster positions.
For region I
d1 = ry2 – rx2 ry +
¼ rx2
= 36 – 64 *6 + ¼ *64
= 36 - 384 + 16
= 52 -
384
= - 332
k
|
d1
|
(xk+1, yk+1)
|
2ry2 xk+1
|
2rx2 yk+1
|
0
|
-332
|
(1,6)
|
72
|
768
|
1
|
-224
|
(2,6)
|
144
|
768
|
2
|
-44
|
(3,6)
|
216
|
768
|
3
|
208
|
(4,5)
|
288
|
640
|
4
|
-108
|
(5,5)
|
360
|
640
|
5
|
288
|
(6,4)
|
432
|
512
|
6
|
244
|
(7,3)
|
504
|
384
|
For region II
The initial point is (7, 3)
Our initial decision parameter is
d2 = 36 (7 + l/2)2 +
64 (3 - 1)2 - 36 *64
= 36*225/4 + 64*4 - 2304
= 2025 + 256 - 2304
= - 23
k
|
d1
|
(xk+1, yk+1)
|
2ry2 xk+1
|
2rx2 yk+1
|
0
|
-23
|
(8,2)
|
576
|
256
|
1
|
361
|
(8,1)
|
576
|
128
|
2
|
297
|
(8,0)
|
-
|
-
|
No comments:
Post a Comment