HW 2D CGA - PPT 8 - Polygon Fill

Question

Solution:

First of all, we need to know the element to be inserted into SET and AEL. The element must contain $y_{max}$, $xof{y}_{min}$, $dx$, and $dy$. Also carry but only in AEL, carry doesn't need to be inserted into SET. With that said, let's begin with the first polygon.

Polygon 1

A(1, 6), B(5,4), C(3,1)

From these 3 vertices we need to find the edges element containing $y_{max}$, $xof{y}_{min}$, $dx$, and $dy$. Let's take a look at edge AB, the $y_{max}$ is 6, the $xof{y}_{min}$ is 5, the $dx$ is 4, and the $dy$ is -2. Now if we found $dy<0$ we need to make it positive, by multiplying $dx$ and $dy$ with -1, so we got $dx$ = -4 and $dy$ = 2. The same rule applies with edges BC and CA. After we've found all of the elements then, we put it into the SET just like below.

SET

	y	Edges
$y_{max}$	6
	5
	4	$\to AB$ 6 5 -4 2
	3
	2
$y_{min}$	1	$\to BC$ 4 3 2 3 $\to CA$ 6 3 -2 5

After finishing the SET, we can continue to the AEL. There are some rules to follow in calculating AEL as written below.

if $dx<0$	if $dx>0$
carry += $dx$ loop (carry $\times (-2)\ge dy$) carry += $dy$ $xof{y}_{min}$ -= 1	carry += $dx$ loop (carry $\times 2\ge dy$) carry -= $dy$ $xof{y}_{min}$ += 1

AEL

y=1	$BC$ 4 3 2 3 0 $\to CA$ 6 3 -2 5 0
y=2	$0+2=2|\times 2|4\ge 3$ $2-3=-1$ $3+1=4$ $-1|\times 2|-2<3$ $-$ $0+(-2)=-2|\times (-2)|4<5$ $-$ $BC$ 4 4 2 3 -1 $\to CA$ 6 3 -2 5 -2
y=3	$-1+2=1|\times 2|2<3$ $-$ $-2+(-2)=-4|\times (-2)|8\ge 5$ $-4+5=1$ $3-1=2$ $1|\times (-2)|-2<5$ $-$ $BC$ 4 4 2 3 1 $\to CA$ 6 2 -2 5 1
y=4	BC has reached y=5 and AB starts $1+(-2)=-1|\times (-2)|2<5$ $-$ $AB$ 6 5 -4 2 0 $\to CA$ 6 2 -2 5 -1
y=5	$0+(-4)=-4|\times (-2)|8\ge 2$ $-4+2=-2$ $5-1=4$ $-2|\times (-2)|4\ge 2$ $-2+2=0$ $4-1=3$ $0|\times (-2)|0<2$ $-$ $-1+(-2)=-3|\times (-2)|6\ge 5$ $-3+5=2$ $2-1=1$ $2|\times (-2)|-4<5$ $-$ $AB$ 6 3 -4 2 0 $\to CA$ 6 1 -2 5 2
y=6	AB and CA both ended in y=6

Now let's continue to the second polygon.

Polygon 2

A(0, 0), B(5, 3), C(10, 0), D(5, 10)

 From these 4 vertices we need to find the edges element containing $y_{max}$, $xof{y}_{min}$, $dx$, and $dy$. Let's take a look at edge AB, the $y_{max}$ is 3, the $xof{y}_{min}$ is 0, the $dx$ is 5, and the $dy$ is 3. The same rule applies with edges BC, CD, and DA. After we've found all of the elements then, we put it into the SET just like below.

SET

	$y$	Edges
$y_{max}$	10
	9
	8
	7
	6
	5
	4
	3
	2
	1
$y_{min}$	0	$\to$ AB 3 0 5 3 $\to$ BC 3 10 -5 3 $\to$ CD 10 10 -5 10 $\to$ DA 10 0 5 10

Now for the AEL. Remember the rule for AEL? Here are the rules to follow in calculating AEL as written below.

