How Do You Draw a Circle?
Created:
Interview
A long time ago I interviewed a lot of candidates for a lot of graphics programming positions. Being a good interviewer is hard work; my early attempts were not great. Over time I came up with this question to get a conversation started.
Me: What do you do if a co-worker comes to you and says "I need to draw a circle?"
- Candidate 0: I don't know.
- Candidate 1: I don't know. A compass?
- Candidate 2: Hmmmm. I'd print a small letter "o".
- Candidate 3: Square root should do it.
- Candidate 4: Sines and Cosines should do it.
- Candidate 5: Bresenham's circle drawing algorithm should do it.
- Candidate 6: I'd tell them to look for a library function, show them where the documentation lives. Better to re-use than invent.
- Candidate 7: I'd say "I don't know. Why do you want to draw a circle?" because maybe they don't really need to draw one. Maybe they need to know what is inside the circle using square root. Maybe they need an ellipse. Once we decide a drawn circle is really needed, where is it being drawn? Will it be filled, solid or with a pattern? Chances are, there is already a function to do this, and well debugged by now. You probably don't need to write it yourself, but if you do, use sines and cosines, and make the step size a function of the radius. How fast does it need to be? Depending on the device, Bresenham might be appropriate. On a printer, a small letter "o" might work for a marker and be good enough.
Discussion
Candidates 0,1,2,3,4,5 all missed the forest. If you are the interviewer, be sure to help them see the other person in the question, because that's half of the question. And if you are the candidate, watch out for two part questions.
If you are the interviewee, never stop where candidate 0 did. Candidates 1 and 2 provide just enough of a hook for the interviewer to ask another question. If you are the interviewer, remember the candidate is in a stressful situation and needs a bit of help unlocking more details.
Candidates 3, 4, and 5 each suggest a technical solution, any of which might work, none of which are always best. If you are the candidate, keep talking about your answer. If you are the interviewer, coach them: "will that be (fast, safe, correct, etc)?"
Candidates 6 and 7 fall at different places on the pragmatic scale. More questions and discussion are needed to determine a best fit.
Answers
The interview question isn't really very much about drawing a circle, but if that's why you are still reading, here's JSL for answers 2,3,4,5,6.
Small letter o, three ways
New Window( "Candidate 2, literal",
Graph Box(
xaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
yaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
Text( Center Justified, {50, 50}, "o" ) // "o" sits above the point
)
);
New Window( "Candidate 2, modified",
Graph Box(
xaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
yaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
markersize(10),
marker( markerstate("O"), {50, 50}) // capital "O" is somewhat centered
)
);
New Window( "Candidate 2, reinvented",
Graph Box(
xaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
yaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
Marker Size( 100 ),
Marker( Marker State( 8 ), {50, 50} ) // bigger is thicker
)
);
Square root, two ways
New Window( "Candidate 3, sqrt hard way",
Graph Box(
framesize( 300, 300 ),
xaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
yaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
// draw a circle at 50,50 with radius 30 using sqrt
// a lot of code, and not too pretty on the left and right
step=3; // to make the problem more obvious, use 1 to almost hide it
For( x = 0, x < 30, x += step,
// hyp = sqrt(x^2 + y^2)
// hyp^2 = x^2 + y^2
// hyp^2 - x^2 = y^2
y1 = Sqrt( 30 ^ 2 - x ^ 2 );
y2 = Sqrt( 30 ^ 2 - (x + step) ^ 2 );
// do all four quadrants in parallel
Line( {50 + x, 50 + y1}, {50 + (x + step), 50 + y2} );
Line( {50 - x, 50 + y1}, {50 - (x + step), 50 + y2} );
Line( {50 - x, 50 - y1}, {50 - (x + step), 50 - y2} );
Line( {50 + x, 50 - y1}, {50 + (x + step), 50 - y2} );
)
)
);
New Window( "Candidate 3, sqrt with YFunction",
Graph Box(
framesize( 300, 300 ),
xaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
yaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
// draw a circle at 50,50 with radius 30 using sqrt
// sqrt has two answers. Looks nice, thanks YFunction. Only a small gap.
Y Function( 50 + Sqrt( 30 ^ 2 - (x - 50) ^ 2 ), x );// top
Y Function( 50 - Sqrt( 30 ^ 2 - (x - 50) ^ 2 ), x );// bottom
)
);
Sines and Cosines
New Window( "Candidate 4, sin/cos with XYFunction",
Graph Box(
framesize( 300, 300 ),
xaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
yaxis( Add Ref Line( 50, "Solid", "Black", "", 1 ) ),
// draw a circle at 50,50 with radius 30 using sin/cos
XY Function( 50 + 30 * Cos( t ), 50 + 30 * Sin( t ), t, Min( 0 ), Max( 2 * Pi() ) )
)
);
Bresenham
//Bresenham.
// using pixel functions (There is no reason I can think of to
// use this code; everything else will be faster! A long time
// ago there was no floating point arithmetic or sin/cos/sqrt
// and tricks like this were useful.)
drawCircle = Function( {xc, yc, x, y}, // not really pixels. this is not a good match for JMP!
Marker( Marker State( 0 ), {xc + x, yc + y} ); // invented for primitive hardware without
Marker( Marker State( 0 ), {xc - x, yc + y} ); // floating point.
Marker( Marker State( 0 ), {xc + x, yc - y} );
Marker( Marker State( 0 ), {xc - x, yc - y} );
Marker( Marker State( 0 ), {xc + y, yc + x} );
Marker( Marker State( 0 ), {xc - y, yc + x} );
Marker( Marker State( 0 ), {xc + y, yc - x} );
Marker( Marker State( 0 ), {xc - y, yc - x} );
);
circleBres = Function( {xc, yc, r}, // https://www.geeksforgeeks.org/bresenhams-circle-drawing-algorithm/
x = 0;
y = r;
d = 3 - 2 * r;
drawCircle( xc, yc, x, y );
While( y >= x,
x++;
If( d > 0,
y--;
d = d + 4 * (x - y) + 10;
,
d = d + 4 * x + 6
);
drawCircle( xc, yc, x, y );
);
);
New Window( "Candidate 5, really hard way using pixels",
Graph Box(
framesize( 900, 900 ),xscale(0,1000),yscale(0,1000),
xaxis( Add Ref Line( 500, "Solid", "Black", "", 1 ) ),
yaxis( Add Ref Line( 500, "Solid", "Black", "", 1 ) ),
// draw a circle at 500,500 with radius 300
circleBres( 500, 500, 300 ),
text({300,700},"Zoom in for detail")
)
);
Library Functions
New Window( "Candidate 6, Circle Function",
Graph Box(
xaxis( Show Major Grid( 1 ) ),
yaxis( Show Major Grid( 1 ) ),
Circle( {50, 50}, 30 )
)
);
New Window( "Candidate 6, Circle on square paper",
Graph Box( framesize(400,400),
xaxis( Show Major Grid( 1 ) ),
yaxis( Show Major Grid( 1 ) ),
Circle( {50, 50}, 30 )
)
);
You might prefer the oval function:
New Window( "Candidate 6, Oval function",
Graph Box( // framesize(600,400),
x=50;
y=50;
r=30;
Oval( x-r, y-r, x+r, y+r );
)
);
Hydraulics
I spent January and February helping a five year old assemble this Mega Cyborg Hand. I'd recommend seven as a reasonable minimum age (as does the box); we did 10 to 15 minute sessions every other day or so. It is an amazing value for about $30. Best part: walking home the other day, the 5yo spots an excavator and tells me about the hydraulic cylinders.
You must be a registered user to add a comment. If you've already registered, sign in. Otherwise, register and sign in.