Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #383962
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: filling area by color atack safety |
| Date | 2024-03-24 10:24 -0700 |
| Organization | A noiseless patient Spider |
| Message-ID | <86jzlrk0f6.fsf@linuxsc.com> (permalink) |
| References | (3 earlier) <20240319131842.00002138@yahoo.com> <86o7b9ms7d.fsf@linuxsc.com> <20240320115416.00001ab5@yahoo.com> <86zfusltwp.fsf@linuxsc.com> <20240324193352.000062e9@yahoo.com> |
Michael S <already5chosen@yahoo.com> writes:
> On Wed, 20 Mar 2024 10:01:10 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Michael S <already5chosen@yahoo.com> writes:
[...]
>>> Generally, I like your algorithm.
>>> It was surprising for me that queue can work better than stack, my
>>> intuition suggested otherwise, but facts are facts.
>>
>> Using a stack is like a depth-first search, and a queue is like a
>> breadth-first search. For a pixel field of size N x N, doing a
>> depth-first search can lead to memory usage of order N**2,
>> whereas a breadth-first search has a "frontier" at most O(N).
>> Another way to think of it is that breadth-first gets rid of
>> visited nodes as fast as it can, but depth-first keeps them
>> around for a long time when everything is reachable from anywhere
>> (as will be the case in large simple reasons).
>
> For my test cases the FIFO depth of your algorithm never exceeds
> min(width,height)*2+2. I wonder if existence of this or similar
> limit can be proven theoretically.
I believe it is possible to prove the strict FIFO algorithm is
O(N) for an N x N pixel field, but I haven't tried to do so in
any rigorous way, nor do I know what the constant is. It does
seem to be larger than 2.
As for finding a worst case, try this (expressed in pseudo code):
let pc = { width/2, height/2 }
// assume pixel field 'field' starts out as all zeroes
color 8 "legs" with the value '1' as follows:
leg from { 1, pc.y-1 } to { pc.x -1, pc.y-1 }
leg from { 1, pc.y+1 } to { pc.x -1, pc.y+1 }
leg from { px.x + 1, pc.y-1 } to { width-2, pc.y-1 }
leg from { px.x + 1, pc.y+1 } to { width-2, pc.y+1 }
leg from { px.x - 1, 1 } to { px.x -1, pc.y-1 }
leg from { px.x + 1, 1 } to { px.x +1, pc.y-1 }
leg from { px.x - 1, pc.y+1 } to { px.x -1, height/2 }
leg from { px.x + 1, pc.y+1 } to { px.x +1, height/2 }
So the pixel field should look like this (with longer legs for a
bigger pixel field), with '-' being 0 and '*' being 1:
+-----------------------+
| - - - - - - - - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - * * * * - * * * * - |
| - - - - - - - - - - - |
| - * * * * - * * * * - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - * - * - - - - |
| - - - - - - - - - - - |
+-----------------------+
Now start coloring at the center point with a new value
of 2.
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar
filling area by color atack safety fir <fir@grunge.pl> - 2024-03-16 05:11 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 11:33 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-16 13:55 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-16 14:41 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 10:42 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 03:00 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-18 14:23 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 14:13 -0700
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 16:05 +0100
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-19 17:16 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-19 17:33 +0000
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 23:07 +0100
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-20 09:29 +0100
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 03:04 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 14:45 +0000
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-16 18:21 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 20:02 +0000
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-16 13:29 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-17 13:19 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-18 14:40 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 23:23 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 15:32 +0200
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 11:25 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 12:37 +0000
Re: filling area by color atack safety Kaz Kylheku <433-929-6894@kylheku.com> - 2024-03-17 17:11 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-23 00:21 +0000
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-23 14:43 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-23 11:48 -0700
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-24 20:48 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-28 22:51 -0700
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-16 15:40 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 15:09 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 14:56 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 17:42 +0200
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 18:25 +0200
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 19:39 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 11:36 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 18:51 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 23:10 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-19 12:06 +0000
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 00:03 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 01:17 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 00:30 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 12:06 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 13:44 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 15:44 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 15:17 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 02:15 +0100
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-17 17:45 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 18:28 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-18 07:58 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 09:26 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-18 17:28 +0100
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 17:25 +0000
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-18 17:42 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-18 18:50 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-19 11:41 +0100
Re: filling area by color atack safety Richard Harnden <richard.nospam@gmail.invalid> - 2024-03-19 12:19 +0000
Re: filling area by color atack safety Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-03-18 11:10 -0700
Keith-world (Was: filling area by color atack safety) gazelle@shell.xmission.com (Kenny McCormack) - 2024-03-18 22:42 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-19 12:31 +0100
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-18 16:18 -0700
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-19 11:32 +0100
Re: filling area by color atack safety scott@slp53.sl.home (Scott Lurndal) - 2024-03-16 18:25 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 10:31 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-17 12:28 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 12:49 +0000
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-17 17:59 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-19 23:52 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:36 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 14:46 +0200
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 12:54 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 15:15 +0200
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 13:23 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-17 15:37 +0200
Re: filling area by color atack safety David Brown <david.brown@hesbynett.no> - 2024-03-17 18:05 +0100
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 14:10 +0000
Re: filling area by color atack safety Spiros Bousbouras <spibou@gmail.com> - 2024-03-17 16:58 +0000
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-17 22:14 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 22:21 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 02:30 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-18 11:08 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 22:54 -0700
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-19 11:41 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-19 21:19 -0700
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:13 +0100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 10:41 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 15:20 +0100
Re: filling area by color atack safety Lew Pitcher <lew.pitcher@digitalfreehold.ca> - 2024-03-17 14:27 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-17 15:13 +0000
Re: filling area by color atack safety Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2024-03-19 10:57 +1100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:26 +0100
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-16 19:13 +0000
Re: filling area by color atack safety bart <bc@freeuk.com> - 2024-03-16 20:23 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-16 20:29 +0000
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 01:48 +0100
Re: filling area by color atack safety Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2024-03-22 13:04 +1100
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-22 17:55 +0300
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-22 18:31 +0300
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-23 11:06 +0100
Re: filling area by color atack safety Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> - 2024-03-17 18:03 +1100
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 13:09 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-18 22:42 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-19 13:18 +0200
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-19 11:57 +0000
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-19 15:49 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-19 21:43 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 10:56 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 06:51 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-19 19:18 +0200
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 09:27 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 09:39 +0100
Re: filling area by color atack safety fir <fir@grunge.pl> - 2024-03-20 09:51 +0100
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 07:27 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-24 20:27 +0300
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-24 13:26 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-24 14:26 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-25 01:28 +0300
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-26 17:52 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-30 00:54 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-30 21:26 +0300
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-09 01:00 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-28 23:04 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-29 15:21 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-29 23:58 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-30 21:15 +0300
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-31 10:54 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-09 02:32 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-09 01:55 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-30 11:59 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 10:26 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-21 15:36 +0200
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-21 09:47 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-19 21:40 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-19 21:43 -0700
Re: filling area by color atack safety "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-03-19 21:48 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-20 11:54 +0200
Re: filling area by color atack safety Ben Bacarisse <ben.usenet@bsb.me.uk> - 2024-03-20 10:23 +0000
Re: filling area by color atack safety Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-03-20 12:06 +0000
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 07:52 -0700
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-20 10:01 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-24 19:33 +0300
Re: filling area by color atack safety Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-03-24 10:24 -0700
Re: filling area by color atack safety Michael S <already5chosen@yahoo.com> - 2024-03-25 01:04 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-05 17:30 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-10 19:47 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-11 15:20 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 21:06 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 21:55 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:09 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-12 11:13 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-13 08:30 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:38 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-11 22:43 -0700
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-12 11:59 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-13 20:26 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-13 10:54 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-13 23:11 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-17 10:47 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-17 22:41 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-04-19 14:59 -0700
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-20 21:10 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-04-25 17:56 +0300
csiph-web