if $dx<0$	if $dx>0$
carry += $dx$ loop (carry $\times (-2)\ge dy$) carry += $dy$ $xof{y}_{min}$ -= 1	carry += $dx$ loop (carry $\times 2\ge dy$) carry -= $dy$ $xof{y}_{min}$ += 1

AEL

y=0	AB 3 0 5 3 0 $\to$ BC 3 10 -5 3 0 $\to$ CD 10 10 -5 10 0 $\to$ DA 10 0 5 10 0
y=1	$0+5=5$ $5|\times 2|10\ge 3$ $5-3=2$ $0+1=1$ $2|\times 2|4\ge 3$ $2-3=-1$ $1+1=2$ $-1|\times 2|-2<3$ $-$ $0+(-5)=-5$ $-5|\times (-2)|10\ge 3$ $-5+3=-2$ $10-1=9$ $-2|\times (-2)|4\ge 3$ $-2+3=1$ $9-1=8$ $1|\times (-2)|-2<3$ $-$ $0+(-5)=-5$ $-5|\times (-2)|10\ge 10$ $-5+10=5$ $10-1=9$ $5|\times (-2)|-10<10$ $-$ $0+5=5$ $5|\times 2|10\ge 10$ $5-10=-5$ $0+1=1$ $-5|\times 2|-10<10$ $-$ AB 3 2 5 3 -1 $\to$ BC 3 8 -5 3 1 $\to$ CD 10 9 -5 10 5 $\to$ DA 10 1 5 10 -5
y=2	$-1+5=4$ $4|\times 2|8\ge 3$ $4-3=1$ $2+1=3$ $1|\times 2|2<3$ $-$ $1+(-5)=-4$ $-4|\times (-2)|8\ge 3$ $-4+3=-1$ $8-1=7$ $-1|\times (-2)|2<3$ $-$ $5+(-5)=0$ $0|\times (-2)|0<10$ $-$ $-5+5=0$ $0|\times 2|0<10$ $-$ AB 3 3 5 3 1 $\to$ BC 3 7 -5 3 -1 $\to$ CD 10 9 -5 10 0 $\to$ DA 10 1 5 10 0
y=3	AB popped BC popped $0+(-5)=-5$ $-5|\times (-2)|10\ge 10$ $-5+10=5$ $9-1=8$ $5|\times (-2)|-10<10$ $-$ $0+5=5$ $5|\times 2|10\ge 10$ $5-10=-5$ $1+1=2$ $-5|\times 2|-10<10$ $-$ CD 10 8 -5 10 5 $\to$ DA 10 2 5 10 -5
y=4	$5+(-5)=0$ $0|\times (-2)|0<10$ $-$ $-5+5=0$ $0|\times 2|0<10$ $-$ CD 10 8 -5 10 0 $\to$ DA 10 2 5 10 0
y=5	$0+(-5)=-5$ $-5|\times (-2)|10\ge 10$ $-5+10=5$ $8-1=7$ $5|\times (-2)|-10<10$ $-$ $0+5=5$ $5|\times 2|10\ge 10$ $5-10=-5$ $2+1=3$ $-5|\times 2|-10<10$ $-$ CD 10 7 -5 10 5 $\to$ DA 10 3 5 10 -5
y=6	$5+(-5)=0$ $0|\times (-2)|0<10$ $-$ $-5+5=0$ $0|\times 2|0<10$ $-$ CD 10 7 -5 10 0 $\to$ DA 10 3 5 10 0
y=7	$0+(-5)=-5$ $-5|\times (-2)|10\ge 10$ $-5+10=5$ $7-1=6$ $5|\times (-2)|-10<10$ $-$ $0+5=5$ $5|\times 2|10\ge 10$ $5-10=-5$ $3+1=4$ $-5|\times 2|-10<10$ $-$ CD 10 6 -5 10 5 $\to$ DA 10 4 5 10 -5
y=8	$5+(-5)=0$ $0|\times (-2)|0<10$ $-$ $-5+5=0$ $0|\times 2|0<10$ $-$ CD 10 6 -5 10 0 $\to$ DA 10 4 5 10 0
y=9	$0+(-5)=-5$ $-5|\times (-2)|10\ge 10$ $-5+10=5$ $6-1=5$ $5|\times (-2)|-10<10$ $-$ $0+5=5$ $5|\times 2|10\ge 10$ $5-10=-5$ $4+1=5$ $-5|\times 2|-10<10$ $-$ CD 10 5 -5 10 5 $\to$ DA 10 5 5 10 -5
y=10	CD popped DA popped

