visitor (0 QPoints)
  • FR
  • EN
  • NL
  • DE
  • ES
315 experts, 1193 registered users, 1659 questions already answered
European Experts Exchange, the very best site for high-quality IT solutions

New Improved Search!

 


05/10/2011 1h30 : Steve Jobs is dead, the father of Apple ][ is gone, we are all orphaned.

Languages :: Pascal :: Arc algorithm
By: espectro U.S.A.  Date: 16/04/2003 00:00:00  English  Points: 75 Status: Answered
Quality : Excellent
Hello, this is my first time here.
I have been assigned a small project to develop some basic graphic primitives (mode 13h, in pascal)
The teacher told us to use the algorithm we made for the ellipse to draw the circle too , and i now
need some info on how to develop the arc algorithm.

I know that the circle algorithm is the entire circle arc, from 0 to 360 degrees, but since i am using the ellipse algorithm, i wonder if i can extend it in some way to receive the starting and ending angle (from 0 to 360)

This is my ellipse algorithm, taken from a paper called "fast bresenham alike ellipse" or something:
pintapixel is putpixel().

I am giving all my points for this one, which isn't much.
You can use the algorithm below or one from scratch.
It cannot use any method in any unit. Just putpixel and the crt one

Thanks for your help!

Procedure PintaElipse(cx,cy,rx,ry:longint;c:byte);
Var x,y,cambiox,cambioy,error,dosascuad,dosbscuad,finx,finy: longint;

Procedure Pinta4Puntos(x,y:longint;c:byte);
Begin
PintaPixel(cx+x,cy+y,c);
PintaPixel(cx-x,cy+y,c);
PintaPixel(cx-x,cy-y,c);
PintaPixel(cx+x,cy-y,c)
End;

Begin
dosascuad:=(rx shl 1)*rx;
dosbscuad:=(ry shl 1)*ry;
x:=rx; y:=0;
cambiox:=ry*ry*(1-(rx shl 1));
cambioy:=rx*rx;
error:=0;
finx:=dosbscuad*rx;
finy:=0;

while(finx>=finy) do
begin
pinta4puntos(x,y,c);
inc(y);
inc(finy,dosascuad);
inc(error,cambioy);
inc(cambioy,dosascuad);
if(((error shl 1)+cambiox) > 0) then
begin
dec(x);
dec(finx,dosbscuad);
inc(error,cambiox);
inc(cambiox,dosbscuad)
end
End;
x:=0;
y:=ry;
cambiox:=ry*ry;
cambioy:=rx*rx*(1-(ry shl 1));
error:=0;
finx:=0;
finy:=dosascuad*ry;
while (finx<=finy) do
begin
pinta4puntos(x,y,c);
inc(x);
inc(finx,dosbscuad);
inc(error,cambiox);
inc(cambiox,dosbscuad);
if(((error shl 1)+cambioy)>0) then
begin
dec(y);
dec(finy,dosascuad);
inc(error,cambioy);
inc(cambioy,dosascuad)
end
end
End;
By: VGR Date: 17/04/2003 22:32:00 English  Type : Comment
unless I'm totally lost, if you've an ellipse program, then drawing a circle is just matter of saying that half-axis are equal and focal points are the same (the center) ;-)
By: VGR Date: 17/04/2003 22:33:00 English  Type : Comment
so in your case it's just rx=ry=whatever
By: espectro Date: 17/04/2003 23:20:00 English  Type : Comment
I said i already have the ellipse algorithm, and that for the circle i simply reuse the ellipse code.

Read the topic of the question. It's "arc algorithm", not circle algorithm.

I want to know how to draw an arc, given a starting and ending angle, counterclockwise, from 0 to 360 degrees, and given a radius.

I hope now people will understand me. So yes, you are totally lost :)

Thanks for replying so fast and maybe now you can help me better.
By: VGR Date: 17/04/2003 23:31:00 English  Type : Comment
may-be

but I've problems understanding your variables' names,especially ascuad in "dos{a|b}ascuad"

I ghuess the solution will be just to modify the loop so tht it stops before finishing the Complete Arc (ie Circle or Ellipse :D )

is "finy" meaning "final y" ?
By: espectro Date: 18/04/2003 00:18:00 English  Type : Comment
Remember that your solution may or may not use this algorithm.

the whole ellipse algorithm, well documented, you can get it from <A HREF="http://homepage.smc.edu/kennedy_john/BELIPSE.PDF">http://homepage.smc.edu/kennedy_john/BELIPSE.PDF</a>

dosbscuad means 2*b^2 and dosascuad means 2*a^2

finx and finy mean stopping x and stopping y respectively.

Cambioy and Cambiox mean Xchange and Ychange respectively.

Notice how i use left shift in all those 2* operations to increase speed.

Thanks for your reply, hoping for an answer soon.
By: VGR Date: 18/04/2003 01:09:00 English  Type : Answer
I saw the SHL calls

