Midpoint körrajzoló algoritmus
Bresenham nevéhez fűződik szintén egy olyan körgeneráló algoritmus, amely eleget tesz azoknak a kritériumoknak, hogy egész aritmetikát használ és alkalmas akár hardver implementációra is. Szintén növekményes algoritmust kapunk, tehát <math xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow>
<mo stretchy="false">(</mo><msub>
<mi>x</mi>
<mrow>
<mi>i</mi><mo>+</mo><mn>1</mn>
</mrow>
</msub>
<mo>,</mo><msub>
<mi>y</mi>
<mrow>
<mi>i</mi><mo>+</mo><mn>1</mn>
</mrow>
</msub>
<mo stretchy="false">)</mo>
</mrow>
<annotation encoding="MathType-MTEF">
</annotation>
</semantics></math> kiszámítását az <math xmlns="http://www.w3.org/1998/Math/MathML">
<semantics>
<mrow>
<mo stretchy="false">(</mo><msub>
<mi>x</mi>
<mi>i</mi>
</msub>
<mo>,</mo><msub>
<mi>y</mi>
<mi>i</mi>
</msub>
<mo stretchy="false">)</mo>
</mrow>
<annotation encoding="MathType-MTEF">
</annotation>
</semantics></math> meghatározása után nyerjük. Az algoritmus során a második nyolcadot tárgyaljuk, a többi pont meghatározható a tengelyekre és a szögfelező egyenesekre történő tükrözésekkel.
A stratégiánk az, hogy két pixel pont közül azt válasszuk ki, amelyik közelebb áll a kör ideális nyomvonalához. Kiszámítjuk a kör 0-ra rendezett implicit egyenletéből kapott függvény helyettesítési értékét, a két pixel pont által meghatározott szakaszközéppontnál (midpoint), s a kapott érték előjelétől függően választunk a határpontok közül.
Az algoritmus részletes levezetését, és a használt képleteket megtaláljuk a következő anyagban: Dr. Kovács Emőd: Fejezetek a számítógépi grafikából ,Szakanyag KOMA 1995/1-777 pályázat támogatásával. (67 oldal jegyzet) http://www.ektf.hu/~emod/KOMA.pdf
Bizonyos alkalmazásokban gyakran kell köröket és ellipsziseket rajzolni. Ezen alakzatok előállításának algoritmusát alapfeladatnak tekintjük. Matematikai ismereteink alapján könnyen tudunk algoritmust készíteni, de ha csak egész aritmetikát szeretnénk használni, akkor ez már nehezebb feladat.
Tekintsük az origó középpontú R sugarú kör implicit egyenletét: x^2+y^2=R^2.
Ebből explicit függvény alakot nyerhetünk, ha két félkörívre bontjuk a kört, és y-ra kifejezzük: y=SQRT(R^2-x^2), y=-SQRT(R^2-x^2). Sajnos ilyenkor négyzetgyököt kell használnunk, amely igen pontatlan és lassú algoritmust eredményez.
Elég meghatároznunk az egyik félkörív pontjait, a többi pont az x tengelyre való tükrözéssel nyerhető. Ezt az elgondolást tovább fejlesztve – a kör szimmetriáját kihasználva – csak a negyedkör pontjait, sőt akár a nyolcadkör pontjait számoljuk ki, a többi tükrözéssel nyerhető. Nem számít speciális esetnek, ha a középpont az origóban van, hiszen ebből eltolással bármely kör előállítható.
Midpoint körrajzoló algoritmus levezetése
Pl. az <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mi>M</mi> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> középpont belül van, tehát a helyettesítési értéke negatív, ezért az <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mi>E</mi> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> pontot választjuk.
Legyen a döntési változók az i. lépésben <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>d</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math>.
Az előző <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>P</mi><mo stretchy="false">(</mo><msub> <mi>x</mi> <mi>p</mi> </msub> <mo>,</mo><msub> <mi>y</mi> <mi>p</mi> </msub> <mo stretchy="false">)</mo> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> pont alapján <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>d</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> meghatározható az <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mi>M</mi> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> pontban: <math display="block" xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>d</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo><mo>=</mo><mi>F</mi><mo stretchy="false">(</mo><msub> <mi>x</mi> <mrow> <mi>p</mi><mo>+</mo><mn>1</mn> </mrow> </msub> <mo>,</mo><msub> <mi>y</mi> <mrow> <mi>p</mi><mo>-</mo><mn>1</mn> </mrow> </msub> <mo>/</mo><mn>2</mn><mo stretchy="false">)</mo><mo>=</mo><msup> <mrow> <mo stretchy="false">(</mo><msub> <mi>x</mi> <mi>p</mi> </msub> <mo>+</mo><mn>1</mn><mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo>+</mo><msup> <mrow> <mo stretchy="false">(</mo><msub> <mi>y</mi> <mi>p</mi> </msub> <mo>−</mo><mn>1</mn><mo>/</mo><mn>2</mn><mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo>−</mo><msup> <mi>R</mi> <mn>2</mn> </msup> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math>
Felhasználjuk, hogy <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>d</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math>-ből két eset vezethető le:
Ha <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>d</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo><mo><</mo><mn>0</mn> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> , akkor az <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mi>E</mi> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> pontot választjuk.
A következő pont esetén az (i1). lépésben legyen a döntési változók d(i1). Az ME középpontot vizsgáljuk. Az előző <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>P</mi><mo stretchy="false">(</mo><msub> <mi>x</mi> <mi>p</mi> </msub> <mo>,</mo><msub> <mi>y</mi> <mi>p</mi> </msub> <mo stretchy="false">)</mo> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> pont alapján d(i1) is meghatározható.
A növekményt <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>Δ</mi><mi>E</mi> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> -vel jelöljük <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <msup> <mrow> <mo stretchy="false">(</mo><msub> <mi>x</mi> <mi>p</mi> </msub> <mo>+</mo><mn>2</mn><mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo>+</mo><msup> <mrow> <mo stretchy="false">(</mo><msub> <mi>y</mi> <mi>p</mi> </msub> <mo>−</mo><mn>1</mn><mo>/</mo><mn>2</mn><mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo>−</mo><msup> <mi>R</mi> <mn>2</mn> </msup> <mo>;</mo><mtext> </mtext><mi>d</mi><mo stretchy="false">(</mo><mi>i</mi><mo>+</mo><mn>1</mn><mo stretchy="false">)</mo><mo>=</mo><mtext> </mtext><mi>d</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo><mo>+</mo><mo stretchy="false">(</mo><mn>2</mn><msub> <mi>x</mi> <mi>p</mi> </msub> <mo>+</mo><mn>3</mn><mo stretchy="false">)</mo><mo>;</mo><mtext> </mtext><mi>Δ</mi><mi>E</mi><mo>=</mo><mo stretchy="false">(</mo><mn>2</mn><msub> <mi>x</mi> <mi>p</mi> </msub> <mo>+</mo><mn>3</mn><mo stretchy="false">)</mo> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> .
Ha <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>d</mi><mo stretchy="false">(</mo><mi>i</mi><mo stretchy="false">)</mo><mo>></mo><mn>0</mn> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> , akkor az SE pontot választjuk, ekkor d(i+1) kiszámítása változik. Az <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <msub> <mi>M</mi> <mrow> <mi>S</mi><mi>E</mi> </mrow> </msub> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> középpontot vizsgáljuk. A növekmény hasonlóan adódik: <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>Δ</mi><mi>S</mi><mi>E</mi><mo>=</mo><mo stretchy="false">(</mo><mn>2</mn><msub> <mi>x</mi> <mi>p</mi> </msub> <mo>−</mo><mn>2</mn><msub> <mi>y</mi> <mi>p</mi> </msub> <mo>+</mo><mn>5</mn><mo stretchy="false">)</mo> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> .
A képletek megadják az algoritmust, hogyan lehet egy közbülső d(i)-hez kiszámítani az utána következő d(i+1)-et. Hiányzik a kezdőérték meghatározása. Az <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>F</mi><mo stretchy="false">(</mo><msub> <mi>x</mi> <mi>p</mi> </msub> <mo>+</mo><mn>1,</mn><msub> <mi>y</mi> <mi>p</mi> </msub> <mo>−</mo><mn>1</mn><mo>/</mo><mn>2</mn><mo stretchy="false">)</mo> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> függvénybe behelyettesítjük a kezdő körpont (0,R) koordinátáit az <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <msub> <mi>y</mi> <mi>p</mi> </msub> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> és <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <msub> <mi>x</mi> <mi>p</mi> </msub> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math> koordináták helyébe.
Ekkor a következő összefüggést kapjuk: <math xmlns="http://www.w3.org/1998/Math/MathML"> <semantics> <mrow> <mi>d</mi><mo stretchy="false">(</mo><mn>1</mn><mo stretchy="false">)</mo><mo>=</mo><mi>F</mi><mo stretchy="false">(</mo><mn>1,</mn><mi>R</mi><mo>−</mo><mn>1</mn><mo>/</mo><mn>2</mn><mo stretchy="false">)</mo><mo>=</mo><mn>1</mn><mo>+</mo><msup> <mrow> <mo stretchy="false">(</mo><mi>R</mi><mo>−</mo><mn>1</mn><mo>/</mo><mn>2</mn><mo stretchy="false">)</mo> </mrow> <mn>2</mn> </msup> <mo>−</mo><msup> <mi>R</mi> <mn>2</mn> </msup> <mo>=</mo><mn>5</mn><mo>/</mo><mn>4</mn><mo>−</mo><mi>R</mi> </mrow> <annotation encoding="MathType-MTEF"> </annotation> </semantics></math>.
Ezek után már könnyedén megadhatjuk a körrajzoló eljárást.
Áttérés egész aritmetikára
Az algoritmus hátránya, hogy a d változó valós típusú. Egy egyszerű program transzformációval megszüntetjük a d változó inicializálásánál fellépő osztást. Bevezetünk egy új döntési változót: h=d-1/4 és ezzel d-t h+1/4-re cseréljük. Ekkor az inicializálás h=1-R lesz, és a ciklusmagban a feltétel h<-1/4-re változik. Mivel h egész értékről indul és egész értékkel növekszik, ezért ezt a feltételt megváltoztathatjuk h<0-ra. Ezek után előállíthatjuk az egész értékekkel dolgozó algoritmust:
21. századi közoktatás - fejlesztés, koordináció (TÁMOP-3.1.1-08/1-2008-0002)
