Circles of text
a Bresenham circle in Scala (35)
The Bresenham - algorithm has 2 major points:
- works without sin/ cosin.
- you only calculate ¼*½ circle, the other points are found by mirroring.
How to do it:
2 1
DCBABCD
GFE | EFG
IJ y|----JI
GJ | /JG
F | / |F
DE | r/ |ED
C | / | C
B 4 |/ | B 3
A +-------A
B 4' x B 3'
C C
DE ED
F F
GJ JG
IJ JI
GFE EFG
DCBABCD
2'1'
- We only calculate the numbers from A in the zenit to I.
- Point I is at 45°, defined by x == y.
- Ground zero is where the + is.
- The A in the zenit is the point (x=0, y=r), r = radius.
- To draw a closed circle we move clockwise (++x), which is to the right (x+=1) or down to the next point, (y-=1).
- every point(x,y) on the circle is r away from the center. Pythagoras says, r²=x²+y².
- This smells like square-root and equitations with 2 solutions, but beware!
- we start at A and want to know, whether we paint next the point below or the point beneath to the right.
- we calculate for both points (x²+y²) and build for both the difference to r² (which stays of course constant).
- since the difference can be negative, we take the abs from it.
- then we look which point is closer to the result (r²), eo ipso smaller.
- depending on that we draw the right or bottom neighbor.
- the so found point
- 1 x, y gets mirrored
- 2 -x, y to the left
- 3 y, x at the diagonal
- 4 -y, x from there to the left
- all those points get mirrored again to the south
- 1' x, -y
- 2' -x, -y
- 3' y, -x
- 4' -y, -x done.
This isn't code golf, but all those numbers at the top of the existing solutions made me think it is, so I spent useless time in golfing my solution. Therefore I added a useless number at the top too. It's 11 times Pi rounded.
object BresenhamCircle extends App {
var count = 0
val r = args(0).toInt
// ratio > 1 means expansion in horizontal direction
val ratio = args(1).toInt
val field = ((0 to 2 * r).map (i=> (0 to 2 * r * ratio).map (j=> ' ').toArray)).toArray
def square (x: Int, y: Int): Int = x * x + y * y
def setPoint (x: Int, y: Int) {
field (x)(y*ratio) = "Bresenham"(count)
field (y)(x*ratio) = "Bresenham"(count)
}
def points (x: Int, y: Int)
{
setPoint (r + x, r + y)
setPoint (r - x, r + y)
setPoint (r + x, r - y)
setPoint (r - x, r - y)
}
def bresenwalk () {
var x = 0;
var y = r;
val rxr = r * r
points (x, y);
do
{
val (dx, dy) = { if (math.abs (rxr - square ((x+1), y)) < math.abs (rxr - square (x, (y-1))))
(1, 0)
else
(0, -1)
}
count = (count + 1) % "Bresenham".length
x += dx
y += dy
points (x, y)
}while ((x <= y))
}
bresenwalk ()
println (field.map (_.mkString ("")).mkString ("\n"))
}
The font-question is decided by sites webserver and your browser settings. Now, that I'm looking it is
'Droid Sans Mono',Consolas,Menlo,Monaco,Lucida Console,Liberation Mono,DejaVu Sans Mono,Bitstream Vera Sans Mono,Courier New,monospace,serif
Font-size is 12px. Pretty useless information, if you ask me, but who does?
Bonus: ellipses and sample output:
The invocation is
scala BresenhamCircle SIZE RATIO
for example
scala BresenhamCircle 10 2
s e r B r e s
h n e e n h
e m a a m e
e r r e
m m
h a a h
n n
s e e s
e e
r r
B B
r r
e e
s e e s
n n
h a a h
m m
e r r e
e m a a m e
h n e e n h
s e r B r e s
A ratio of 2 will print a circular shape for most fonts which happen to be about twice as tall than wide. To compensate for that, we widen by 2.
# As smaller value than 2 only 1 is available:
scala BresenhamCircle 6 1
erBre
aes sea
ah ha
e e
es se
r r
B B
r r
es se
e e
ah ha
aes sea
erBre
# widening it has more freedom:
scala BresenhamCircle 12 5
s e r B r e s
a h n e e n h a
B m m B
e r r e
e s s e
B r r B
a m m a
h h
n n
s e e s
e e
r r
B B
r r
e e
s e e s
n n
h h
a m m a
B r r B
e s s e
e r r e
B m m B
a h n e e n h a
s e r B r e s
I restricted the ratio parameter for Int to keep it simple, but it can easily be widened to allow floats.
Javascript (360)
function c(r){var f=1.83;var e=2*Math.PI/(r*r*r*r*r);var s=r*2+1;var g=Array(s);for(var i=0;i<s;i++){g[i]=Array(Math.round(s*f))};for(var i=0;i<=2*Math.PI;i+=e) {var x=Math.round(f*r*Math.cos(i)+f*r);var y=Math.round(r*Math.sin(i))+r;g[y][x]=1;}for(var j=0;j<g.length;j++){for(var i=0;i<g[j].length;i++)document.write((g[j][i]==1)?'*':' ');document.writeln()}}
http://jsfiddle.net/YssSb/3/ (f is a correction factor for the line-height / font-width ratio. If you use a square font setting, i.e., set line-height = font-size, you can set f=1 and get "square" circles. Or set f arbitrarily for ellipses.)
Output for 3 (interestingly enough, accidentally exactly the same shape as OP), 5, 15:
******
** **
** **
* *
** **
** **
******
*********
*** ****
*** **
** **
* *
* *
* *
** **
*** **
*** ****
*********
***************
****** ******
**** *****
*** ***
*** ***
*** ***
** **
** **
** **
** **
** **
* *
** **
* *
* *
* *
* *
* *
** **
* *
** **
** **
** **
** **
** **
*** ***
*** ***
*** ***
**** *****
****** ******
***************
Python (172)
172 chars including the two mandatory newlines. Uses the Bresenham algorithm for conic curves (no divisions or multiplications); it only outputs circles for square fonts, but should be exempt from staircase effects (ie. always has the same width).
y=input();t=[y*[' ']for x in range(y)];x=0;y-=1;p=3-2*y
while x<=y:t[x][y]=t[y][x]='*';n,y=((x-y+1,y-1),(x,y))[p<0];p+=4*n+6;x+=1
for s in t[::-1]+t:print"".join(s[::-1]+s)
Not very pretty, but well, I thought I'd give it a shot.
****
* *
* *
* *
* *
* *
* *
****
********
*** ***
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
* *
*** ***
********
Edit: typo, replaced addition with division.