After I received several proposals for the algorithm of ellipse, I made a comparative test:
Code: Select all
#Include Once "cairo\cairo.bi"
Dim SHARED AS cairo_t PTR cr
CONST Pi = 3.141592653589793
Const Pi_div_2 = Pi / 2
Sub ellipse_H(byval x as single, byval y as single, byval a as single, _
byval b as single, byval angle as single, byval col as uinteger) ' H4tt3n
'' Very fast ellipse drawing function by Michael "h4tt3n" Nissen
'' version 1.0, june 2009
''
'' Spends less than one eigths as many trig calls as the brute-force method.
''
'' This algorithm requires number-of-vertices / 4 trig calls, whereas the
'' normal brute-force method requires 2 + number-of-vertices * 2 trig calls.
'' these constants decide the graphic quality of the ellipse
' const as single pi = 4*atn(1) '' pi
const as single twopi = 2*pi '' two pi (radians in a circle)
const as integer face_length = 8 '' approx. face length in pixels
const as integer max_faces = 4096 '' maximum number of faces in ellipse
const as integer min_faces = 32 '' minimum number of faces in ellipse
'' approx. ellipse circumference (Hudson's method)
dim as single h = (a-b*a-b)/(a+b*a+b)
dim as single circumference = 0.25*pi*(a+b)*(3*(1+h/4)+1/(1-h/4))
'' number of faces in ellipse
dim as integer num_faces = circumference\face_length
'' clamp number of faces
if num_faces > max_faces then num_faces = max_faces
if num_faces < min_faces then num_faces = min_faces
'' keep number of faces divisible by 4
num_faces -= num_faces mod 4
'' get sine and cosine to ellipse angle
dim as single sinangle = sin(angle)
dim as single cosangle = cos(angle)
'' theta (the angle from the ellipse center)
dim as single theta = 0
'' deltatheta (angular step per iteration)
dim as single deltatheta = twopi/num_faces
'' number of iterations
'' (optimised to just 1/4 of the ellipse circumference)
dim as integer num_iterations = num_faces\4
'' dim array for holding cosine theta
dim as single costheta(1 to num_iterations-1)
'' precalc cosine theta
for i as integer = 1 to num_iterations-1
theta += deltatheta
costheta(i) = cos(theta)
next
'' dim arrays to hold cartesian (x, y) coordinates
dim as single _X(num_faces-1), _Y(num_faces-1)
'' iterate
for i as integer = 1 to num_iterations-1
'' predefine handy index numbers
dim as integer j = 2*num_iterations - i
dim as integer k = 2*num_iterations + i
dim as integer l = 4*num_iterations - i
'' precalc a few values
dim as single a_costheta_cosangle = a*costheta(i)*cosangle
dim as single a_costheta_sinangle = a*costheta(i)*sinangle
'' Check this: we get sine theta from already precalced cosine theta!
'' since sin(angle) = cos(0.5*pi - angle). This halves the number of trig calls!
dim as single b_sintheta_sinangle = b*costheta(num_iterations - i)*sinangle
dim as single b_sintheta_cosangle = b*costheta(num_iterations - i)*cosangle
'' convert angles to cartesian (x, y) coordinates
'' Here we reuse the same cos and sin theta values four times.
'' This reduces the already halved number of trig calls to one fourth - or one eighths all in all!
_X(i) = x+a_costheta_cosangle-b_sintheta_sinangle: _Y(i) = y+a_costheta_sinangle+b_sintheta_cosangle
_X(j) = x-a_costheta_cosangle-b_sintheta_sinangle: _Y(j) = y-a_costheta_sinangle+b_sintheta_cosangle
_X(k) = x-a_costheta_cosangle+b_sintheta_sinangle: _Y(k) = y-a_costheta_sinangle-b_sintheta_cosangle
_X(l) = x+a_costheta_cosangle+b_sintheta_sinangle: _Y(l) = y+a_costheta_sinangle-b_sintheta_cosangle
next
'' get coordinates of the four "right angles"
'' (we don't need to call cos / sin theta since it'll always be 0 or 1)
'' This reduces the number of trig calls by two. Not much but it's there.
_X(0*num_iterations) = x+a*cosangle: _Y(0*num_iterations) = y+a*sinangle '' 0.0*pi
_X(1*num_iterations) = x-b*sinangle: _Y(1*num_iterations) = y+b*cosangle '' 0.5*pi
_X(2*num_iterations) = x-a*cosangle: _Y(2*num_iterations) = y-a*sinangle '' 1.0*pi
_X(3*num_iterations) = x+b*sinangle: _Y(3*num_iterations) = y-b*cosangle '' 1.5*pi
'' draw ellipse
for i as integer = 0 to num_faces-1
dim as single j = (i+1) mod num_faces
line (_X(i), _Y(i))-(_X(j), _Y(j)), col '' draw ellipse as closed line loop
'draw string (_X(i), _Y(i)), str(i) '' draw ellipse point numbers
'pset (_X(i), _Y(i)), col '' draw ellipse as set of points
next
end Sub
Sub polygon(n As Integer,cx As Single,cy As Single,col As Uinteger,size As Single,th As Single=1,angle As Single=0,ecc As Single=1,im As Any Pointer=0) ' Dodicat
angle=angle*pi/180
Var slug =2*pi/n ' Red poligona
'Var slug
var count =0
For z As Single=0 To 2*pi Step slug
count=count+1
If count>n Then Exit For
For k As Single =0 To th-1 Step 1/th
var x1r=(Cos(angle)*(ecc*(size-k)*Cos(z))-Sin(angle)*(size-k)*Sin(z))+cx
var y1r=(Sin(angle)*(ecc*(size-k)*Cos(z))+Cos(angle)*(size-k)*Sin(z))+cy
var x2r=(Cos(angle)*(ecc*(size-k)*Cos(z+slug))-Sin(angle)*(size-k)*Sin(z+slug))+cx
var y2r=(Sin(angle)*(ecc*(size-k)*Cos(z+slug))+Cos(angle)*(size-k)*Sin(z+slug))+cy
Line im,(x1r,y1r)-(x2r,y2r),col
Next k
Next z
End Sub
Sub Elipsa_F (A As Integer, B As Integer, X0 As Integer, Y0 As Integer, Kut As Double, Boja As Integer) ' Frisian
Dim As Integer Xp, Yp, i
Dim As Double X, Y, R, Fi, Fi0, K1, K2
K1 = B*B : K2 = K1/(A*A)
X = B * Cos(Kut+Pi_div_2) ' if i = 0 then R = B and Y = B, Atn(Y/0) = Pi/2
Y = B * Sin(Kut+Pi_div_2)
PSet(X0+X,Y0+Y),boja
PSet(X0-X,Y0-Y),boja
For i = 1 To A
Y = Sqr (K1 - K2*i*i) : R = Sqr(i*i+Y*Y) : Fi0 = Atn (Y/i)
Fi = Fi0 + Kut : X = R*Cos (Fi) : Y = R*Sin (Fi)
PSet (X0+X, Y0+Y), Boja
PSet (X0-X, Y0-Y), Boja 'Sin(Fi0+Kut+Pi) = - Sin(Fi0+Kut) and Cos(Fi0+Kut+Pi) = - Cos(Fi0+Kut)
Fi = -Fi0 + Kut : X = R*Cos (Fi) : Y = R*Sin (Fi)
PSet (X0+X, Y0+Y), Boja
PSet (X0-X, Y0-Y), Boja
Next i
K1 = A*A : K2 = K1/(B*B)
X = A * Cos(Kut)' if i = 0 then R = A and Y = A, Atn(X/0) = 0
Y = A * Sin(Kut)
PSet(X0+X,Y0+Y),boja
PSet(X0-X,Y0-Y),boja
For i = 1 To B
X = Sqr (K1 - K2*i*i) : R = Sqr(x*x+i*i) : Fi0 = Atn (X/i)
Fi = Fi0-Kut : Y = R*Cos (Fi) : X = R*Sin (Fi)
PSet (X0+X, Y0+Y), Boja
PSet (X0-X, Y0-Y), Boja
Fi = -Fi0 - Kut : Y = R*Cos (Fi) : X = R*Sin (Fi)
PSet (X0+X, Y0+Y), Boja
PSet (X0-X, Y0-Y), Boja
Next i
End Sub
Sub Elipsa_T (A AS DOUBLE, B AS DOUBLE, X0 AS DOUBLE, Y0 AS DOUBLE, Kut AS Double)' TJF
cairo_new_path (cr)
cairo_save (cr)
cairo_translate (cr, X0, Y0)
cairo_rotate(cr, Kut)
cairo_scale (cr, A, B)
cairo_arc (cr, 0.0, 0.0, 1.0, 0.0, 2.0 * Pi)
cairo_restore (cr)
cairo_stroke(cr)
END Sub
Sub Elipsa_I (A As Integer, B As Integer, X0 As Integer, Y0 As Integer, Kut As Double, Boja As Integer)' Ivan
dim As integer Xp, Yp, i ' Xp i Yp -> Prave koordinate na koje ce se ucrtati tocka
dim As Double X, Y, R, Fi, Fi0, K1, K2 ' Pomocne varijable za izracun koordinata
' Crtanje elipse tako što X pomicemo jednu po jednu tocku a zatim racunamo Y
K1 = B*B : K2 = K1/(A*A) ' Konstante
For i = 0 to A ' A -> Horizontalni radijus elipse (prije zakretanja za kut)
x = i ' X koordinata (vrijednost mjenja od 0 do A)
y = sqr (K1 - K2*X*X) ' Y koordinata (racuna se)
R = sqr(X*X+Y*Y) ' Udaljenost tocke od centra elipse
fi0 = Atn (Y/X) ' Kut pod kojim se nalazi tocka u odnosu na centra elipse
' dok još nije uzet u obzir kut elipse
' Ako bi elipsa bila pod kutem 0 ovaj dio koda bi nacrtao cetvrtinu elipse dole desno
fi = fi0 + Kut ' Ukupni kut tocke u odnosu na centar se dobije dodavanjem
' zadanog kuta elipse kutu tocke na horizontalnoj elipsi
X = R*Cos (fi)' X -> Horizontalna udaljenost tocke od centra elipse
Y = R*sin (fi)' Y -> Vertikalna udaljenost tocke od centra elipse
Xp = X + X0 ' Xp, Yp -> tocka koju treba iscrtati, X0, Y0 -> Centar elipse
Yp = Y + Y0 ' X, Y -> horizontalna i vertikalna udaljenost tocke od centra elipse
pset (Xp, Yp), Boja ' Crta tocku zadane boje na izracunatoj koordinati
' Isto se ponavlja za ostala tri dijela elipse
fi = -fi0 + Kut + Pi : X = R*Cos (fi) : Y = R*sin (fi) ' Dole lijevo
Xp = X + X0 : Yp = Y + Y0 : pset (Xp, Yp), Boja
Fi = fi0 + Kut + Pi : X = R*Cos (fi) : Y = R*sin (fi) ' Gore lijevo
Xp = X + X0 : Yp = Y + Y0 : pset (Xp, Yp), Boja
fi = -fi0 + Kut : X = R*Cos (fi) : Y = R*sin (fi) ' Gore desno
Xp = X + X0 : Yp = Y + Y0 : pset (Xp, Yp), Boja
Next i
' Ponovno crtanje elipse tako što Y pomicemo jednu po jednu tocku a zatim racunamo X
K1 = A*A : K2 = K1/(B*B)
For i = 0 to B
y = i : x = sqr (K1 - K2*Y*Y) : R = sqr(x*x+y*y) : fi0 = Atn (X/Y)
fi = fi0 - Kut : Y = R*Cos (fi) : X = R*sin (fi) ' Dole desno (kut 0)
Xp = X + X0 : Yp = Y + Y0 : pset (Xp, Yp), Boja
fi = -fi0 - Kut : Y = R*Cos (fi) : X = R*sin (fi) ' Dole lijevo (kut 0)
Xp = X + X0 : Yp = Y + Y0 : pset (Xp, Yp), Boja
fi = fi0 - Kut + Pi : Y = R*Cos (fi) : X = R*sin (fi) ' Gore lijevo (kut 0)
Xp = X + X0 : Yp = Y + Y0 : pset (Xp, Yp), Boja
fi = -fi0 - Kut + Pi : Y = R*Cos (fi) : X = R*sin (fi) ' Gore desno (kut 0)
Xp = X + X0 : Yp = Y + Y0 : pset (Xp, Yp), Boja
Next i
End Sub
' +++++++++++++++++++ MAIN PROGRAM ++++++++++++++++++++++++
Dim As Integer i, j, X, Y, A, B
Dim As Single ecc
Dim as Double Ts, Tf
'Dim As Double A
ScreenInfo X, Y
X -= 32 : Y -= 64
ScreenRes X, Y, 32, 3, 0 ' Initializes a graphics mode by specifying horizontal and vertical resolution
Width X\8, Y\16
Screenset 1, 0
VAR cs = cairo_image_surface_create_for_data( SCREENPTR, CAIRO_FORMAT_ARGB32, X, Y, X * LEN(INTEGER))
cr = cairo_create(cs)
cairo_set_source_rgb(cr, 1.0, 1.0, 1.0)
cairo_set_line_width(cr, 1.0)
B = Y \ 4 - 10
A = B \ 4
ecc = B \ 2
Screenset 2,0
Draw String ( X\4-16, Y\4-8),"Ivan" ,&HFFFF00
Draw String (3*X\4-12, Y\4-8),"TJF" ,&HFFFF00
Draw String ( X\4-28,3*Y\4-8),"Frisian",&HFFFF00
Draw String (3*X\4-28,3*Y\4-8),"Dodicat",&HFFFF00
Draw String (X\2-28,Y\2-8),"H4TT3N",&HFFFF00
ScreenCopy 2, 1
Screenset 1,0
For i = 0 To 2
Elipsa_I (A, B, X\4, Y\4, i * Pi/3, &HFFFFFF)
Elipsa_T (A, B, 3*X\4, Y\4, i * Pi/3)
Elipsa_F (A, B, X\4,3*Y\4, i * Pi/3, &HFFFFFF)
polygon ( 45, 3*X\4, 3*Y\4, RGB(&HFF,&HFF,&HFF), B, 1, i*60, A/B)
ellipse_H(X\2, Y\2, A, B,i * Pi/3, &HFFFFFF)
Next
Draw String (X\2-100,Y-18),"Press any key to continue",&HFFFF00
ScreenCopy 1, 0
Sleep
For j = 0 To 30
Screenset 1,0
ScreenCopy 2, 1
For i = 0 To 2
Elipsa_I (A, B, X\4, Y\4, i * Pi/3 + j * Pi /180, &HFFFFFF)
Elipsa_T (A, B, 3*X\4, Y\4, i * Pi/3 + j * Pi /180)
Elipsa_F (A, B, X\4,3*Y\4, i * Pi/3 + j * Pi /180, &HFFFFFF)
polygon ( 45, 3*X\4,3*Y\4, RGB(&HFF,&HFF,&HFF), B, 1, i*60+j, A/B)
ellipse_H(X\2, Y\2, A, B,i * Pi/3 + j * Pi /180, &HFFFFFF)
Next i
ScreenCopy 1, 0
Sleep 25
Next j
Sleep
'End ' Obrisati
cairo_destroy(cr)
cairo_surface_flush(cs)
cairo_surface_destroy(cs)
Screenset 0
i = 10000
Cls
cs = cairo_image_surface_create_for_data( SCREENPTR, CAIRO_FORMAT_ARGB32, X, Y, X * LEN(INTEGER))
cr = cairo_create(cs)
cairo_set_source_rgb(cr, 1.0, 1.0, 1.0)
cairo_set_line_width(cr, 1.0)
Draw String (X\2-20, Y\2-16),"Start" ,&HFFFF00
Ts = Timer
For j = 0 To i
Elipsa_I (A, B, X\4, Y\4, j * Pi /i, &HFFFFFF)
Elipsa_T (A, B, 3*X\4, Y\4, j * Pi /i)
Elipsa_F (A, B, X\4,3*Y\4, j * Pi /i, &HFFFFFF)
polygon ( 45, 3*X\4, 3*Y\4, RGB(&HFF,&HFF,&HFF), B, 1, 180*j/i, A/B)
ellipse_H(X\2 , Y\2,A, B,j * Pi /i, &HFFFFFF)
Next j
Tf = Timer
Draw String (X\2-24, Y\2+8),"Finish" ,&HFFFF00
Draw String ( X\2, Y\2),Str(Tf-Ts) ,&H808080
Sleep
Cls
Draw String ( X\4-40, Y\4-18),"Ivan start" ,&HFFFF00
Ts = Timer
For j = 0 To i
Elipsa_I (A, B, X\4, Y\4, j * Pi /i, &HFFFFFF)
Next j
Tf = Timer
Draw String ( X\4-40, Y\4+8),"Ivan finish" ,&HFFFF00
Draw String ( X\4, Y\4+26),Str(Tf-Ts) ,&H808080
Sleep
Draw String (3*X\4-36, Y\4-16),"TJF start" ,&HFFFF00
Ts = Timer
For j = 0 To i
Elipsa_T (A, B, 3*X\4, Y\4, j * Pi /i)
Next j
Tf = Timer
ScreenCopy 0, 1 ' Why I must
ScreenCopy 1, 0 ' to do this?
Draw String (3*X\4-40, Y\4+8),"TJF finish" ,&HFFFF00
Draw String (3*X\4, Y\4+26),Str(Tf-Ts) ,&H808080
Sleep
Draw String ( X\4-52,3*Y\4-16),"Frisian start",&HFFFF00
Ts = Timer
For j = 0 To i
Elipsa_F (A, B, X\4,3*Y\4, j * Pi /i, &HFFFFFF)
Next j
Tf = Timer
Draw String ( X\4-56,3*Y\4+8),"Frisian finish",&HFFFF00
Draw String ( X\4, 3*Y\4+26),Str(Tf-Ts) ,&H808080
Sleep
Draw String (3*X\4-52,3*Y\4-16),"Dodicat start",&HFFFF00
Ts = Timer
For j = 0 To i
polygon ( 45, 3*X\4, 3*Y\4, RGB(&HFF,&HFF,&HFF), B, 1, 180*j/i, A/B)
Next j
Tf = Timer
Draw String (3*X\4-56,3*Y\4+8),"Dodicat finish",&HFFFF00
Draw String (3*X\4, 3*Y\4+26),Str(Tf-Ts) ,&H808080
Sleep
Draw String (X\2-48,Y\2-16),"H3TT3N start",&HFFFF00
Ts = Timer
For j = 0 To i
ellipse_H (X\2,Y\2,A, B, j * Pi /i, &HFFFFFF)
Next j
Tf = Timer
Draw String ( X\2-48,Y\2+8),"H3TT3N finish",&HFFFF00
Draw String ( X\2, Y\2+26),Str(Tf-Ts) ,&H808080
Draw String (X\2-100,Y-18),"Press any key to finish",&HFFFF00
Sleep
The result is not exactly the same every time but it is around that.
H4tt3n is the fastest (but has the most lines of code).
Dodicat is a little slower with shortest code.
TJF is is slowest, and requires extra effort to work, but it gives the most beautiful print.