I had understood "fin" and "cambio", it's not that difficult for an European :D

anyway, if you want an Arc algorithm from scratch, here's one :

-given you want to trace an Arc of radius=R and between angles Theta1 and Theta2 in radians :

PutPixel(R,0);
for i:=Theta1 to Theta2 by step of Z Do {
LineTo (R*cos(i),R*sin(i));
// here cope with modulo problems when changing quadrant
} // for
By: espectro Date: 18/04/2003 01:15:00 English  Type : Comment
Some questions
1)What is Z?
2) putpixel(R,0) ?
the method should receive the starting (x,y). Dont't worry, i think the change is pretty obvius.

I will try it tomorrow and if it works i will accept your answer.

I take it that lineto is a standard line algorithm in the graph unit, well i hope it works nice with my pintalinea() bresenham line algorithm :)

What about those modulo comments you display?
By: VGR Date: 18/04/2003 01:17:00 English  Type : Comment
1) Z must be a fraction of a radian, the step of iteration for drawing small segments because true circles don't exist on a computer screen made of squares (or hexagons ;-).
For instance Z=0.01 for a very precise drawing ; beware that this was just pseudocode, you can't step with a real being 0.01, you've tyo step to (step=1) or downto (step=-1), so this would become with a multiplication factor of 100 :
for i:=0 to 100 Do
Begin
angle=Theta1+i*(Theta2-Theta1)/100;
// compute and draw
End;

2) PutPixel(R,0) signature PutPixel(X,Y:Integer) is usually defined, if not by the language,n at least by the user. It can be implemented as :
Mem[basevideo:offset]:=value; // direct video memory access, DOS Turbo-Pascal
TCanvas.property Pixels[X, Y: Integer]: TColor; in Delphi 4
MoveTo in Turbo-Pascal 3.0+ (doesn't draw, but prepares for the next LineTo or Line/LineRel call)

3) MoveTo and LineTo are defined since Turbo-Pascal 3.0 I guess

4) for "modulo problems", I meant that you can't reliably use ***only*** R.cos(angle),R.sin(angle) while ranging angle from 0 to 360° or 2.Pi Radians. Why? Because sin(Pi+x)=sin(x) and cos(Pi/2+x)=cos(x) and because usually functions arccos, arcsin arttan etc return the first possible value modulo Pi or Pi/2 (depending) and always modulo 2.Pi
By: espectro Date: 18/04/2003 01:43:00 English  Type : Comment

1) I didnt understand too well how would the algorithm be with those Z changes (in pascal). Could you please ellaborate? Is 0 to 100 some random angles you provided? Or is it just the size of the step you are using?


2)I already had done the putpixel method, i just asked why are you calling putpixel with (R,0) since that would paint a pixel in the first row of the screen and in the column matching the radius.

As i understood the problem, the arc function should start drawing at (r,0) too, but those coordinates should be relative to the arc figure not the 320x200 screen itself.

Because If the arc is bigger than 1 degree then it would try to paint at the top of the screen?

Or are you painting from top to bottom? I thought it would have to paint from 0 up to 360 (counterclockwise)

3)I'm not worried about lineto, since i am using my own. Remember, i dont want to use any unit other than crt

4)You meant sin(Pi+x)=cos(x) and cos(Pi/2+x)=sin(x) right? How would you overcome this limitation?

Thanks for your time
By: VGR Date: 18/04/2003 01:53:00 English  Type : Comment
1) size of the step because you can't iterate by fractions
2) R,0 is relative to the center, sorry, so it's rather (xc+R,yc)
3) no, I just wrote what I wrote : just to be careful with angles and trigonometric functions, aspecially Arc-ones.

Example : angle=-3Pi/4, ArcTan(Tan(angle))=Pi/4
By: espectro Date: 18/04/2003 04:36:00 English  Type : Comment
Ok here is that i have so far, i am screwing up somewhere
Remember that i cant use the graph unit so i dont have moveto or line to.
Instead i developed my own pintalinea() which takes the first poing x,y and draws it to x2,y2
My putpixel takes x,y and the color c

program arco;
procedure arc(xc,yc,r,a,b,c: integer);
var i,x,y: integer;
angle: real;
begin
x:=xc+r;
y:=yc;
pintapixel(x,y,c); {putpixel x,y, c is the color}
for i:=0 to 100 do
begin
angle:=a+i*(b-a)/100;
pintalinea( x,y,round(r*cos(angulo)),round(r*sin(angulo)),c);
x:=round(r*cos(angulo)); {pintalinea takes x,y,x2,y2,c}
y:=round(r*sin(angulo));
end;
end;

I hope i can finish this by your next reply :-\ i am so sorry for bothering you
By: espectro Date: 18/04/2003 04:38:00 English  Type : Comment
btw i tried to emulate the lineto by setting x and y to the result of r*sin and r*cos (since i cant use getx and gety from the graph unit)
By: VGR Date: 18/04/2003 04:48:00 English  Type : Comment
good except that :

