recursion

[bill]

I've written a LISP function that uses recursion to draw a picture.
The proceedure is:

f(x,y,r):
1: choose a random theta
2: call f(x+r*cos(theta), y+r*sin(theta), r/2)
3: repeat step 2 for another random theta
4: Draw a circle centre (x,y), radius r.

ie, each circle drawn has 2 smaller circles centred on it's circumference,
with half the first circle's radius. The proceedure terminates when the
circles are smaller than a pixel.

I've added color to the picture, so that each level has a different
color. The problem is, I'm plotting all the circles on one branch, and then
all the circles on another branch, which doesn't look great because the
branches sometimes overlap. What I want to do is draw all the circles on
the last level (ie. the smallest ones), then on the next level, etc. until
the biggest circle is drawn.

My problem is that although I've been using recursion for a couple of
years now, I can't figure out how to do this. I'm sure I should be able to
do it just by changing the order of the steps outlined above.

Any suggestions...?
Thanks in advance, bill

[Ken Anderson]

Try something like this:

(defun f (x1 y1 x2 y2 r)
(when (> r 1)
(let ((theta1 (* (random 1.0) (* 2 pi)))
(theta2 (* (random 1.0) (* 2 pi))))
(f (+ x1 (* r (cos theta1))) (+ y1 (* r (sin theta1)))
(+ x2 (* r (cos theta2))) (+ y2 (* r (sin theta2)))
(truncate r 2)))
(draw-circle x1 y1 r)
(draw-circle x2 y2 r)))

--
Ken Anderson
Internet: kand...@bbn.com
BBN ST Work Phone: 617-873-3160
10 Moulton St. Home Phone: 617-643-0157
Mail Stop 6/4a FAX: 617-873-2794
Cambridge MA 02138
USA

[bill]

On 6 May 1995, Ken Anderson wrote:

> Try something like this:
>
> (defun f (x1 y1 x2 y2 r)
> (when (> r 1)
> (let ((theta1 (* (random 1.0) (* 2 pi)))
> (theta2 (* (random 1.0) (* 2 pi))))
> (f (+ x1 (* r (cos theta1))) (+ y1 (* r (sin theta1)))
> (+ x2 (* r (cos theta2))) (+ y2 (* r (sin theta2)))
> (truncate r 2)))
> (draw-circle x1 y1 r)
> (draw-circle x2 y2 r)))
>
> --
> Ken Anderson

Thanks Ken, it works fine and looks great.

BTW, anyone know if the picture is a fractal? It's perimeter tends to
infinity, but the shape stays within a finite area. Is this sufficient to
make it fractal?

BFN,
bill.

[bill]

oops, forget my last message. Sorry Ken, it doesn't draw the whole
shape. Each circle has to have 2 daughter circles. Your function only draws
one daughter for each circle, although it does draw the smallest circles
first, as I requested. Any more ideas...?

On 6 May 1995, Ken Anderson wrote:

> Try something like this:
>
> (defun f (x1 y1 x2 y2 r)
> (when (> r 1)
> (let ((theta1 (* (random 1.0) (* 2 pi)))
> (theta2 (* (random 1.0) (* 2 pi))))
> (f (+ x1 (* r (cos theta1))) (+ y1 (* r (sin theta1)))
> (+ x2 (* r (cos theta2))) (+ y2 (* r (sin theta2)))
> (truncate r 2)))
> (draw-circle x1 y1 r)
> (draw-circle x2 y2 r)))
>
> --
> Ken Anderson

Sorry about the last message, I didn't look closely enough.

bill.

[bill]

On Mon, 8 May 1995, Thomas Yan wrote:

> In article <Pine.SV4.3.91.950506174328.23348A-100000@unicorn> you write:
> >What I want to do is draw all the circles on
> >the last level (ie. the smallest ones), then on the next level, etc. until
> >the biggest circle is drawn.
>

> while not empty todo:
> 1. dequeue (x,y,r) from todo
> 2. push (x,y,r) onto todraw
> 3. if r is large enough, then
> 4. enqueue (x',y',r/2) for random theta onto todo
> 5. repeat step 3 for another random theta
> for each (x,y,r) in todraw, draw circle (x,y,r)

Thanks Thomas, I've had a few other emails pointing out that this
is the only way to do it.

It works well (a bit slower, a bit more memory hungry, but a great picture).
Shame there's no easier way to do it...

bill.