On Wed, 5 Jun 2024 17:45:45 +0300
Michael S <
already5chosen@yahoo.com> wrote:
On Fri, 3 May 2024 18:33:05 +0300
Michael S <already5chosen@yahoo.com> wrote:
On Thu, 25 Apr 2024 17:56:06 +0300
Michael S <already5chosen@yahoo.com> 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 <stddef.h>
#include <stdlib.h>
#include <stdint.h>
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;
++todo;
}
// bounces
y = y+from;
if (xEnd+2 <= x1) { // bounce on the right side
todo->x0 = xEnd+2;
todo->x1 = x1;
todo->y = y;
todo->from = -from;
++todo;
}
if (x0 <= xBeg-2) { // bounce on the left side
todo->x0 = x0;
todo->x1 = xBeg-2;
todo->y = y;
todo->from = -from;
++todo;
}
break;
}
++x;
} while (x <= xEnd);
++periodic_i;
if ((periodic_i & 31)==0) { // maintenance
if (todo - squeezed >= SQUEEZE_THR) {
// squeeze empty intervals
interval_t* wr = squeezed;
while (squeezed != todo) {
Color* row = &image[squeezed->y*w];
for (int x = squeezed->x0; x <= squeezed->x1; ++x) {
if (row[x] == old_color) { // interval non-empty
*wr = *squeezed;
wr->x0 = x;
++wr;
break;
}
}
++squeezed;
}
todo = squeezed = wr;
}
if (stack_end-todo < 67) {
// Allocate more space
size_t todo_i = todo - stack_base;
size_t squeezed_i = squeezed - stack_base;
size_t sz = stack_end - stack_base;
sz += (sz/128)*64;
interval_t* tmp = realloc(
stack_base, sz*sizeof(*stack_base));
if (!tmp) {
free(stack_base);
return -1;
}
stack_base = tmp;
stack_end = &stack_base[sz];
todo = &stack_base[todo_i];
squeezed = &stack_base[squeezed_i];
}
}
}
free(stack_base);
return 1;
}
Re: filling area by color atack safety - worst memory size
Re: filling area by color atack safety - worst memory size