angle:=a+i*(b-a)/100;

should be

angulo:=a+i*(b-a)/100;

:D

and you forgot to add xc and yc in the pintalinea calls, no ?
You also had a and b integer whereas they are real (radians start/stop)

I suggest to have :
newx, newy, oldx, oldy and do
(not tested live)

procedure arc(xc,yc,r,c: integer; a,b : Real); { a,b : start/end angle ; r : radius ; xc, yc : center coord. ; c : colour }
var i,oldx,oldy,newx,newy : integer;
angulo : real; { in radians }
begin
oldx:=xc+round(r*cos(a));
oldy:=yc+round(r*sin(a));
pintapixel(oldx,oldy,c); {putpixel x,y, c is the color}
for i:=0 to 100 do
begin
angulo:=a+i*(b-a)/100;
newx:=xc+round(r*cos(angulo));
newy:=yc+round(r*sin(angulo));
pintalinea( oldx,oldy,newx,newy,c);
oldx:=newx;
oldy:=newy;
end; { for }
end; { procedure Arc }
By: espectro Date: 18/04/2003 12:17:00 English  Type : Comment
Actually, none of those issues that you mention were causing trouble. I was translating the algorithm for you

The good news is that i was able to make my own algorithm based on your for i:=Theta1 to Theta2 by step of Z Do {
LineTo (R*cos(i),R*sin(i));

I did it without any line calls , without any stepping and without that first putpixel, and i was even able to correct the aspect ratio, all without calling a single unit.

I am so happy :) You get all your points.

Good nite!
By: espectro Date: 18/04/2003 12:19:00 English  Type : Comment
Although it was not complete, it was enough for me to get some lighting into my brain and fix things. Thanks
By: VGR Date: 18/04/2003 15:04:00 English  Type : Comment
I did it without any line calls , without any stepping and without that first putpixel, and i was even able to correct the aspect ratio, all without calling a single unit.
>>Hum, I'm sooo surprised. To LineTo you need a PutPixel. To draw you need PutPixel() too, in Pascal you can't step with Z being a fraction (real<1), the aspect ratio was never taken into consideration here, and "althought incomplete" my algorithm draws the circle [(Cx,Cy),R] if supplied with a=0 and b=2.Pi

I am so happy :) You get all your points.
>> yes, but I get "grade B" :/
By: espectro Date: 19/04/2003 02:42:00 English  Type : Comment
I managed to reduce the algorithm to ONE LINE :)

for a:=a to b do
PutPixel(round((xc+r*cos((pi*a)/180))*Aspect),round(yc-r*sin((pi*a)/180)),color);

Hey, B is a good grade. An A in my book would have meant that your algorithm worked directly with cut and paste. I had to convert radians to degrees, and also had to add and substract xc and yc respectively. I also had to use putpixel instead of the line algorithm (i could have done that, but it would have costed much more)

No grade lost for the aspect ratio (i didn't ask for help on that)

Thanks for all your help
By: VGR Date: 19/04/2003 03:24:00 English  Type : Comment

IMHO, doing a "one-liner" isn't AT ALL a prowess...

And finally it's not my fault if trigonomzetric functions accept degrees in stead of radians or grades ;-)
I hope it wasn't too much work for you 8-)
By: espectro Date: 25/04/2003 01:43:00 English  Type : Comment
Ok, i had to modify my 2-liner algorithm into something a little bigger, but now it is way much better. Still using sin/cosine though :(. I hope someone that needs this will consider it useful.
xc,yc is the center point of the arc.
R is the radius
a,b are the angles alpha,beta of the arc
c is the color i want to paint with

Since i am using 320x200, i need to correct the aspect radio in x by multiplying by 1.2.

I am converting all degrees to radians.
According to the books, the step to iterate in arc generation should be 1/radius

Procedure Arc(xc,yc,r,a,b:word;c:byte);
var x,y,i,step: real;
Begin
i:=1/(r*Aspect);
step:=(a*pi)/180;
xc:=round(xc*Aspecto);
while step<(b*pi)/180 do
begin
x:=xc+r*cos((step))*Aspect;
y:=yc-r*sin((step));
drawpixel(round(x),round(y),c);
step:=step+i;
End;
End;

Do register to be able to answer

©2010 These pages are served without commercial sponsorship. (No popup ads, etc...). Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE.
Please DO link to this page! Post to Twitter Post to Plurk Post to Yahoo Buzz Post to Delicious Post to Digg Post to Facebook Post to MySpace Post to Ping.fm Post to Reddit Post to StumbleUpon

EContact
browser fav
page generated in 354.969020 milliseconds

Why Google AdSense ads ?
compteur
 Ranking-Hits PageRank for this page