Path: ...!weretis.net!feeder8.news.weretis.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail From: Michael S Newsgroups: comp.lang.c Subject: Re: filling area by color atack safety Date: Tue, 19 Mar 2024 15:49:00 +0200 Organization: A noiseless patient Spider Lines: 124 Message-ID: <20240319154900.00001dca@yahoo.com> References: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Injection-Info: dont-email.me; posting-host="a8871862f6b018cf47b195a984142ca8"; logging-data="789293"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/S2BWZBvAqPTkTnU9Doe5wReFkv5XiCVs=" Cancel-Lock: sha1:DRppXLT87mFrrT7/WNl6m7fcKJs= X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32) Bytes: 5676 On Tue, 19 Mar 2024 11:57:53 +0000 Malcolm McLean wrote: > > No. Mine takes horizontal scan lines and extends them, then places > the pixels above and below in a queue to be considered as seeds for > the next scan line. (It's not mine, but I don't know who invented it. > It wasn't me.) > > Tim, now what does it do? Essentially it's the recursive fill > algorithm but with the data only on the stack instead of the call and > the data. And todo is actually a queue rather than a stack. > > Now why would it be slower? Probaby because you usually only hit a > pixel three times with mine - once below, once above, and once for > the scan line itself, whilst you consider it 5 times for Tim's - once > for each neighbour and once for itself. Then horizontally adjacent > pixels are more likely to be in the same cache line than vertically > adjacent pixels, so processing images in scan lines tends to be a bit > faster. > Below is a variant of recursive algorithm that is approximately as fast as your code (1.25x faster for filling solid rectangle, 1.43x slower for filling snake shape). The code is a bit long, but I hope that the logic is still obvious and there is no need to prove correctness. I have a micro-optimized variant of the same algorithm that is as fast or faster than yours in all cases that I tested, but posting micro-optimized code on c.l.c is a bad sportsmanship. Recursion depth of this algorithm for typical solid shape is O(max(width,height)), but for a worst case it still very bad, about N/4. And since there are more local variable to preserve, the worst case size of occupied stack is likely even bigger than in simple (but non-naive) recursion. So, while fast, I wouldn't use this algorithm in general-purpose library. But it can serve as a reference point for implementation with explicit stack. struct recursive_context_t { unsigned char *grey; int width, height; unsigned char target, dest; }; static void floodfill_r_core(const struct recursive_context_t* context, int x, int y); int floodfill_r( unsigned char *grey, int width, int height, int x, int y, unsigned char target, unsigned char dest) { if (x < 0 || x >= width || y < 0 || y >= height) return 0; if (grey[y*width+x] != target) return 0; struct recursive_context_t context = { .grey = grey, .width = width, .height = height, .target = target, .dest = dest, }; floodfill_r_core(&context, x, y); return 1; } static void floodfill_r_core(const struct recursive_context_t* context, int x, int y) { // point (x,y) is in target rectangle and has target color. It's guaranteed by caller // Find maximal cross (of Saint George's variety) with target color and center at (x,y) // go left int x0; for (x0 = x-1; x0 >= 0 && context->grey[y*context->width+x0] == context->target; --x0); ++x0; // go right int x1; for (x1 = x+1; x1 < context->width && context->grey[y*context->width+x1] == context->target; ++x1); // go up int y0; for (y0 = y-1; y0 >= 0 && context->grey[y0*context->width+x] == context->target; --y0); ++y0; // go down int y1; for (y1 = y+1; y1 < context->height && context->grey[y1*context->width+x] == context->target; ++y1); // Fill cross with destination color for (int i = x0; i < x1; ++i) context->grey[y*context->width+i] = context->dest; for (int i = y0; i < y1; ++i) context->grey[i*context->width+x] = context->dest; if (y > 0) { // recursion into points above horizontal line unsigned char *row = &context->grey[(y-1)*context->width]; for (int i = x0; i < x1; ++i) if (row[i] == context->target) floodfill_r_core(context, i, y-1); } if (y+1 < context->height) { // recursion into points below horizontal line unsigned char *row = &context->grey[(y+1)*context->width]; for (int i = x0; i < x1; ++i) if (row[i] == context->target) floodfill_r_core(context, i, y+1); } if (x > 0) { // recursion into points left of vertical line unsigned char *col = &context->grey[x-1]; for (int i = y0; i < y1; ++i) if (col[i*context->width] == context->target) floodfill_r_core(context, x-1, i); } if (x+1 < context->width) { // recursion into points right of vertical line unsigned char *col = &context->grey[x+1]; for (int i = y0; i < y1; ++i) if (col[i*context->width] == context->target) floodfill_r_core(context, x+1, i); } }