Now for the third polygon.

Polygon 3

A(7, 1), B(13, 5), C(13, 11), D(7, 7), E(2, 9), F(2, 3)

From these 6 vertices we need to find the edges element containing $y_{max}$, $xof{y}_{min}$, $dx$, and $dy$. Let's take a look at edge AB, the $y_{max}$ is 5, the $xof{y}_{min}$ is 7, the $dx$ is 6, and the $dy$ is 4. The same rule applies with edges BC, CD, DE, EF, and FA. After we've found all of the elements then, we put it into the SET just like below.

SET

	$y$	Edges
$y_{max}$	11
	10
	9
	8
	7	$\to$ CD 11 7 6 4 $\to$ DE 9 7 -5 2
	6
	5	$\to$ BC 11 13 0 6
	4
	3	$\to$ EF 9 2 0 6
	2
$y_{min}$	1	$\to$ AB 5 7 6 4 $\to$ FA 3 7 -5 2

Now for the AEL. Remember the rule for AEL? Here are the rules to follow in calculating AEL as written below.

if $dx<0$	if $dx>0$
carry += $dx$ loop (carry $\times (-2)\ge dy$) carry += $dy$ $xof{y}_{min}$ -= 1	carry += $dx$ loop (carry $\times 2\ge dy$) carry -= $dy$ $xof{y}_{min}$ += 1

AEL

y=1	AB 5 7 6 4 0 $\to$ FA 3 7 -5 2 0
y=2	$0+6=6$ $6|\times 2|12\ge 4$ $6-4=2$ $7+1=8$ $2|\times 2|4\ge 4$ $2-4=-2$ $8+1=9$ $-2|\times 2|-4<4$ $-$ $0-5=-5$ $-5|\times (-2)|10\ge 2$ $-5+2=-3$ $7-1=6$ $-3|\times (-2)|6\ge 2$ $-3+2=-1$ $6-1=5$ $-1|\times (-2)|2\ge 2$ $-1+2=1$ $5-1=4$ $1|\times (-2)|-2<2$ $-$ AB 5 9 6 4 -2 $\to$ FA 3 4 -5 2 1
y=3	$-2+6=4$ $4|\times 2|8\ge 4$ $4-4=0$ $9+1=10$ $0|\times 2|0<4$ $-$ FA popped, insert EF AB 5 10 6 4 0 $\to$ EF 9 2 0 6 0
y=4	$0+6=6$ $6|\times 2|12\ge 4$ $6-4=2$ $10+1=11$ $2|\times 2|4\ge 4$ $2-4=-2$ $11+1=12$ $-2|\times 2|-4<4$ $-$ EF dx=0 so no need to calculate this one AB 5 12 6 4 -2 $\to$ EF 9 2 0 6 0
y=5	EF dx=0 so no need to calculate this one AB popped, insert BC EF 9 2 0 6 0 $\to$ BC 11 13 0 6 0
y=6	EF dx=0 so no need to calculate this one BC dx=0 so no need to calculate this one EF 9 2 0 6 0 $\to$ BC 11 13 0 6 0
y=7	EF dx=0 so no need to calculate this one BC dx=0 so no need to calculate this one insert CD insert DE EF 9 2 0 6 0 $\to$ BC 11 13 0 6 0 $\to$ CD 11 7 6 4 0 $\to$ DE 9 7 -5 2 0
y=8	EF dx=0 so no need to calculate this one BC dx=0 so no need to calculate this one $0+6=6$ $6|\times 2|12\ge 4$ $6-4=2$ $7+1=8$ $2|\times 2|6\ge 4$ $2-4=-2$ $8+1=9$ $-2|\times 2|-4<4$ $-$ $0-5=-5$ $-5|\times (-2)|10\ge 2$ $-5+2=-3$ $7-1=6$ $-3|\times (-2)|6\ge 2$ $-3+2=-1$ $6-1=5$ $-1|\times (-2)|2\ge 2$ $-1+2=1$ $5-1=4$ $1|\times (-2)|-2<2$ $-$ EF 9 2 0 6 0 $\to$ BC 11 13 0 6 0 $\to$ CD 11 9 6 4 -2 $\to$ DE 9 4 -5 2 1
y=9	EF popped BC dx=0 so no need to calculate this one $-2+6=4$ $4|\times 2|10\ge 4$ $4-4=0$ $9+1=10$ $0|\times 2|0<4$ $-$ DE popped BC 11 13 0 6 0 $\to$ CD 11 10 6 4 0
y=10	BC dx=0 so no need to calculate this one $0+6=6$ $6|\times 2|12\ge 4$ $6-4=2$ $10+1=11$ $2|\times 2|4\ge 4$ $2-4=-2$ $11+1=12$ $-2|\times 2|-4<4$ $-$ BC 11 13 0 6 0 $\to$ CD 11 12 6 4 -2
y=11	BC popped CD popped

