Path: ...!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 - worst memory size Date: Wed, 5 Jun 2024 17:59:07 +0300 Organization: A noiseless patient Spider Lines: 229 Message-ID: <20240605175907.000002f0@yahoo.com> References: <86h6h3nvyz.fsf@linuxsc.com> <865xxiok09.fsf@linuxsc.com> <20240319131842.00002138@yahoo.com> <86o7b9ms7d.fsf@linuxsc.com> <20240320115416.00001ab5@yahoo.com> <86zfusltwp.fsf@linuxsc.com> <20240324193352.000062e9@yahoo.com> <86jzlrk0f6.fsf@linuxsc.com> <20240405173033.00006145@yahoo.com> <868r1k1uq8.fsf@linuxsc.com> <20240411152033.00007173@yahoo.com> <86bk6ez9te.fsf@linuxsc.com> <20240417004609.000010aa@yahoo.com> <86plunyj82.fsf@linuxsc.com> <20240417224126.0000727a@yahoo.com> <86a5lpxbd3.fsf@linuxsc.com> <20240420211023.000067cc@yahoo.com> <20240425175606.000059d5@yahoo.com> <20240503183305.000079e0@yahoo.com> <20240605174545.00002c4e@yahoo.com> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Injection-Date: Wed, 05 Jun 2024 16:58:55 +0200 (CEST) Injection-Info: dont-email.me; posting-host="af421c1bf631e23d6a62a4e576399d10"; logging-data="966879"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+zyAbfoGLsMsLVOJLvd2wq13nhdPmAja4=" Cancel-Lock: sha1:MkYve3UaNP+BUsrf7Kn8tbC3fXw= X-Newsreader: Claws Mail 3.19.1 (GTK+ 2.24.33; x86_64-w64-mingw32) Bytes: 8265 On Wed, 5 Jun 2024 17:45:45 +0300 Michael S wrote: > On Fri, 3 May 2024 18:33:05 +0300 > Michael S wrote: > > > On Thu, 25 Apr 2024 17:56:06 +0300 > > Michael S wrote: > > > > > > A solution (sort of) is in line with the famous quite of David > > Wheeler > > - to turn todo lists from bit maps into arrays of > > abscesses-or-ordinates of contact points. > > > > The cost is a memory footprint - 4x bigger than the previous > > version, 32 times bigger than above-mentioned "packed" variant of > > the previous version. But in BigO sense it's the same. > > > > In my tests it reduced the worst case time from O(max(A,B)**3) to > > O(A*B*log(max(A,B)). Which is non-ideal, but probably acceptable, > > because the bad cases should be very rare in practice. > > > > The real trouble is different - I don't know if my "worst case" is > > really the worst. > > > > The code below is for presentation of algorithm in both clear and > > compact manner, with emphasis on symmetry between x and y > > directions. It is not optimal in any sense and can be made > > no-trivially faster both by algorithm enhancements an by > > specialization of critical loops. > > > > > > Following code improves on ideas from the previous post. > Unlike the previous one, it is purely iterative, with no recursion. > The algorithm is simpler and access storage in more compact manner, > i.e. all accessed memory area starts from beginning and grows > according to need. Previous attempt did not have this property. > It's still longer and less simple than I would like. > And here is something that I found by chance when developing the code presented in the previous post. Unlike for the previous one, I can not prove that memory requirements of this algorithm are O(N). However, for all my tests cases it's not just O(N), but consumes significantly less memory than the one above. And it is simpler and shorter. // HIS - todo stack of Horizontal Intervals // with periodic Squeeze of empty intervals #include #include #include typedef unsigned char Color; int floodfill4( Color* image, int width, int height, int x, int y, Color old_color, Color new_color) { if (width <= 0 || height <= 0) return 0; if (x < 0 || x >= width || y < 0 || y >= height) return 0; size_t w = width; Color* row = &image[w*y]; if (row[x] != old_color) return 0; typedef struct { int x0, x1, y; int8_t from; // -1 => from y-1, +1 => from y+1 } interval_t; enum { INITIAL_STACK_SIZE = 128, SQUEEZE_THR = 32, }; interval_t* stack_base = malloc(INITIAL_STACK_SIZE*sizeof(*stack_base)); if (!stack_base) return -1; interval_t* stack_end = &stack_base[INITIAL_STACK_SIZE]; interval_t* todo = stack_base; // recolor initial horizontal interval row[x] = new_color; // look backward int x00; for (x00 = x-1; x00 >= 0 && row[x00]==old_color; --x00) row[x00] = new_color; x00 += 1; // look forward int x01; for (x01 = x+1; x01 < width && row[x01]==old_color; ++x01) row[x01] = new_color; x01 -= 1; // push neighbors of initial interval on todo stack for (int from = -1; from <= 1; from += 2) { unsigned next_y = y-from; if (next_y < (unsigned)height) { todo->x0 = x00; todo->x1 = x01; todo->y = next_y; todo->from = from; ++todo; } } interval_t* squeezed = stack_base; unsigned periodic_i = 0; while (todo != stack_base) { --todo; // pop interval from todo stack int xBeg = todo->x0; int xEnd = todo->x1; int y = todo->y; if (todo < squeezed) squeezed = todo; // look for target points Color* row = &image[y*w]; int x = xBeg; do { if (row[x] == old_color) { // target found row[x] = new_color; int x0 = x; if (x == xBeg) { // look backward for (x0 = x-1; x0 >= 0 && row[x0]==old_color; --x0) row[x0] = new_color; x0 += 1; } // look forward int x1; for (x1 = x+1; x1 < width && row[x1]==old_color; ++x1) row[x1] = new_color; x1 -= 1; int from = todo->from; // remaining part of current interval if (x1+2 <= xEnd) { todo->x0 = x+2; todo->x1 = xEnd; todo->y = y; todo->from = from; ++todo; } // forward continuation unsigned next_y = y-from; if (next_y < (unsigned)height) { todo->x0 = x0; todo->x1 = x1; todo->y = next_y; todo->from = from; ========== REMAINDER OF ARTICLE TRUNCATED ==========