Re: filling area by color atack safety - worst memory size

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).