Risanje krožnic

Poleg ravnih črt so krožnice še ena oblika, ki jo moramo pogosto narisati z računalnikom. Za učinkovito risanje krožnice so razvili algoritem, podoben Bresenhamovemu algoritmu za risanje črt, ki so ga poimenovali algoritem središča krožnice (ang. Midpoint Circle Algorithm). Krožnica je določena s središčem $S$ in polmerom $R$. Vse točke na krožnici so za polmer oddaljene od središča krožnice.

Ali lahko z barvanjem pikslov, brez uporabe ravnila in šestila, narišeš krožnico tako, da bo dejansko videti okrogla?

19
18
17
16
15
14
13
12
11
10
9										S							R
8
7
6
5
4
3
2
1
0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

Krožnico je mogoče narisati s formulo, ki temelji na Pitagorovem izreku, vendar moramo za vsak piksel izračunati kvadratni koren, kar je zelo dolgotrajno. Naslednji algoritem je veliko hitrejši in vključuje samo preprosto računanje, zato lahko z njim bistveno hitreje izračunamo, katere piksle naj pobarva.

Za uporabo algoritma središča krožnice moramo upoštevati nekaj preprostih korakov (spodaj). Najprej moramo izračunati tri vrednosti: $E = -R, X = R, Y = 0$

Del krožnice s središčem $S(x, y)$ in polmerom $R$ narišemo tako, da sledimo naslednjim korakom:

Pobarvamo piksel s koordinatama $(x + X, y + Y)$.
Povečamo $E$ za $2 \times Y + 1$.
Povečamo $Y$ za $1$.
Če je $E \geq 0$, zmanjšamo $E$ za $2 \times X - 1$, nato zmanjšamo $X$ za $1$.
Ponavljamo, dokler $Y$ ne postane večji kot $X$.

S pomočjo algoritma središča krožnice ter brez uporabe ravnila in šestila v spodnji mreži nariši krožnico s središčem $S$ in polmerom $R$.

19
18
17
16
15
14
13
12
11
10
9										S							R
8
7
6
5
4
3
2
1
0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

Ko $Y$ postane večji od $X$, smo narisali eno osmino krožnice. Preostanek krožnice narišemo tako, da preslikamo osmino, ki jo že imamo (ponovimo korake v nasprotni smeri). Nato preslikamo četrtino krožnice preko osi $y$, da dobimo zgornjo polovico krožnice. Nato preslikamo polovico krožnice preko osi $x$, da dobimo celo krožnico.

19
18
17
16
15
14
13
12
11
10
9										S							R
8
7
6
5
4
3
2
1
0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

19
18
17
16
15
14
13
12
11
10
9										S							R
8
7
6
5
4
3
2
1
0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

19
18
17
16
15
14
13
12
11
10
9										S							R
8
7
6
5
4
3
2
1
0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

19
18
17
16
15
14
13
12
11
10
9										S							R
8
7
6
5
4
3
2
1
0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

19
18
17
16
15
14
13
12
11
10
9										S							R
8
7
6
5
4
3
2
1
0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19

19
18
17
16
15
14
13
12
11
10
9										S							R
8
7
6
5
4
3
2
1
0
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19