Now let's continue to the fourth polygon.

Polygon 4

A(3, 3), B(10, 5), C(14, 5), D(8, 1), E(21, 10), F(13, 10), G(3, 17)

From these 7 vertices we need to find the edges element containing $y_{max}$, $xof{y}_{min}$, $dx$, and $dy$. Let's take a look at edge AB, the $y_{max}$ is 5, the $xof{y}_{min}$ is 3, the $dx$ is 7, and the $dy$ is 2. The same rule applies with edges BC, CD, DE, EF, FG, and GA. After we've found all of the elements then, we put it into the SET just like below.

SET

	$y$	Edges
$y_{max}$	17
	16
	15
	14
	13
	12
	11
	10	$\to$ FG 17 13 -10 7
	9
	8
	7
	6
	5
	4
	3	$\to$ AB 5 3 7 2 $\to$ GA 17 3 0 14
	2
$y_{min}$	1	$\to$ CD 5 18 -4 4 $\to$ DE 10 18 3 9

Notice that out of 7 pairs of edges we only insert 5 of them, that is because we don't need to include horizontal edges where dy=0 such as BC and EF. Now for the AEL. Remember the rule for AEL? Here are the rules to follow in calculating AEL as written below.

if $dx<0$	if $dx>0$
carry += $dx$ loop (carry $\times (-2)\ge dy$) carry += $dy$ $xof{y}_{min}$ -= 1	carry += $dx$ loop (carry $\times 2\ge dy$) carry -= $dy$ $xof{y}_{min}$ += 1

AEL

