Path: ...!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups: comp.lang.c
Subject: Re: filling area by color atack safety - worst memory size
Date: Sat, 13 Apr 2024 08:30:03 -0700
Organization: A noiseless patient Spider
Lines: 106
Message-ID: <86y19hxouc.fsf@linuxsc.com>
References: <ut3669$21eur$1@i2pn2.org> <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> <86o7afyxnk.fsf@linuxsc.com> <20240412111305.00004bf2@yahoo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Injection-Date: Sat, 13 Apr 2024 17:30:06 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="44a1207aeaadfda1483c7b96a3737e57";
	logging-data="3234235"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1+X8iJav99cSWXIOpvELf5rkM1OnuKkPwU="
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock: sha1:0E8rk8HT4HPmCPzui5w/deGrL9k=
	sha1:HXnEO+LurFtDc3kGsq5Nt2YyjVI=
Bytes: 4590

Michael S <already5chosen@yahoo.com> writes:

> On Thu, 11 Apr 2024 22:09:51 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
[...]

>> I do timings over these sizes:
>>
>>       25 x 19
>>       19 x 25
>>      200 x 200
>>     1280 x 760
>>      760 x 1280
>>     1920 x 1080
>>     1080 x 1920
>>     3840 x 2160
>>     2160 x 3840
>>     4096 x 4096
>>    38400 x 21600
>>    21600 x 38400
>>    32767 x 32767
>>    32768 x 32768
>
> I didn't went that far up (ended at 4K)

I test large sizes for three reasons.  One, even if viewable
area is smaller, virtual displays might be much larger.  Two,
to see how the algorithms scale.  Three, larger areas have
relatively less influence from edge effects.

Also I have now added

      275 x 25      25 x 275
      400 x 300    300 x 400
      640 x 480    480 x 640
     1600 x 900    900 x 1600
    16000 x 9000  9000 x 16000


> and I only test landscape sizes.  May be, I'd add portrait option
> to see anisotropic behaviors.

I decided to do both, one, for symmetry (and there are still some
applications for portrait mode), and two, to see whether that has
an effect on behavior (indeed my latest algorithm is anisotropic,
so it is good to test the flipped sizes).

>> with these patterns:
>>
>>    fractal
>>    slalom
>>    rotated slalom
>>    horizontal snake and vertical snake
>>    cross in cross
>>    donut aka ellipse with hole
>>    entire field starting from center
>>
>> If you have other patterns to suggest that would be great,
>> I can try to incorporate them (especially if there is
>> code to generate the pattern).
>>
>> Patterns are allowed to include a nominal start point,
>> otherwise I can make an arbitrary choice and assign one.
>
> My suit is about the same with following exceptions:
> 1. I didn't add donut yet
> 2. + 3 greeds with cell size 2, 3 and 4
> 3. + fractal tree

By "fractal" I meant fractal tree.  Sorry if that was confusing.

> 4. + entire field starting from corner

I used to do that but took it out as redundant.  I've added
it back now. :)

> It seems, neither of us tests the cases in which linear dimensions
> of the shape are much smaller than those of the field.

Shouldn't make a difference (for any of the algorithms shown) as
long as there is at least a 1 pixel border around the pattern.
Maybe I will add that variation (ick, a lot of work).  By the
way the donut pattern already has a 1 pixel border, ie, does
not touch any edge.

> static void make_grid(
>   unsigned char *image,
>   int width, int height,
>   unsigned char background_c,
>   unsigned char pen_c, int cell_sz)
> {
>   for (int y = 0; y < height; ++y) {
>     unsigned char* p = &image[y*width];
>     if (y % cell_sz == 0) {
>       memset(p, pen_c, width);
>     } else {
>       for (int x = 0; x < width; ++x)
>         p[x] = x % cell_sz ? background_c : pen_c;
>     }
>   }
> }

Ahh, this is what you meant by greed.  A nice set of patterns.
I wrote a variation where the "line width" as well as the
"hole width" is variable, and added a bunch of those to my
tests (so a full timing suite now runs for several hours).