Informatica št. 4 , letnik 1977 
kako narišemo 
pravilni mnogokotnik ? 
v. batagelj 
UDK 681.3:513 
PNT, VTO matematika in mehanika Ljubljana 
Namen sestavka jOjOb reševanju navidez enostavne naloge: narisati pravilni mnogokotnik z vsemi di­
agonalami, seznaniti bralca z nekaj osnovnimi značilnostmi uporabe risalne naprave (plotterja)- V 
sestavku se srečamo tudi s teorijo grafov (Kulerjev izrek), z uporabo rekurzije pri programiranju 
in s prevedbo rekurzivne rešitve v iterativno, 
HOW TO DRAW A REGULAH POLIGON? - In the paper some basic characteristics of plotter-programming 
are illustrated by solving the problem; write a program for drawing the regular polygon with ali 
diagonalso The uso of recursion and the transformation of the recursive solution to an iterative 
one are also included« 
Haloga: 
Sestavi program, ki bo na risalni napravi 
(plotterju) narisal pravilni mnogokotnik z 
vsemi diagonalami; 
kateri je posvečen pričujoči sestavek, sodi v 
tisto področje programiranja, ki mu radi pravi­
mo "igračkanje na računalniku"; nekateri pa ce­
lo: "kako leihko z računalnikom zapravljamo čas 
(in denar) ?l". 
Toda to je le ena plat<medalje. Poglejmo še 
za hip na drugo stran«]Programiranje je precej 
razgibana dejavnost in zahteva o<i progretmerjev 
nenehno učenje. Kajti, če hočemo nekaj upora­
bljati, moreuno to tudi dobro poznati in obvla­
dati. In prav tu se rado pojavi "igračkanje", 
v katerem se prepletajo: 
- preizkušanje in iskanje (za programerja) 
novih programirnih tehnik in konceptov; 
- zanimivost in "čistost" naloge; 
- kratkost rešitve (programa) - od nekaj 10 
do nekaj 100 vrstic; 
... seveda, nove tehnike in koncepte lahko po­
navadi veliko hitreje in temeljiteje preizkusi­
mo s posebej v ta namen pripravljenimi testnimi 
programi ... ali, če povzamemo za [s] : "Čemu 
zabresti v morje težav, ki se pojavijo pri ra­
čunanju števila ^ , recimo, na milijon deci­
malnih mest natančno ? Nedvomno prvih sto Jeci-
malk, znanih že stoletja, zadostuje za reševa­
nje kateregakoli realnega problema, kakršne 
srečsuno v fiziki ali astronomiji. Čemu torej 
tolikšni napori za nepotrebno natančnost 7" ooo 
In vendar so računalniki mleli podobne probleme 
ure in ure. Omenimo le še, da je naš rojak ba­
ron Jurij Vegai že leta 179* (brez računalnika) 
izračunal ^T na 140 mest natančno. 
Večina programerjev, ko se sreča z interaktiv­
nim delom, piše programe za razne igrice; ko pa 
se srečamo z rekurzije, skoraj ne moremo mimo 
naloge o osmih kraljicah f^5, 6, 7, 8, 9, loJI . 
Toliko v pojasnilo na morebitni ZAKAJ ? 
S problemom uporabe risalne naprave sem se sre­
čal, ko sem se odločil, da bom v CLUSE £^1J 
vključil podprogram za risanje dendrogramov 
(dendrogram = grafični prikaz drevesa združeva­
nja). Preden sem se spoprijel s tem problemom, 
sera se raoral privaditi rutinam, ki omogočajo 
delo z risalno napravo. Slučajno sem tedaj v 
neki knjigi iz teorije grafov zagledal sliko 
polnega grafa (= pravilni mnogokotnik z vsemi 
diagonalami) in seveda sem se nemudoma vprašal: 
Ali bi ga znal narisati 7 
Preden nadaljujemo, naj za bralca, ki ni domač 

