# Board index » delphi » the fastest algorithm for drawing a circle?

## the fastest algorithm for drawing a circle?

I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
unsatisfied with the performance. I believe that there must be some
algorithm far better than mine, can you tell me?

## Re:the fastest algorithm for drawing a circle?

Search the net for Bresenham's algorithm for circles and you will find what
you need.
--
Finn Tolderlund

"Alphone" <Silf...@sohu.com> skrev i en meddelelse news:3c9e9e1d_1@dnews...

##### Quote
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

## Re:the fastest algorithm for drawing a circle?

##### Quote
"Alphone" <Silf...@sohu.com> wrote in message news:3c9e9e1d_1@dnews...
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm
very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

or you can pre-compute a table of sin/cos values for, say, 12 points round
the circle and use the table values.

## Re:the fastest algorithm for drawing a circle?

use lookup tables (arrays) to store sin and cos

Michael.

##### Quote
"Alphone" <Silf...@sohu.com> wrote in message news:3c9e9e1d_1@dnews...
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

## Re:the fastest algorithm for drawing a circle?

You can use a table with sin and cos entries. Usually, you won't see the
difference between a true circle and - say - one with about 80 line
segments.

This translates to a table of ONLY 20 value pairs, because, smart hehe, you
only have to hold values for 1 quadrant. The second, third and 4th quadrant
values just require negations on the correct spot.

You can precalculate this sin/cos table and re-use it anywhere where you
need them (circles, ellipses).

If you want to draw a true circle then you can also use the sqr(x) + sqr(y)
= constant property to get there faster. I believe this is the basis for the
aforementioned Bresenham algorithm.

This also works ideally for painting circular areas. Just imagine a square
box (or bitmap) where you go through all the scanlines, top down. For each
pixel you do

if sqr(Xpos - Xmid) + sqr(Ypos - Ymid) < sqr(Radius) then
Pixel[XPos, YPos] := Black
else
Pixel[XPos, YPos] := White

You can optimise this by using scanlines, and precalculating sqr(Radius),
and sqr(YPos- YMid) for each scanline.

Using an estimation method to find the left and right x per scanline would
be not too hard. And using the same quadrant copying scheme is not hard too.

You can even make it neater by defining a band (Radius1 & Radius2) of a
pixel wide (or the width you want). Then, define for each pixel corner the
value and doing some math to calculate the pixel's coloring. This would
actually be a anti-aliased circle draw, and probably still miles faster than

Regards,

Nils
www.abc-view.com

##### Quote
Alphone <Silf...@sohu.com> wrote in message news:3c9e9e1d_1@dnews...
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

## Re:the fastest algorithm for drawing a circle?

Hi

Make a lookup table for results of sin and cos functions. Then, instead
calculating the value, look for result in the table.

Tomaz

##### Quote
"Alphone" <Silf...@sohu.com> wrote in message news:3c9e9e1d_1@dnews...
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

## Re:the fastest algorithm for drawing a circle?

Have you tried the Borland work ?

Put a button on a form and put this code:

Var i : Integer;
begin
for i := 1 to 500 do
form1.Canvas.Ellipse(0,0,i,i);
end;

"Alphone" <Silf...@sohu.com> escreveu na mensagem news:3c9e9e1d_1@dnews...

##### Quote
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

## Re:the fastest algorithm for drawing a circle?

##### Quote
> I previously use lots of sin(..) & cos(..)

There was a paper of Prof N. Wirth ETH Zrich
"Drawing Lines, Circles ands Ellipses in a Raster"
using only (32 bit) integer arithmetic (Bresenham)

I have this as PDF: 5 pages, 300 kB.

There is cited
Foley, Van Dam;  Fundamentals of of interactive Computer Graphics; 1982

Cossit; Line drawing with the NS32CG16 and drwaing circles with NS32CG16.
AN-522 and AN-523 National Semiconductors Corp 1988

## Re:the fastest algorithm for drawing a circle?

see
http://www.national.com/apnotes/apnotes_all_1.html
AN-522
##### Quote
Alphone wrote:

> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

## Re:the fastest algorithm for drawing a circle?

##### Quote
Alphone wrote:
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

Note that you only need to calculate the coords for 1/8 of a circle,
the other points can be mirrored...

--
Andreas

## Re:the fastest algorithm for drawing a circle?

##### Quote
> There was a paper of Prof N. Wirth ETH Zrich
> "Drawing Lines, Circles ands Ellipses in a Raster"
> using only (32 bit) integer arithmetic (Bresenham)

I tried to translate the algorithms

UNIT BresPix;
INTERFACE                                                {+unit BresPix}
TYPE
std_Str=STRING;
std_Int=LongInt;
PROCEDURE BresPix_Test;
{====================================================}
IMPLEMENTATION                                           {+unit BresPix}
USES  Crt  ;
TYPE
xyPix_Rec=RECORD
xPix,yPix:{Vw0Typ .}std_Int;
END;

PROCEDURE PixelPut(x:xyPix_Rec; c:Char);
BEGIN                                            {+procedure PixelPut}
Crt .GotoXY(x.xPix+1,x.yPix+1);    Write(c);
END;                                             {+procedure PixelPut}

