Hvordan plotter maskinen en sirkel?

Jeg har grublet på spørsmålet med hvordan en sirkel blir formet i et koordinatsystem x y slik skjermen på en digital enhet er. Jeg fant noe som heter midpoint circle algorithm og jeg forstår ikke helt algoritmen men den tar imot et koordinat for senter av sirkelen som skal tegnes og en radius og tegner åtte punkter av gangen helt til sirkelen er komplett.

Når du lager en sirkel i et tegneprogram så vil jo den vises på skjermen med en gang fordi maskinen er så rask men egentlig så tegner den hvert punkt og sånn jeg forstår det så er det denne algoritmen som er i bruk men det kan hende det finnes andre. Selv begynte jeg å tenke på radianer og polarkoordinater og alt mulig for det naturlige ville jo være å finne hvert punkt i sekvens heller enn å tegne 8 steder på en gang. Men denne er ikke avhengig av radianer eller polarkoordinater.

Sjekk ut en sakte demonstrasjon:

(DU MÅ GÅ INN PÅ BLOGGPOSTEN FOR AT KODEN SKAL KJØRE HER)

Tegner sirkel på x=200 y=200 i et 400×400 felt

Radius:

Operasjoner:0

dx:

dy:

decisionOver2

I artikkelen jeg viser til på wikipedia bruker algoritmen i kode bitshift-operator til venstre. En artig ting jeg lærte her er at bitshifting av et heltall med en plassering er det samme som å gange tallet med to. Så det ble lettere å tenke på diameter som radius ganger 2 enn diameter som radius bitshift 1.

Hvis man har et binærtall: 0110 (4) og bitshifter dette til venstre: 1100 så blir det 8. Bitshifter man en gang til har man 11000 og det er det samme som 16 altså en dobling til. Det er litt stilig og egentlig logisk men jeg har aldri visst det før.

Midpoint circle algorithm er først implementert i Assembly for lenge siden og jeg tenker at å bitshifte radius en gang til venstre for å gange den med to sikkert er mer effektivt fordi en multiplisering antakeligvis inkrementerer noen tall så og så mange ganger og derfor er sikkert multiplikasjon en kostbar operasjon men jeg tror at dagens kode vil lese alle heltall ganger to som en heltall<<1 altså bitshifte heltallet en til venstre for jeg vet at det er gjort mye for å optimalisere. Algoritmen bruker kun heltall og et avvikstall bestemmer hvordan man skal justere x og y slik at det blir en sirkel. Noen variabler i koden forstår jeg ikke ut i fra navngivingen men jeg har refaktorert ut bitshiftoperasjonen:

Det er interessant at algoritmen kun bruker heltall altså ingen flyttall og «decisionOver2» er et avvik definert som 1-diameter i begynnelsen men det endrer seg. Det hele handler om å bestemme x og y og antall operasjoner øker med radius og det er helt sikkert et forholdstall men jeg føler det er så mye å tenke på på grunn av at hver iterasjon tegner utover fra fire punkter.

Jeg husker vi problematiserte sirkelen på barneskolen også med en passer og jeg ser at om man endrer dx i utgangspunktet vekk fra 1 vil man få noe annet enn en sirkel. Samme gjelder endringer i dy. Men sirkelen må være ganske rasjonell ut i fra at dx og dy begynner på 1 og senere i koden endres den hver gang den skal endres med 2.

For hver operasjon bestemmer man på bakgrunn av kriteriet «decisionOver2» i koden (definert som et avvik i C versjonen av koden) både om man skal øke y og om man skal minke x. «decisionOver2» endrer seg også hver gang man tar denne beslutningen og det er forbløffende at det skaper en sirkel for jeg klarer ikke vri hodet rundt konseptene. Ganske stilig.

Blogglistenhits

Én kommentar til «Hvordan plotter maskinen en sirkel?»

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert. Obligatoriske felt er merket med *