49 
z risalno napravo, povem, da je osnovna akcija, 
ki jo omogočajo rutine za risanje, premik pere­
sa po premici iz točke, v kateri se trenutno 
nahaja, v izbrano točko. Pri tem je pero ali 
spuščeno (« risanje) ali pa dvignjeno (= pomik 
brez risanja). 
Za začetek našega ubadanja z nalogo poskusimo 
odgovoriti na vprašanje: Kako bi nalogo rešili 
sami z ravnilom, šestilom in kotomerom 7 
Recimo, da želimo narisati pravilni n-kotnik. 
Tedaj narišemo najprej krožnico in jo z h to­
čkami T,, Tp« •*• » ^n (oglišča mnogokotnika) 
razdelimo na n enakih lokov. Nato povežemo 
vse točke eno z drugo z daljicami (diagonalami). 
To lahko povzamemo v pi^o zamisel rešitve: 
1. določi koordinate točk T. , i = l,.,.,n 
2. za vsak (i,j) : l^i,js^n ponovi 
2.1. poveži točki J.. •S. z daljico 
Ta rešitev vsebuje dva spodrsljaja; 
- če je , i «= j , poskušamo z diagonalo pove­
zati točko T. samo s sabo; 
- vsako diagonalo rišemo dvakrat, 
ki pa ju zlahka odpravimo, če se odločimo, da 
mora biti indeks j vedno večji od indeksa i. 
Tako dobimo drugo zamisel: 
1. 
2. 
določi koordinate točk T 
za vsak (i,j) : 1 
1,. ^ r •" - J-, . . • ,» 
i-<j^n ponovi 
poveži točki 
^i 
in •ff. z daljico 
Vrstica 2 v tej rešitvi nami j«sšča proste roke 
v izbiri vrstnega reda preborai snoži.ce { (i, j) s 
l^i<j^nj . Ena izmed najpreprostejših 
določitev vrstnega reda je podana v naslednji 
zamisli rešitve: 
1. 
2. 
2.1. 
2.2. 
določi koordinate točk T. , i •> l,.,,,n 
za i » 1,,,., n-1 ponovi 
za j - i+1,..., n ponovi 
prestavi dvignjeno pero v točko T. 
nariši daljico (od T.) do točke T. 
Toda v tej rešitvi nismo niti poskusili upošte­
vati eno od osnovnih zahtev pri programiranju 
dela risalne naprave: 
celotna pot, ki jo pri risanju opravi pero 
risalne naprave, naj bo kar se da kratka. 
^o je predvsem zahteva po (časovno) učinkoviti 
rabi risalne naprave. 
Ali lahko pridemo do boljše rešitve ? 
Dolžina vsake poti peresa, katere rezultat je 
neka izbrana risba, je navzdol omejena z vsoto 
dolžin dejansko narisanih črt na tej risbi. 
Potemtakem lahko dobimo boljšo rešitev le tako, 
da zmanjšamo skupno dolžino premikov dvignjene­
ga peresa. Najugodneje je seveda, če znamo ris­
bo narisati v "eni potezi" ~ ne da bi dvignili 
pero. 
Tu nam priskoči na pomoč Eulerjev izrek iz teo­
rije grafov [^t-l .Za razumevanje tega izreka 
pojasnimo najprej dva pojma: Sekli bomo, da je 
risba povezana, če lahko iz vsake točke risbe 
pridemo po risbi v vsako drugo. Točka risbe je 
liha natanko takrat, ko je ali prosto krajišče 
črte, ki pripada risbi, ali pa se v njej sreča 
liho število črt; dmigače je soda. 
Sedaj že lahko prevedemo Eulerjev izrek v ter­
minologijo našega problema: 
Če je na povezani risbi 2k'ylihih točk 
(število lihih točk je vedno sodo), potem 
lahko risbo narišemo v k potezah. Vsaka 
od teh potez se začne in konča v lihi točki. 
Povezano risbo brez lihih točk lahko narišemo 
v eni potezi s sklenjeno črto (risanje konča­
mo v točki, v kateri smo ga začeli). 
Za primer si oglejmo risbo; 
Na njej je šest lihih točk, ki so oštevilčene s 
številkami od 1 do• 6 . Torej jo lahko nari­
šemo v treh potezali. Na primer takole: 
Povrnimo se na našo nalogo ! Ali lahko kak 
(vsak ?) n-kotnik zvsemi diagonalami narišemo 
v eni potezi ? 
Ker so presečišča diagonal sode točke, nam lah­
ko povzročajo težave le oglišča mnogokotnika. 
Vsako oglišče je povezaao z diagonalami z vsemi 
ostalimi; to pa so tudi vse črte, ki se v njem 
stikajo. Zato bodo oglišča liha/soda, če bo n 
sodo/liho število. Torej lahko v eni potezi na­
rišemo le lihe mnogokotnike (in 2-kotnik « da-
Ijica). 
Toda, KAKO ? 

so 
Recimo, da želimo narisati 2k+l - kotnik« Ka­
kor vemo, ga je mogoče narisati a sklenjeno 
črto v eni potezi. To velela tudi za 2k-l -
kotniko Ali bi znali narisati 2k+l - kotnik, 
če že vemo, kako narišemo 2k-l kotnik ? Če to 
znamo, potem znamo narisati poljuben lihi mno-
gokotnik; saj, ker znamo narisati trikotnik, bi 
znali narisati tudi petkotnik; ker znamo tega, 
bi znali tudi sedemkotnik; ..o 
Poglejmo, kam nas pripelje ta zamisel postopka 
risanja 2k+l - kotnika: 
lo nariši 2k-l - kotnik 
2. nariši ostanek: diagonale, ki imajo eno 
krajišče v točki T-j. ali točki Tgjj^, 
Kako narisati ostanek ? 
Tudi vse točke ostemka so sode. Torej ga lahko 
narišemo s sklenjeno črto v eni potezi. 
T, T, T, 
''2k-2 '^2k-l 
Ponuja nam se nekaj "smiselnih" risanj ostanka; 
toda paziti moramo še, da bosta risanje 2k-l -
kotnika in risanje ostanka vsklajena: točka, v 
kateri začnemo (in zaradi sklenjenosti tudi kon­
čamo) risati 2k-l - kotnik, mora biti začetek 
(in konec) risanja ostanka. Najbrž je najugod­
neje, če izberemo za to točko kar točko , T. , 
Tedaj lahko narišemo ostanek recimo takole (na 
začetku risanja se nahajamo v točki T, ): 
"narisi ostanek" 
1. iS i o 2, 3, 00., 2k ponovi 
1.1. č^ je i sod potem 
1.1.1. nariši daljico do 
druRače 
nariši daljico do T 
2k+l 
1.1 
lo2 nariši daljico do Tj 
narisi daljico do T^ 
2k 
Ce jezik,v katerega programiramo, poana rekur-
zivno podprograme, smo s tem risanje lihega 
mnogokotnika 2e ugnali. 
Recimo, da je dana procedura ortado(i) , ki 
nariše daljico iz točke, v kateri se pero tre­
nutno nahaja, do ogliSča T^^ , potem bi risanje 
lihega mnogokotnika opisali v Pascalu z nasled­
njo rekurzivno proceduro: 
procedure risilih( m: integer ); 
I m - red mnogokotnika; liho število| 
var i: integer; 
begln 
if a >• 1 then bep:in 
risilih( m-2 ); 
for i := 2 t£ m-1 do bep;ln 
crtado( m - i mod 2 ); crtado( 1 ) 
end; 
crtado( 1 ) 
end 
end J risilih J ; 
Kaj pa, če jezik, v katerega programiramo, no 
pozna rekurzije ? Običajno se moramo tedaj za­
teči k uporabi sklada; vendar to v našem prime­
ru ni potrebno, ker postopek vsebuje samo an 
rekurzivni klic. Take procedure ne zahtevajo 
"drevesnega mehanizma" in jih zato lahko pogo­
sto brez posebnih težav prepišemo v Iterativno 
obliko. Proceduro risilih bi tako zapisali v 
Structranu £3] '• 
SUBPOUTINE /JIISI LIH ( M 
N = 3 
tfHILE < N .LE. M ) DO 
NM = N - 1 
FOfii ( I = 2, NM ) DO 
CALL ČRTA 00 ( N -
CALL ČRTA DO ( I ) 
ENOFOR 
CAIV CRTft DO ( 1 ) 
NI a N • 2 
ENOdHILE 
REtrURN' 
END 
) 
HOD(Io2) ) 
Tako, lihe mnogokotnike znamo narisati v eni 
potezio Kako pa je a sodimi 7 
Hecimo, da želimo narisati 2k - kotniko Potso 
nam Eulerjev izrek pove, da bomo morali vsaj 
k krat pomakniti pero "po zraku" v drugo točkoj 
pa tudi, da to zadostuje,, Podobno kot proj, 
lahko problem razbijemo na dva podproblecia: 
- nariši 2k-l - kotnik 
in 
- nariši ostanek: diagonale, ki imajo eno 
krajišče v točki Tov ° 
Prvi podproblem je naš stari znanec - risanje 
lihega mnogokotnika. Torej aoramo premisliti Is 
še risanje ostanka. Ta sedaj izgleda talsolss 
21r-l 