PROCEDURE LineSimple(a,b:{Vw0Typ .}std_Int);
VAR
x:xyPix_Rec;
BEGIN                                          {+procedure LineSimple}
x.xPix:=0;
WHILE (x.xPix<a) DO BEGIN                                    {+ _1_}
x.yPix:=b*x.xPix DIV a;
PixelPut(x,'1');
Inc(x.xPix); END;
END;                                           {+procedure LineSimple}

PROCEDURE LineBres(a,b:{Vw0Typ .}std_Int);
VAR
x:xyPix_Rec;
i:RECORD
hlp:{Vw0Typ .}std_Int;
b_a:{Vw0Typ .}std_Int;
END;
BEGIN                                            {+procedure LineBres}
x.xPix:=0;    x.yPix:=0;
i.hlp:=b-(a DIV 2)-(b div 2){ correct for 1 pixel };
i.b_a:=b-a;
WHILE (x.xPix<a) DO BEGIN                                    {+ _2_}
PixelPut(x,'2');
IF (i.hlp<=0) THEN BEGIN
i.hlp:=i.hlp+b;
END ELSE BEGIN
i.hlp:=i.hlp+(i.b_a);        x.yPix:=x.yPix+1;
END;
Inc(x.xPix); END;
END;                                             {+procedure LineBres}

VAR
x:xyPix_Rec;
i:RECORD
hlp:{Vw0Typ .}std_Int;
END;
BEGIN                                          {+procedure CircleBres}
x.xPix:=r;    x.yPix:=0;
i.hlp:=1-r;
WHILE (x.yPix<x.xPix) DO BEGIN                               {+ _3_}
PixelPut(x,'c');
IF (i.hlp<0) THEN BEGIN
i.hlp:=i.hlp+2*x.yPix+3;
END ELSE BEGIN
i.hlp:=i.hlp+2*(x.yPix-x.xPix)+5;        x.xPix:=x.xPix-1;
END;
Inc(x.yPix); END;
END;                                           {+procedure CircleBres}

VAR
x:xyPix_Rec;
i:RECORD
d,g,h:{Vw0Typ .}std_Int;
END;
y:RECORD
y1:{Vw0Typ .}std_Int;
a2,b2:{Vw0Typ .}std_Int;
END;
BEGIN                                         {+procedure EllipseBres}
y.a2:=a*a;    y.b2:=b*b;
BEGIN
x.xPix:=0;      x.yPix:=b;
i.h:=(y.a2 DIV 4)-b*y.a2+y.b2;
i.g:=Round((9/4)*y.a2)-3*b*y.a2+y.b2;
WHILE (i.g<0) DO BEGIN                                     {+ _4_}
PixelPut(x,'E');
IF (i.h<0) THEN BEGIN
i.d:=(2*x.xPix+3)*y.b2;
i.g:=i.g+i.d;
END ELSE BEGIN
i.d:=(2*x.xPix+3)*y.b2-2*(x.yPix-1)*y.a2;
i.g:=i.g+i.d+2*y.a2;
x.yPix:=x.yPix-1;
END;
i.h:=i.h+i.d;
Inc(x.xPix); END;
END;
BEGIN
x.xPix:=a;      y.y1:=x.yPix;       x.yPix:=0;
i.h:=(y.b2 DIV 4)-a*y.b2+2*y.a2;
WHILE (x.yPix<=y.y1) DO BEGIN                              {+ _5_}
PixelPut(x,'e');
IF (i.h<0) THEN BEGIN
i.h:=i.h+(2*x.yPix+3)*y.a2;
END ELSE BEGIN
i.h:=i.h+(2*x.yPix+3)*y.a2-2*(x.xPix-1)*y.b2;
x.xPix:=x.xPix-1;
END;
Inc(x.yPix); END;
END;
END;                                          {+procedure EllipseBres}
{= = = = = = = = = = = = = = = = = = = = = = = = = = }
PROCEDURE BresPix_Test;
BEGIN                                        {+procedure BresPix_Test}
Crt .ClrScr;
LineSimple(60,20);
LineBres(60,20);
END;                                         {+procedure BresPix_Test}

BEGIN                                                    {+unit BresPix}
{\$DEFINE Test_BresPix}
{\$IFDEF Test_BresPix }BresPix_Test{\$ENDIF };
END {\$IFDEF VwDel6 }{\$WARNINGS OFF}{\$ENDIF}.             {+unit BresPix}

## Re:the fastest algorithm for drawing a circle?

There is another way to do it using rotations.
Imagine the circle with center (X0, Y0) and radius R
Set the initial point (R, 0) => (X0+R, Y0)

var
X, Y : Double;
I : Integer;

X:=R;
Y:=0;

Set the number of points to 2.Pi.R

for I:=0 to Round(2*Pi*R) do
begin
Plot(X0+X, Y0+Y);
{ Rotate point (X,Y) }
X:=X-Y/R;
Y:=Y+X/R;
end;

The angle between each point is (2.Pi)/(2.Pi.R) = 1/R

Cos(X) for small X is near 1 and Sin(X) for small X is near X and that is
the magic.
I know the X in the second expression (Y=...) is new and this is an error
but it works.

[]s
Arthur

Alphone <Silf...@sohu.com> escreveu nas notcias de mensagem:3c9e9e1d_1@dnews...

##### Quote
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?