Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!uflorida!haven!rutgers!psuvax1!vu-vlsi!swatsun!jackiw
From: jackiw@cs.swarthmore.edu (Nick Jackiw)
Newsgroups: comp.sys.mac.programmer
Subject: Re: Need help on fill routine
Message-ID: <2403@ilium.cs.swarthmore.edu>
Date: 6 Feb 89 17:32:41 GMT
References: <1173@dogie.edu>
Reply-To: jackiw@ilium.UUCP (Nick Jackiw)
Organization: Visual Geometry Project, Swarthmore College, PA
Lines: 65

In article <1173@dogie.edu> yahnke@vms.macc.wisc.edu (Ross Yahnke, MACC) writes:
> I need to do a pixel by pixel visit of a region for a program I'm 
> working on. (I don't mean "region" in the quickdraw sense really, more of an 
> arbitrary bitmap image).
> 
> [Code Deleted]
>
> The only problem with it is it's really stack 
> intensive, it could blow the stack if the area to be filled is too 
> large. Does anybody know of an unrecursive routine that works
> similarly?                              Thanks in advance!

To do the same thing iteratively, you could maintain an array of points
to visit, with your VISIT routine gobbling up entries off the bottom of
the array and tacking on new-ones-to-visit to the end.  Start with an
array of relatively small size.  When TACKING-ON, if you've reached the
last element, call your Grow procedure.  Grow checks if there's enough
heap space to continue, and if so, expands you array with SetHandleSize.

The advantages:

You're still requiring variable-amounts of memory (I don't think anyone
will show you a fill routine in constant size that doesn't visit every
POSSIBLE point in your drawing region), but only your DATA is growing,
not your data plus all the stack-frame-header crap that an actual
recursive procedural invocation involves.

You're growing in the heap, not the stack. This makes it easier to
check whether you have enough room to continue, esp. under multifinder.
Also, in general I think you'll find there's more free room in the
heap than in the stack.

Also, you don't need to remember "processed" points. Because your
routine isn't tail-recursive, each invocation--which processes a pt before
invoking itself on neighboring points--has to be RETURNED to before being
disposed from the stack.  Thus its still hogging space even though it
doesn't DO anything (--not really true: the first five times it gets
returned to, it reinvokes itself to process another neighbor; the last
time, it does nothing--).  In the array based model, whenever you GROW
your array, you can remove from it the space occupied by entries
"already processed."  Basically, before growing by some fixed size,
BLOCKMOVE the unprocessed components of the array down to the base of the
array. 

With an array, you can also check whether you've already scheduled a pt
to be visited before tacking it on. This will save lots of duplicate
entry space, and perhaps enough duplicate-entry-processing-time to
justify checking your array for the duplicate.  Read up on K-D trees for
fast searches in two-dimensional data pools (Sedgewick, _Algorithms_, has
a good version). Likewise, your code as above is basically:
  (CHECK IF I'M RELEVANT) (DO ME) (DO MY NEIGHBORS)
By expanding your code an insignificant bit to
  (DO ME) (DO MY NEIGHBORS ONLY IF THEY'RE RELEVANT)
will cut down on duplicate processing and wasted stack frames enormously.

Hope this helps.




-- 
+-------------------+-jackiw@cs.swarthmore.edu / !rutgers!bpa!swatsun!jackiw-+
|  nicholas jackiw  | jackiw%campus.swarthmore.edu@swarthmr.bitnet           |
+-------------------+-VGP/MathDept/Swarthmore College, Swarthmore, PA 19081--+
"Big tough man.  Big tough plan.  Spend my life. With a big tough wife." - Ant