yahnke@vms.macc.wisc.edu (Ross Yahnke, MACC) (02/03/89)
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).
A fill routine would do, here's a real ez version, and a rare practical
application of recursion:
Fill(hPt, vPt)
int hPt, vPt;
{ Rect aRect;
Point aPoint;
if (!GetPixel(hPt, vPt))
{ SetRect(&aRect, hPt, vPt, hPt + 1, vPt + 1);
PaintRect(&aRect);
Fill(hPt + 1, vPt + 1);
Fill(hPt , vPt + 1);
Fill(hPt - 1, vPt + 1);
Fill(hPt - 1, vPt );
Fill(hPt - 1, vPt - 1);
Fill(hPt , vPt - 1);
Fill(hPt + 1, vPt - 1);
Fill(hPt + 1, vPt );
}
} /* Fill */
This works well for hollowed out closed loop areas. My application
will be a little different, involving transfering one bitmap image
to another, so if I did a recursive version the above code would be
somewhat changed. 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!
////////////////////////////////////////////////////////////
Internet: yahnke@vms.macc.wisc.edu
Bitnet: yahnke@wiscmacc(.bitnet)
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\rae@geaclib.UUCP (Reid Ellis) (02/06/89)
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). | |A fill routine would do, here's a real ez version, and a rare practical |application of recursion: Aren't there calls in Quickdraw to handle this? I seem to recall routines called SeedFill, CalcMask and some others that might help along these lines -- unless they do a 4-neighbour fill and you want an 8-neighbour fill, or vice versa. :-) Reid "That does it! I'm tired of always being compared to Barry!" "Oh, stop being so sensitive, Wally! I wasn't talking about you! God! You'd never catch Barry getting so defensive!" -- Reid Ellis, geaclib!rae@geac.uucp, rae@geaclib.uucp [if you're lucky]
jackiw@cs.swarthmore.edu (Nick Jackiw) (02/07/89)
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
jimc@iscuva.ISCS.COM (Jim Cathey) (02/14/89)
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! Check out the May 1986 issue of Computer Language magazine. They had a flood (paintbucket) routine in it that was designed to utilize a minimum of stack space (although was still recursive). There was a reasonable discussion of whats 'n whys in the article. The flooder itself was fairly slow, but that was because it was completely unoptimized. It was, however, fairly simple as presented and it wasn't too hard to soup up. It depends greatly on what you're doing during your visit. +----------------+ ! II CCCCCC ! Jim Cathey ! II SSSSCC ! ISC Systems Corp. ! II CC ! TAF-C8; Spokane, WA 99220 ! IISSSS CC ! UUCP: uunet!iscuva!jimc ! II CCCCCC ! (509) 927-5757 +----------------+ "With excitement like this, who is needing enemas?"