51 

S2 
Ker mora biti risanje 2k-l - kotnika in ostan­
ka vsklajeno, Je najenostavneje začeti risanje 
v točki T, C Tako dobimo naslednji postopek: 
1. 
2o 
<^ 0 X o 
C o<^ o 
2.3, 
3o 
pomakni se v točko T, 
2k-i - kotnik 
za i •=• 1, 2, .o., k-I 
nariši daljico do 
nariSi daljico do 
pomakni se v točko 
nariSi daljico do 'i'-^ 
in nariši 
ponovi 
'''2k ' 
^2i » 
^"21+1 
S tem smo obdelali obe možnosti (lihe In aode 
mnoKOkotnike). Preostane nam le 6o, da Ju zdru­
žimo v enoten proe;ram za risanje poljubnega 
mnogokotnika: 
P303RAM TETIVE( INPUT, TAPEI«°INP1JT ) 
C0M>1OMi / TOČKE / X(5l>)» Y(50) 
04Tft PI / 3. U159 26536 / 
C»LU 30PRI 
o PREBEREMO. RED M IN POLMER R MNOGOKOT^IKA 
RiBDK 149 o » M, R 
o OOLOgnO KOORDINATE OOLIS« MNOGOKOTNIKA 
Plo. JOPI/M 
FOR ( I = i"o M ) DO 
«(I) = R t» COS(IOFI) 
r(I) = R O SIN(IOFI) 
E^DI'0^1 
o NARigEMO MN080K0TNIK 
CALU »OMIK V < 1 I 
IFI ( W00(Mi2» „EQ. I ) THEN 
CALL RISI LIH ( M )' 
EUBEI 
*1M a M - 1 
CALL RISI LIH ( MM ) 
FO^i ( I =; 2« MM. 2 ) 00 
CALL' CRTA 00 < M ) 
CALL. ČRTA 00 ( I » 
CALL' POMIK V ( 1*1 ) 
ENDFOR 
CALL CRTA. 00 ( M ) 
EMOIF ^ 
C4LU 2APRI 
EMD 
V programu smo poleg podprograma rieilih , ki 
ga že poznamo, uporabili nekaj podprogramov, ki 
omogočajo delo z risalno napravo. Ti so odvisni 
od osnovnih rutin za risanje, ki se od računal­
nika do računalnika spreminjajo. Za računalnik 
Cyber na HRO v LJubljani Izgledajo takole fllj t 
SJBfOJTiNE CRTfl 00 ( I ) 
COM^IOMi / TOČKE / X(5;)l » Y(50> 
C4LLI »LINE ( K(I)« vd), I ) 
REirjRMi 
SJB^OJTINE POMIK V ( I i 
COMMOM! / TOČKE / K<50)(i Y< 50 ) 
CftLU »LINE ( X<I)o Vil)o O ) 
REirURMi 
EMO' 
SJB^^OJTINE ODPRI 
CALLI 'OPEV ( 11,, 6LTETIVE I 
C4LLI 'SCALE ( Uo« Coo 9i'o(, llo« II. 
B£ITJR>J 
E^JO 
SJB^OJTINE ZAPRI 
CALLI »CL05E 
RtffJRMi 
EMD 
Opomba; Bralec, ki ima dostop do Cybera, lahko 
zahteva izpis priročnikov za delo z risalnimi 
rutinami iri za atructran s Scope karticama: 
BEGIN.MINI, 
MANUAL,PLOCTKK,STfiUCTRAN, 
Na koncu naj omenim soroden in nekoliko "upora­
bno jSi" (vsuj za tisto, ki se ukvarjajo z prafi) 
problem, pri reBovanJu katerega bi nam nabrane 
izkušnjo precej koristilo. To Je: oeotavi pro­
gram, ki bo na podoben način, kot smo ga upora­
bili pri risanju mnoi;;okotnikov, narisal duni 
neusmerjeni graf, v katerem poljubni dve točki 
veže največ ena povezava. Nekaj koristnih idej 
v tej smori Je najti na zadnjih straneh sestav­
ka [sl . Problem si lahko dodatno zabelimo s 
zahtevo, naj bodo točke grafa razvrščene po 
krožnioi tako, du se bodo povezave sekale čim 
nanjkrato To pa Jo že zelo težek problemo 
LITiiHATUHA 
£l3 V.Batagelj: CLUaE - program za hierarhično 
razvrščanje v skupine; priročnik., LJubljana^ 
1977 
£23 V.Batagelj, T.Pieanski: Delno usmerjeni Eu-
lerjevi grafi; (rokopis) seminar za računal­
niško in nutnorično matematiko, LJubljana, 
1977 
ITjl V.Batagelj, K.ZakraJšok: Structran, Infor-
matica 75, Bled, 1975 
£4]] DoCvetkovid, M.Milic: Teorija grafova i nje­
ne primeno; Naučna knjiga, Beograd, 1977 
£53 O.J.Bahl, K.lV.DiJkstra, C.A„H,Hoare: Sfcruc-
tured programming; Academic Press, London, 
Now York, 1972 
£ 63 F.Gruenberger, G,Jaffray: Problema for Com­
puter Solution; John Wiley & Sons, W9w iork^ 
1965 
£73 H.BoKieburtz: Structured programming und 
problem solving with PL/1; Prentice-llall, 
Knglewood Cliffa, Now Kersej, 1977 
{e]! J.Nievergelt, J,O.Farrar, £„MoReingold: GOB-
puter approaches to mathematical problema, 
Prentico-Hall, Eng. Cliffs, No)fers®y, 197* 
£ 93 M.BoWells: Klements of Combinatorial Compu-
ting; Pergaraon Press, OxfoFd, 1971 
OLOJ N.Wirth: AlRorithms+Data Strcturea^Programs; 
Prontioe-Hall, Jing.Cliffs, fl.yeraey, 1976 
£ll3 E.ZakrajSek: Uporaba risalne naprave v HHC; 
priročnik, LJubljana, 1975