y=1	CD 5 18 -4 4 0 $\to$ DE 10 18 3 9 0
y=2	$0-4=-4$ $-4|\times (-2)|8\ge 4$ $-4+4=0$ $18-1=17$ $0|\times (-2)|0<4$ $-$ $0+3=3$ $3|\times 2|6<9$ $-$ CD 5 17 -4 4 0 $\to$ DE 10 18 3 9 3
y=3	$0-4=-4$ $-4|\times (-2)|8\ge 4$ $-4+4=0$ $17-1=16$ $0|\times (-2)|0<4$ $-$ $3+3=6$ $6|\times 2|12\ge 9$ $6-9=-3$ $18+1=19$ $-3|\times 2|-6<9$ $-$ insert AB insert GA CD 5 16 -4 4 0 $\to$ DE 10 19 3 9 -3 $\to$ AB 5 3 7 2 0 $\to$ GA 17 3 0 14 0
y=4	$0-4=-4$ $-4|\times (-2)|8\ge 4$ $-4+4=0$ $16-1=15$ $0|\times (-2)|0<4$ $-$ $-3+3=0$ $0|\times 2|0<9$ $-$ $0+7=7$ $7|\times 2|14\ge 2$ $7-2=5$ $3+1=4$ $5|\times 2|10\ge 2$ $5-2=3$ $4+1=5$ $3|\times 2|6\ge 2$ $3-2=1$ $5+1=6$ $1|\times 2|2\ge 2$ $1-2=-1$ $6+1=7$ $-1|\times 2|-2<2$ $-$ GA dx=0 so no need to calculate this one CD 5 15 -4 4 0 $\to$ DE 10 19 3 9 0 $\to$ AB 5 7 7 2 -1 $\to$ GA 17 3 0 14 0
y=5	CD popped $0+3=3$ $3|\times 2|3<9$ $-$ AB popped GA dx=0 so no need to calculate this one DE 10 19 3 9 3 $\to$ GA 17 3 0 14 0
y=6	$3+3=6$ $6|\times 2|12\ge 9$ $6-9=-3$ $19+1=20$ $-3|\times 2|-6<9$ $-$ GA dx=0 so no need to calculate this one DE 10 20 3 9 -3 $\to$ GA 17 3 0 14 0
y=7	$-3+3=0$ $0|\times 2|0<9$ $-$ GA dx=0 so no need to calculate this one DE 10 20 3 9 0 $\to$ GA 17 3 0 14 0
y=8	$0+3=3$ $3|\times 2|6<9$ $-$ GA dx=0 so no need to calculate this one DE 10 20 3 9 3 $\to$ GA 17 3 0 14 0
y=9	$3+3=6$ $6|\times 2|12\ge 9$ $6-9=-3$ $20+1=21$ $-3|\times 2|-6<9$ $-$ GA dx=0 so no need to calculate this one DE 10 21 3 9 -3 $\to$ GA 17 3 0 14 0
y=10	DE popped, insert FG GA dx=0 so no need to calculate this one FG 17 13 -10 7 0 $\to$ GA 17 3 0 14 0
y=11	$0-10=-10$ $-10|\times (-2)|20\ge 7$ $-10+7=-3$ $13-1=12$ $-3|\times (-2)|6<7$ $-$ GA dx=0 so no need to calculate this one FG 17 12 -10 7 -3 $\to$ GA 17 3 0 14 0
y=12	$-3-10=-13$ $-13|\times (-2)|26\ge 7$ $-13+7=-6$ $12-1=11$ $-6|\times (-2)|12\ge 7$ $-6+7=1$ $11-1=10$ $1|\times (-2)|-2<7$ $-$ GA dx=0 so no need to calculate this one FG 17 10 -10 7 1 $\to$ GA 17 3 0 14 0
y=13	$1-10=-9$ $-9|\times (-2)|18\ge 7$ $-9+7=-2$ $10-1=9$ $-2|\times (-2)|4<7$ $-$ GA dx=0 so no need to calculate this one FG 17 9 -10 7 -2 $\to$ GA 17 3 0 14 0
y=14	$-2-10=-12$ $-12|\times (-2)|24\ge 7$ $-12+7=-5$ $9-1=8$ $-5|\times (-2)|10\ge 7$ $-5+7=2$ $8-1=7$ $2|\times (-2)|-2<7$ $-$ GA dx=0 so no need to calculate this one FG 17 7 -10 7 2 $\to$ GA 17 3 0 14 0
y=15	$2-10=-8$ $-8|\times (-2)|16\ge 7$ $-8+7=-1$ $7-1=6$ $-1|\times (-2)|2<7$ $-$ GA dx=0 so no need to calculate this one FG 17 6 -10 7 -1 $\to$ GA 17 3 0 14 0
y=16	$-1-10=-11$ $-11|\times (-2)|22\ge 7$ $-11+7=-4$ $6-1=5$ $-4|\times (-2)|8\ge 7$ $-4+7=3$ $5-1=4$ $3|\times (-2)|-6<7$ $-$ GA dx=0 so no need to calculate this one FG 17 4 -10 7 3 $\to$ GA 17 3 0 14 0
y=17	FG popped GA popped

And that's that is all the solution for this question.