i
i
“Vitek-kroznica” — 2010/5/28 — 9:15 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 14 (1986/1987)
Številka 3
Strani 145–155
Andrej Vitek:
KAKO RAČUNALNIK NARIŠE KROŽNICO
Ključne besede: računalništvo, matematika.
Elektronska verzija: http://www.presek.si/14/831-Vitek.pdf
c© 1987 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
KAKO RAČUNALNIK NARISE KROŽNICO
Zadnjič (Presek 13 (1985/86)1) smo si ogledali računalnikovo ravnilo . Spozna-
li smo, kako računalnik nariše dalj ico. Danes si oglejmo še njegovo šestilo , po-
glejmo torej, kako računalnik riše krožni lok. Preden nadaljujemo, le ponovi-
mo, kakšen je računalnikov papir: velika rešetka raznobarvnih pik, oštevilčenih
z dvema celima številoma - številko stolpca in vrstice, v kateri pika stoji. Zato
bo tudi krožnica, ki jo bomo narisali, rahlo žaqasta, Toda to nas ne bo motilo,
kot nas ni motilo zadnjič.
Slika 1. Skica risanja z mnogokotnikom
145
Kratek izlet v trigonometrijo
(Opomba: če trigonometrije ne obvladate. lahko ta odstavek mirno presko-
čite.)
Sedaj, ko znamo risati daljice. nam najprej pride na misel. da bi poskusili
krožnico narisati z daljicami. Po obodu kroga razporedimo enakomerno raz-
maknjene točke. ki jih med seboj povežemo z daljicami. Tako namesto krožni-
ce narišemo sicer mnogokotnik, ki pa krožnico ponazarja dovolj dobro. če smo
le na obod razmetali dovolj točk. Poskusimo določiti koordinate teh točk! V
ta namen privzemimo, da se središče kroga ujema z izhodiščem koordinatnega
sistema, njegov polmer pa označimo zR. Na obod razporedimo N točk.
Točko. v kateri bomo začeli risati, postavimo na os x in jo označimo s To,
preostale pa naj bodo Ti. oo., TN -l. Tako je središčni kot med zaporednima
točkama enak ravno N-temu delu polnega kota, torej (izražen vradianih)
2*PI/N (glej sliko 1). Središčni kot med začetnim in k-tim naslednjim ogliš-
čem (Tk) je zato k-krat tolikšen. Koordinati xk' Yk točke Tk sta tako xk =
= R * cos(k * 2 * PIIN) in Y k = R * sin(k * 2 * PI/N). kjer je k = 0, 1,2, ...•
N - 1. Če se središče krožnice in izhodišče koordinatnega sistema ne ujemata,
moramo koordinatama xk in Y k prišteti še koordinati središča Xs in ys, tako
da ima v splošnem primeru točka Tk koordinati (xS+xk' YS+Yk) '
Prepišimo te ugotovitve v postopek za risanje! V ta namen označimo z
R
N
xsred, ysred
xzač,yzač
xkon,ykon
kot
korak
- polmer kroga,
- število stranic mnogokotnika,
- koordinati središča kro žnice,
- koordinati začetne točke trenutno risane
stranice,
- koordinati končne točke te stranice,
- središčni kot zadnje narisane točke,
- središčni kot med zaporednima ogliščema.
Risanje gre potem takole:
(1) postavi se v začetno oglišče:
xkon := R, ykon := 0, kot:= 0, korak := 2*PIIN
(2) izra čuna] koordinati naslednje točke :
xzač := xkon, yzač:= ykon,
kot := kot + korak,
xkon := R * cos (kot), ykon := R * sin (kot)
146
(3) prejšnjo točko poveži z njo:
Daljica (xzač, yzač, xkon, ykon)
(4) koraka (2) in (3) ponavljaj, dokler ni narisanih vseh N daljic.
Ustrezni podprogram prikazuje program 1. Podprogram Daljica v njem mo-
ra v resnici seveda povezati obe podani točki z ravno črto.
procedure Krog1 (xSred, ySred, R: real; N : integer);
{Program 1: Risanje kroga s kotnimi funkcijami}
const
PI = 3.1415926;
var
Program 1
xZac, yZac: real; {Zacetna tocka \
xKon, yKon:real; {Koncna tocka }
kot, korak: real; {Srediscni kot trenutne tocke in korak 1
i: integer ;{Stevec i
procedure Daljica (xZac, yZac , xKon, yKon: real) ;
begin
{Narisedaljico od tocke xZac, yZac do tocke xKon , yKon}
end { Daljica\;
begin {Krog1 ~
xKon := R; yKon := 0; kot:= 0; korak := 2*PI/N;
for i := 1 to N do
begin
xZac := xKon; yZac := yKon;
kot := kot + korak;
xKon := R * costkot): yKon := R * slntkot) :
Daljica (xsred+xZac, ysred+yZac, xsred+xKon, ysred+yKon)
end
end {Krog1 \.
Nazaj k celim številom
Prvo vrsto računalnikovega šestila smo tako spoznali. Pa nam ni mc preveč
všeč: kotne funkcije nastopajo v njem , te pa takoj zahtevajo računanje z
decimalnimi števili. Tako rač u nanj e pa je potrebno na enostavnih računalni­
kih, kot je na primer Spectrum, posebej sprogramirati, tako da je običajno
147
znatno po časnejše od računanja s celimi števili. Poskusimo zato poiskati
kakšen postopek, kjer nam bo računanje s celimi števili povsem zadostovalo.
Kot se spomnimo, nam je pri risanju daljice to uspelo .
Ker smo mojstri, nam bo uspelo tudi pri krogu . Seveda pa bo treba pred
končnim programom streti še nekaj orehov. Zato si oglejmo krožnico podro-
bneje. Najprej si jo zato narišimo (slika 2) . Njeno središče za začetek postavi-
mo v izhodišče . Izberimo na kro žnici poljubno točko T in njeni koordinati
označimo z x in y. Označimo z S središče kroga, s T' pa projekcijo točke T
na os x. Kot vemo, je krožnica spoimerom R ravno množica tistih točk, ki so
od središča oddaljene za R. Tako je dolžina daljice ST ravno R, dolžina daljice
ST' je x, dolžina daljice T'T pa je y. Ker je trikotnik ST'T pravokoten, velja
po Pitagorovem izreku:
T T4 / /Q
-c
" /-,
<
/ " "
/
/
/
/
/
/
/
/
/
Slika 2. Skica naše naloge - zrcaljenja
148
(1 )
Ker smo točko T izbrali povsem poljubno, velja ta zveza za vse točke krožnice.
Od tod pa hitro vidimo, da so na krožnici tudi zrcal ne slike točke T glede na
os x (TI na sliki 2), glede na os y (T2 ) ter glede na središče (T3 ) . (O tem se
lahko sami kaj hitro prepričate.) Pa še eno zrcaljenje upoštevajmo: zamenjajmo
obe koordinati (T4 v sliki 2). Ta zamenjava se na sliki odraža kot zrcaljenje na
premico O, ki razpolavlja kot med osema x in y. Povzemimo ta razmislek: če je
na krožnici točka (x, y), so na njej tudi točke (-x, V), (x , -y), (-x, -yl,
(y, x), (-y, x), (y, - x ) ter (-y, -x). Krožnico bomo tako lahko risali na osmih
krajih hkrati : kakor hitro bomo našli koordinate ene točke na krožnici, bomo
vedeli še za zgornjih sedem zrcalnih točk . (Nekaj izjem je, ko je točk nekaj
manj. Jih znate poiskati sami?) Zato bo dovolj, da narišemo le osmino krožnice
(denimo od osi x pa do premice O), preostale dele pa narišemo s pomočjo
zgornj ih zrcaljenj.
Še nekaj si na hitro oglejmo. Če točka T(x, y) ni povsem na krožnici, izraz
(2)
meri razdaljo točke Tod krožnice in mu bomo rekli odmik točke od krožnice.
Bliže ko je točka krožnici, bližji je odmik O; N(x, y) je enak nič le pri točkah
krožnice. Znotraj kroga je odmik negativen, zunaj njega pa pozitiven. Zato nam
bo odmik dragoceno sodilo, ki nam bo pomagalo izbirati točke.
Sedaj pa se lotimo iskanja točk na krožnici. Od zadnjič se še spomnimo, da
pri izbiri točk na računalnikovem papirju nimamo povsem prostih rok: po-
črnimo lahko le točke s celoštevilskimi koordinatami. Privzemimo zato, da je
polmer kroga celo število. Potem za eno točko na krožnici takoj vemo: točka
(R ,0) je to,v kateri smo začeli risati krog pri prejšnjem postopku. Njen odmik je
seveda enak 0, kot se lahko sami hitro prepričate. Postavimo se torej v to
točko in se iz nje ozrimo naokrog.
Ko izberemo eno od točk, lahko pot iz nje nadaljujemo le v eno od njenih
osmih sosed (slika 3) . (Po analogiji z zemljepisnimi kartami smo sliko označili
s stranmi neba tako, da je sever S zgoraj, ostale strani pa si slede na običajen
način.) Podobno kot pri dalj ici lahko krog teh osmih sosed takoj zožimo na
dve, na tisti dve pač, za kateri vemo, da med njima vodi krožnica. Denimo, da
iz izbrane začetne točke začnemo krožnico risati v protiurnem smislu. Potem
vemo, da krožnica vodi navzgor in v levo. Ko tako korakamo od točke do
točke, vemo, da vse do presečišča krožnice s premico O krožnica vodi med
severno in severozahodno sosedo. Pa nista obe sosedi enako dobri: ena je dlje
149
od kro žnice kot druga . Bolj ši od obeh možnih korakov je seveda t ist i, k i nas
privede v točko, katere odmik je kar najmanjši .
Severni korak nas iz točke T(x, y) privede v točko Ts(x, y +ll. severoza-
hodn i pa v točko Tsz(x-l , y+l) . Poglejmo, za koliko sev posameznem pr ime-
ru spremeni odmik.
N(x,y+l) -N(x,y) =x2+(y+1) 2_R2_ (X2+y2_R2) =2*y+l
N(x-l, y+l) - N(x, y) = (x_l) 2+(y+l)2_R2_(x2+y2_R2) = 2*(y-x+1)
Tako , pa smo pri postopku ! Začetno točko poznamo, njen odmik ravno tako ,
vemo pa tudi , kako izbrati naslednjo točko . Zapi šimo torej postopek :
sz S SV
Ef} Ef} Ef}
Z Ef} EfJv
Ef} Ef}EfJ
JZ J JV
Slika 3 . Sosede točke
150
(1) postavi se v začetno toč ko:
x := R, y := O,odmik := O
(2) počrni točke :
(x,Y), (x,-Y), (-x,Y) , (- x ,- y ),
(y,x) , (y,-x) , (-y,x) r (-y,-x)
(3) izračunaj odmik severne in severozahodne sosede:
odmikS := odmik + 2 * y + 1, odmik SZ := odmik + 2 * (y-x+l)
(4) če je A8S(odmikS) manjše od A8S(odmikSZ) ,
potem y := y + 1, odmik := odmikS
sicer x := x - 1, y := y + 1, odmik := odmikSZ
(5) korake (2), (3), (4) in (5) ponavljaj, dokler ni x manjši od y .
procedure Krog2 (xSred , ySred, R : integer) ;
{Program 2 : Risanje kroga v celih stevilih }
var
Program 2
x,y : integer; { Trenutna tocka )
odmik, {Odmik trenutne tocke ]
odmikS,odmikSZ : integer; {ter njene severne in severozahodne sosede ~
procedure Pika (x , y: integer) ;
begin
{Pocrni tocko x , y)
end {Pika) ;
begin { Krog 2 )
x := R; y := 0; odmik := 0;
wh ile x '>v do
begin
Pika (xSred+x, ySred+y) ; Pika (xSred-x, ySred+y) ;
Pika (xSred+x, ySred-y); Pika (xSred-x, ySred-y);
Pika (xSred+y, ySred+x); Pika (xSred -y, ySred+x) ;
Pika (xSred+y , ySred-x); Pika (xSred-y , ySred-x);
odmikS := odmik + 2 * y + 1; odmik SZ := odmik + 2*(y-x+l);
it A8S (odmikS) < A8S (odm ik SZ) then
begin y := y + 1; odm ik := odmikS end
else
begin x := x - 1; y := y + 1; odmik := odmikSZ end
end
end { Krog2~. 151
Preden zapišemo postopku ustrezen program, opravimo še drobno izbolj-
šavo. Pri računu odmikov v koraku (3) vidimo, da se odm ika spreminjata vzpo-
redno s spreminjan jem x in y , zato ju lahko le enostavno popravljam o in ne
vedno znova rač u namo . Tako izboljšanemu postopku ustreza program 2. Pro-
gram seveda še ni popoln : včasih počrni kakšno točko preveč (če ste odgovor ili
na eno od gornjih vprašanj, tudi veste, kdaj). Podprogram Pika v njem počrn i
točko s podanima koord inatama .
Krožni lok
Končno se lotimo še krožnega loka . To je del krožnice. Zaradi enostavnost i bo-
mo vzeli , da ga podamo z njegovim središčem, polmerom ter začetno in
končno točko. Tako začetna kot končna točka lahko ležita kjerkol i na kro ž-
nic i, dogovorimo se le, da bomo lok risali v protiurnem smislu. Risali ga bomo
po korakih od začetne točke proti končni. Podobne bližnjice, kot smo jo ubra-
li pri krogu, ki smo ga risali na osmih koncih hkrati , si tu torej ne moremo pri-
voščiti.
Način risanja pa bo podoben risanju kroga. Postavili se bomo v začetno
točko, izračunali njen odmik od krožnice ter korakali proti končni. Na vsakem
koraku se bomo premaknili v eno od toč kinih sosed in to počeli , vse dokler
ne bomo prikorakali do končne točke. Kot vemo, ima vsaka točka osem sosed.
Pri dalj ici in krogu smo to število lahko hitro zožili na dve, ki se potem med
risanjem nista več spreminjali, na tisti dve, med katerima je vodila dalj ica ozi-
roma kro žnica. Tu se bomo morali malo bolj potruditi: primerjati bomo mora-
li odmik treh sosed in med njimi izbrat i najugodnejšo. Te tri sosede bomo
izbrali na vsakem koraku posebej.
Najprej si oglejmo, kako bomo izbrali prave tri sosede. Spet nam bo poma-
galo naše znanje o krogu. Postavimo njegovo središče v izhodišče in si oglejmo
ponovno sliko 1. Vemo , da je v vsaki točki T na obodu kroga kro žnica pravo-
kotna na polmer ST, ki jo veže s središčem . V točki (R, O) je krožnica nav-
pična, v točki (O,R) pa vodoravna . Poskusimo sedaj določiti daljico, pravo-
kotno na daljico ST. Daljica STveže točko (0 ,0) s točko (x, v) . Njeno smer do -
ločata x in y : večji je y pr i izbranem x, bolj strma je dalj ica, večji je x pri izbra-
nem y , bolj položna je. Pravimo , da sta x in y parametra smeri. Parametra pra-
vokotne smeri pa sta -y in x, pravokotna dalj ica iste dolžine torej veže točko
(0,01 s točko (-y, x l. (To je le ena od pravokotnih daljic te dolžine. Znate
poiskati še drugo?) Iz točke T bomo torej pogledali proti točki (x-y, y+x) ter
pr i risanju kroga upoštevali tri sosede, med katerimi bomo pogledali, in sicer
eno navpično, eno vodoravno ter poševno med njima. Kako jih določimo?Vo-
152
--
doravno sosedo določa predznak -y, navpično predznak x, natančneje pa ju
določimo tako kot pri dalj ici. Poševna povzroča še najmanj preglavic, zakaj,
lahko že sami razberete iz slike 3. Tudi postopka podrobneje ne bomo opiso-
vali, gre pa takole :
Program 3
procedure Kroznilok (xSred. vSred, R: integer;
xZac, vZac, xKon, vKon: integer) ;
{Program 3: Risanje kroznega loka s celimi stevili 1
var
x, v: integer; { trenutna tocka ')
dx, dv: integer; { vodoravni in navpicni korak )-
odmik: integer; {odmik trenutne tocke 1
odmvod:integer; {odmik vodoravne sosede ~
odmnav: integer; {odmik navpicne sosede}
odmpos: integer; {odmik posevne sosede ~
procedure Pika (x, v: integer);
begin
{Pocrni tocko x, V ~
end {Pikaj;
begin [Kroznll.ok }
x := xZac-xSred; V := vZac-vSred; odmik := x*x + v*v - R*R;
repeat Pika (xSred+x, vSred+v);
it V> 0 then dx := -1 else dx := 1;
it x > 0 then dv := 1 else dv :> -1;
odmvod:= odmik + 2 * x * dx + 1;
odmnav := odmik + 2 * V * dv + 1;
odmpos := odmvod + odmnav - odmik;
it abs (x) < abs (V) then
it abs (odmvod) < abs Iodmpos] then
begin x := x + dx; odmik := odmvod end
else
begin x := x + dx; V := V+ dv: odmik := odrnpos end
else
it abs (odrnnav) < abs (odrnpos] then
begin V := V+ dv: odmik := odmnav end
else
begin x := x + dx; V := V+ dv: odmik := odmpos end
until (x+xSred = xKon) and (v+vSred = vKon)
end {KrozniLokJ.
153
(1) postavi se v začetno točko in iz ra čuna] njen odmik
(2) počrni trenutno točko
(3 ) s pomočjo predznakov - y in x določ i vse tri sosede
(4) izračunaj odmike vseh treh sosed
(5) izmed sosed izberi tisto , katere odmik je najmanjši ter se preseli vanjo
(6) ko rake (2), (3) , (4) in (5) ponavljaj. dokler ne prispeš v konč no točko
Ustrezen program prikazuje program 3 . Program se seveda zanaša, da smo
končno toč ko točno podali . V nasp rotnem prime ru se prog ram nikol i ne
ustavi.
Ob koncu velja tako pristaviti še nekaj besed orisanju splošnejših krogov
in lokov . Pri njih polmer ni ravno celo število, pa tud i središče nima celošte-
vilskih koordinat. Običajno pri tem postopamo tako, da središče postavimo v
najbližjo točko s celoštevi lskimi koordinatami ter polmer zaokrožimo do naj-
bližjega celega štev ila. Pri risanju loka se pri tem znajdemo pred dodatnim
problemom: prestaviti moramo tudi začetno in končno točko loka. Enostavno,
boste rekli: tako kot pri središču zaokrožimo njene koordinate . Pa ni čisto
tako! Poglejmo , zakaj. V programu 3 smo se pri risanju zanašali na to, da sta
obe točki točno na krožnici. Pri prestavljanju pa se lahko zgodi, da točko malo
narobe prestavimo, da torej narisana krožnica prestavljeno točko malo zgreši.
Pri začetni točki to še ni hud problem, huje je to pri končni , saj se program
ustavi le, če krožnica točko natančno zadene.
Pa premislimo, kako bi tudi ta problem rešili. Zato še enkrat poglejmo,
kako izbiramo točke pri risanju krožnice . Ko eno točko poznamo, za naslednjo
izbe remo tisto med sosedami , pri kateri je odmik N(x, y) najmanjši . Kot se
spomnimo, nam Nix, y) meri oddaljenost narisane točke od prave krožnice.
Pri risanju narišemo tiste točke, ki so krožnici najbližje. Pri prestavljanju
končne točke moramo zato z uporabo odmika pogledati, ali ni morda katera
od sosed nove točke bliže krožnici kot ta točka. Za končno točko moramo
tako vzeti tisto, pri kateri je odmik N(x, y) najmanjši. Poskusite program tako
sami dopolniti!
Za konec pa še nekaj nalog. yse so povezane z risanjem loka. Lok namreč
v praksi podajamo na več različnih načinov. Prvega smo že povedali : podamo
središče, polmer ter začetno in končno točko. Tu je podatkov preveč: pri obeh
točkah moramo paziti, da sta od središča oddaljeni natanko za polmer. Pa
sprostimo ta pogoj: podajmo lok s središčem, polmerom ter dvema točkama.
Prva določa začetek loka tako, da je začetna točka loka presečišče krožnice in
154