Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #383647 > unrolled thread
| Started by | fir <fir@grunge.pl> |
|---|---|
| First post | 2024-03-16 05:11 +0100 |
| Last post | 2024-05-15 09:57 -0700 |
| Articles | 20 on this page of 167 — 16 participants |
Back to article view | Back to comp.lang.c
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
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-05-03 18:33 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-06-05 17:45 +0300
Re: filling area by color atack safety - worst memory size Michael S <already5chosen@yahoo.com> - 2024-06-05 17:59 +0300
Re: filling area by color atack safety - worst memory size Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-05-15 09:57 -0700
Page 6 of 9 — ← Prev page 1 2 3 4 5 [6] 7 8 9 Next page →
| From | Peter 'Shaggy' Haywood <phaywood@alphalink.com.au> |
|---|---|
| Date | 2024-03-17 18:03 +1100 |
| Message-ID | <t7hick-t14.ln1@hendrix.foo> |
| In reply to | #383647 |
Groovy hepcat fir was jivin' in comp.lang.c on Sat, 16 Mar 2024 03:11
pm. It's a cool scene! Dig it.
> i was writing simple editor (something like paint but more custom for
> my eventual needs) for big pixel (low resolution) drawing
>
> it showed in a minute i need a click for changing given drawed area of
> of one color into another color (becouse if no someone would need to
> do
> it by hand pixel by pixel and the need to change color of given
> element is very common)
Not really a C question, but I'll forgive that for now.
What you're looking for (and can easily find on Google, Duck Duck Go
or any other search engine, if you but utilise any of those services)
is called a "flood fill" algorithm.
But a word of advice: recursion can be tricky if you don't understand
the effect. Your method creates a very large recursive chain. This is
best avoided. Try it out "by hand". Get a piece of graph paper and draw
some shapes on it, including some complex ones. Now choose one of these
shapes and choose a starting pixel within this area and try applying
your algorithm. With a coloured pencil, colour in each square as you
go, just as the algorithm would. Also make note of the level of
recursion as you go. I think you'll be amazed. Repeat for all the
shapes on your graph paper.
--
----- Dig the NEW and IMPROVED news sig!! -----
-------------- Shaggy was here! ---------------
Ain't I'm a dawg!!
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-18 13:09 -0700 |
| Message-ID | <86h6h3nvyz.fsf@linuxsc.com> |
| In reply to | #383647 |
fir <fir@grunge.pl> writes:
> i was writing simple editor (something like paint but more custom for
> my eventual needs) for big pixel (low resolution) drawing
>
> it showed in a minute i need a click for changing given drawed area of
> of one color into another color (becouse if no someone would need to
> do it by hand pixel by pixel and the need to change color of given
> element is very common)
>
> there is very simple method of doing it - i men i click in given color
> pixel then replace it by my color and call the same function on
> adjacent 4 pixels (only need check if it is in screen at all and if
> the color to change is that initial color
>
> int RecolorizePixelAndAdjacentOnes(int x, int y, unsigned old_color,
> unsigned new_color)
> {
> if(old_color == new_color) return 0;
>
> if(XYIsInScreen( x, y))
> if(GetPixelUnsafe(x,y)==old_color)
> {
> SetPixelSafe(x,y,new_color);
> RecolorizePixelAndAdjacentOnes(x+1, y, old_color, new_color);
> RecolorizePixelAndAdjacentOnes(x-1, y, old_color, new_color);
> RecolorizePixelAndAdjacentOnes(x, y-1, old_color, new_color);
> RecolorizePixelAndAdjacentOnes(x, y+1, old_color, new_color);
> return 1;
> }
>
> return 0;
> }
>
> it work but im not quite sure how to estimate the safety of this -
> incidentally as i said i use this editor to low res graphics like
> 200x200 pixels or less, and it is only a toll of private use,
> yet i got no time to work on it more than 1-2-3 days i guess but still
>
> is there maybe simple way to improve it?
As others have explained using simple recursion like this
runs the risk of producing a stack overflow.
Here is a short routine that uses allocated memory rather than
recursion, and so does not have the stack overflow risk that
the above recursive routine does.
The code below uses a slightly different interface to access
the pixel field but I expect you can see how to adapt it to
your interface.
Also the code uses a variably modified type in two places. It
should be easy to change the code to use ordinary types rather
than variably modified types if it's important to do that in
your environment. And it may be the case that changing to use
a different interface to access and change the pixel field will
get rid of the variably modified types so that they wouldn't be
needed anyway.
Oh, before I forget. If someone doesn't like using a single
fixed-size allocated area, it isn't hard to change the code
so that the allocated area grows as needed (and starting with
a smaller size, presumably). I leave doing that as an
exercise.
The code:
#include <assert.h>
typedef unsigned char Color;
typedef unsigned int UI;
typedef struct { UI x, y; } Point;
typedef unsigned int Index;
static _Bool change_it( UI w, UI h, Color [w][h], Point, Color, Color );
void
fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color new ){
static const Point deltas[4] = { {1,0}, {0,1}, {-1,0}, {0,-1}, };
Index k = 0;
Index n = (w+h) *17 /16 +10;
Point *todo = malloc( n * sizeof *todo );
if( todo && change_it( w, h, pixels, p0, old, new ) ) todo[k++] = p0;
while( k > 0 ){
Index j = n-k;
memmove( todo + j, todo, k * sizeof *todo );
k = 0;
while( j < n ){
Point p = todo[ j++ ];
for( Index i = 0; i < 4; i++ ){
Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
if( ! change_it( w, h, pixels, q, old, new ) ) continue;
assert( j > k );
todo[ k++ ] = q;
}
}
}
free( todo );
}
_Bool
change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color new ){
if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old ) return 0;
return pixels[p.x][p.y] = new, 1;
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-18 22:42 -0700 |
| Message-ID | <865xxiok09.fsf@linuxsc.com> |
| In reply to | #383727 |
Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
[...]
Here is the refinement that uses a resizing rather than
fixed-size buffer.
typedef unsigned char Color;
typedef unsigned int UI;
typedef struct { UI x, y; } Point;
typedef unsigned int Index;
static _Bool change_it( UI w, UI h, Color [w][h], Point, Color, Color );
void
fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color new ){
static const Point deltas[4] = { {1,0}, {0,1}, {-1,0}, {0,-1}, };
UI k = 0;
UI n = 17;
Point *todo = malloc( n * sizeof *todo );
if( todo && change_it( w, h, pixels, p0, old, new ) ) todo[k++] = p0;
while( k > 0 ){
Index j = n-k;
memmove( todo + j, todo, k * sizeof *todo );
k = 0;
while( j < n ){
Point p = todo[ j++ ];
for( Index i = 0; i < 4; i++ ){
Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
if( ! change_it( w, h, pixels, q, old, new ) ) continue;
todo[ k++ ] = q;
}
if( j-k < 3 ){
Index new_n = n+n/4;
Index new_j = new_n - (n-j);
Point *t = realloc( todo, new_n * sizeof *t );
if( !t ){ k = 0; break; }
memmove( t + new_j, t + j, (n-j) * sizeof *t );
todo = t, n = new_n, j = new_j;
}
}
}
free( todo );
}
_Bool
change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color new ){
if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old ) return 0;
return pixels[p.x][p.y] = new, 1;
}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-19 13:18 +0200 |
| Message-ID | <20240319131842.00002138@yahoo.com> |
| In reply to | #383732 |
On Mon, 18 Mar 2024 22:42:14 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>
> [...]
>
> Here is the refinement that uses a resizing rather than
> fixed-size buffer.
>
>
> typedef unsigned char Color;
> typedef unsigned int UI;
> typedef struct { UI x, y; } Point;
> typedef unsigned int Index;
>
> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
> Color );
>
> void
> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color
> new ){ static const Point deltas[4] = { {1,0}, {0,1}, {-1,0},
> {0,-1}, }; UI k = 0;
> UI n = 17;
> Point *todo = malloc( n * sizeof *todo );
>
> if( todo && change_it( w, h, pixels, p0, old, new ) )
> todo[k++] = p0;
>
> while( k > 0 ){
> Index j = n-k;
> memmove( todo + j, todo, k * sizeof *todo );
> k = 0;
>
> while( j < n ){
> Point p = todo[ j++ ];
> for( Index i = 0; i < 4; i++ ){
> Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
> if( ! change_it( w, h, pixels, q, old, new ) )
> continue; todo[ k++ ] = q;
> }
>
> if( j-k < 3 ){
> Index new_n = n+n/4;
> Index new_j = new_n - (n-j);
> Point *t = realloc( todo, new_n * sizeof *t );
> if( !t ){ k = 0; break; }
> memmove( t + new_j, t + j, (n-j) * sizeof *t );
> todo = t, n = new_n, j = new_j;
> }
> }
> }
>
> free( todo );
> }
>
> _Bool
> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color
> new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old )
> return 0; return pixels[p.x][p.y] = new, 1;
> }
This variant is significantly slower than Malcolm's.
2x slower for solid rectangle, 6x slower for snake shape.
Is it the same algorithm?
Besides, I don't think that use of VLA in library code is a good idea.
VLA is optional in latest C standards. And incompatible with C++.
[toc] | [prev] | [next] | [standalone]
| From | Malcolm McLean <malcolm.arthur.mclean@gmail.com> |
|---|---|
| Date | 2024-03-19 11:57 +0000 |
| Message-ID | <utbuk3$qed7$1@dont-email.me> |
| In reply to | #383737 |
On 19/03/2024 11:18, Michael S wrote:
> On Mon, 18 Mar 2024 22:42:14 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>
>> [...]
>>
>> Here is the refinement that uses a resizing rather than
>> fixed-size buffer.
>>
>>
>> typedef unsigned char Color;
>> typedef unsigned int UI;
>> typedef struct { UI x, y; } Point;
>> typedef unsigned int Index;
>>
>> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
>> Color );
>>
>> void
>> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old, Color
>> new ){ static const Point deltas[4] = { {1,0}, {0,1}, {-1,0},
>> {0,-1}, }; UI k = 0;
>> UI n = 17;
>> Point *todo = malloc( n * sizeof *todo );
>>
>> if( todo && change_it( w, h, pixels, p0, old, new ) )
>> todo[k++] = p0;
>>
>> while( k > 0 ){
>> Index j = n-k;
>> memmove( todo + j, todo, k * sizeof *todo );
>> k = 0;
>>
>> while( j < n ){
>> Point p = todo[ j++ ];
>> for( Index i = 0; i < 4; i++ ){
>> Point q = { p.x + deltas[i].x, p.y + deltas[i].y };
>> if( ! change_it( w, h, pixels, q, old, new ) )
>> continue; todo[ k++ ] = q;
>> }
>>
>> if( j-k < 3 ){
>> Index new_n = n+n/4;
>> Index new_j = new_n - (n-j);
>> Point *t = realloc( todo, new_n * sizeof *t );
>> if( !t ){ k = 0; break; }
>> memmove( t + new_j, t + j, (n-j) * sizeof *t );
>> todo = t, n = new_n, j = new_j;
>> }
>> }
>> }
>>
>> free( todo );
>> }
>>
>> _Bool
>> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old, Color
>> new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] != old )
>> return 0; return pixels[p.x][p.y] = new, 1;
>> }
>
> This variant is significantly slower than Malcolm's.
> 2x slower for solid rectangle, 6x slower for snake shape.
> Is it the same algorithm?
>
No. Mine takes horizontal scan lines and extends them, then places the
pixels above and below in a queue to be considered as seeds for the next
scan line. (It's not mine, but I don't know who invented it. It wasn't me.)
Tim, now what does it do? Essentially it's the recursive fill algorithm
but with the data only on the stack instead of the call and the data.
And todo is actually a queue rather than a stack.
Now why would it be slower? Probaby because you usually only hit a pixel
three times with mine - once below, once above, and once for the scan
line itself, whilst you consider it 5 times for Tim's - once for each
neighbour and once for itself. Then horizontally adjacent pixels are
more likely to be in the same cache line than vertically adjacent
pixels, so processing images in scan lines tends to be a bit faster.
> Besides, I don't think that use of VLA in library code is a good idea.
> VLA is optional in latest C standards. And incompatible with C++.
>
>
--
Check out Basic Algorithms and my other books:
https://www.lulu.com/spotlight/bgy1mm
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-19 15:49 +0200 |
| Message-ID | <20240319154900.00001dca@yahoo.com> |
| In reply to | #383740 |
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>
> No. Mine takes horizontal scan lines and extends them, then places
> the pixels above and below in a queue to be considered as seeds for
> the next scan line. (It's not mine, but I don't know who invented it.
> It wasn't me.)
>
> Tim, now what does it do? Essentially it's the recursive fill
> algorithm but with the data only on the stack instead of the call and
> the data. And todo is actually a queue rather than a stack.
>
> Now why would it be slower? Probaby because you usually only hit a
> pixel three times with mine - once below, once above, and once for
> the scan line itself, whilst you consider it 5 times for Tim's - once
> for each neighbour and once for itself. Then horizontally adjacent
> pixels are more likely to be in the same cache line than vertically
> adjacent pixels, so processing images in scan lines tends to be a bit
> faster.
>
Below is a variant of recursive algorithm that is approximately as
fast as your code (1.25x faster for filling solid rectangle, 1.43x
slower for filling snake shape).
The code is a bit long, but I hope that the logic is still obvious and
there is no need to prove correctness.
I have a micro-optimized variant of the same algorithm that is as fast
or faster than yours in all cases that I tested, but posting
micro-optimized code on c.l.c is a bad sportsmanship.
Recursion depth of this algorithm for typical solid shape is
O(max(width,height)), but for a worst case it still very bad, about N/4.
And since there are more local variable to preserve, the worst case
size of occupied stack is likely even bigger than in simple (but
non-naive) recursion. So, while fast, I wouldn't use this algorithm in
general-purpose library.
But it can serve as a reference point for implementation with explicit
stack.
struct recursive_context_t {
unsigned char *grey;
int width, height;
unsigned char target, dest;
};
static void floodfill_r_core(const struct recursive_context_t* context,
int x, int y);
int floodfill_r(
unsigned char *grey,
int width, int height,
int x, int y,
unsigned char target, unsigned char dest)
{
if (x < 0 || x >= width || y < 0 || y >= height)
return 0;
if (grey[y*width+x] != target)
return 0;
struct recursive_context_t context = {
.grey = grey,
.width = width,
.height = height,
.target = target,
.dest = dest,
};
floodfill_r_core(&context, x, y);
return 1;
}
static void floodfill_r_core(const struct recursive_context_t* context,
int x, int y) {
// point (x,y) is in target rectangle and has target color. It's
guaranteed by caller
// Find maximal cross (of Saint George's variety) with target color
and center at (x,y) // go left
int x0;
for (x0 = x-1; x0 >= 0 &&
context->grey[y*context->width+x0] == context->target; --x0); ++x0;
// go right
int x1;
for (x1 = x+1; x1 < context->width &&
context->grey[y*context->width+x1] == context->target; ++x1); // go up
int y0;
for (y0 = y-1; y0 >= 0 &&
context->grey[y0*context->width+x] == context->target; --y0); ++y0;
// go down
int y1;
for (y1 = y+1; y1 < context->height &&
context->grey[y1*context->width+x] == context->target; ++y1);
// Fill cross with destination color
for (int i = x0; i < x1; ++i)
context->grey[y*context->width+i] = context->dest;
for (int i = y0; i < y1; ++i)
context->grey[i*context->width+x] = context->dest;
if (y > 0) { // recursion into points above horizontal line
unsigned char *row = &context->grey[(y-1)*context->width];
for (int i = x0; i < x1; ++i)
if (row[i] == context->target)
floodfill_r_core(context, i, y-1);
}
if (y+1 < context->height) { // recursion into points below
horizontal line unsigned char *row =
&context->grey[(y+1)*context->width]; for (int i = x0; i < x1; ++i)
if (row[i] == context->target)
floodfill_r_core(context, i, y+1);
}
if (x > 0) { // recursion into points left of vertical line
unsigned char *col = &context->grey[x-1];
for (int i = y0; i < y1; ++i)
if (col[i*context->width] == context->target)
floodfill_r_core(context, x-1, i);
}
if (x+1 < context->width) { // recursion into points right of
vertical line unsigned char *col = &context->grey[x+1];
for (int i = y0; i < y1; ++i)
if (col[i*context->width] == context->target)
floodfill_r_core(context, x+1, i);
}
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-19 21:43 -0700 |
| Message-ID | <86jzlxms22.fsf@linuxsc.com> |
| In reply to | #383744 |
Michael S <already5chosen@yahoo.com> writes: > On Tue, 19 Mar 2024 11:57:53 +0000 > Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: > >> No. Mine takes horizontal scan lines and extends them, then places >> the pixels above and below in a queue to be considered as seeds for >> the next scan line. (It's not mine, but I don't know who invented it. >> It wasn't me.) >> >> Tim, now what does it do? Essentially it's the recursive fill >> algorithm but with the data only on the stack instead of the call and >> the data. And todo is actually a queue rather than a stack. >> >> Now why would it be slower? Probaby because you usually only hit a >> pixel three times with mine - once below, once above, and once for >> the scan line itself, while you consider it 5 times for Tim's - once >> for each neighbour and once for itself. Then horizontally adjacent >> pixels are more likely to be in the same cache line than vertically >> adjacent pixels, so processing images in scan lines tends to be a bit >> faster. > > Below is a variant of recursive algorithm that is approximately as > fast as your code (1.25x faster for filling solid rectangle, 1.43x > slower for filling snake shape). > The code is a bit long, but I hope that the logic is still obvious and > there is no need to prove correctness. [...] To me it looks like this recursive algorithm doesn't find all pixels that need coloring in some situations.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-20 10:56 +0200 |
| Message-ID | <20240320105647.000070ff@yahoo.com> |
| In reply to | #383764 |
On Tue, 19 Mar 2024 21:43:33 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Tue, 19 Mar 2024 11:57:53 +0000 > > Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: > > > >> No. Mine takes horizontal scan lines and extends them, then places > >> the pixels above and below in a queue to be considered as seeds for > >> the next scan line. (It's not mine, but I don't know who invented > >> it. It wasn't me.) > >> > >> Tim, now what does it do? Essentially it's the recursive fill > >> algorithm but with the data only on the stack instead of the call > >> and the data. And todo is actually a queue rather than a stack. > >> > >> Now why would it be slower? Probaby because you usually only hit a > >> pixel three times with mine - once below, once above, and once for > >> the scan line itself, while you consider it 5 times for Tim's - > >> once for each neighbour and once for itself. Then horizontally > >> adjacent pixels are more likely to be in the same cache line than > >> vertically adjacent pixels, so processing images in scan lines > >> tends to be a bit faster. > > > > Below is a variant of recursive algorithm that is approximately as > > fast as your code (1.25x faster for filling solid rectangle, 1.43x > > slower for filling snake shape). > > The code is a bit long, but I hope that the logic is still obvious > > and there is no need to prove correctness. [...] > > To me it looks like this recursive algorithm doesn't find all > pixels that need coloring in some situations. Yesterday night I had few doubts myself, but after further thinking came to conclusion that it it works in all situations.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-20 06:51 -0700 |
| Message-ID | <86frwlm2p3.fsf@linuxsc.com> |
| In reply to | #383772 |
Michael S <already5chosen@yahoo.com> writes: > On Tue, 19 Mar 2024 21:43:33 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: [...] >> To me it looks like this recursive algorithm doesn't find all >> pixels that need coloring in some situations. > > Yesterday night I had few doubts myself, but after further thinking > came to conclusion that it it works in all situations. Sorry, my bad. I did some experiments to convince myself the algorithm sometimes doesn't work, but it turns out the results showed a problem in the experiments rather than the algorithm. :/
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-19 19:18 +0200 |
| Message-ID | <20240319191859.00004bc8@yahoo.com> |
| In reply to | #383740 |
On Tue, 19 Mar 2024 11:57:53 +0000
Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> On 19/03/2024 11:18, Michael S wrote:
> > On Mon, 18 Mar 2024 22:42:14 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
> >>
> >> [...]
> >>
> >> Here is the refinement that uses a resizing rather than
> >> fixed-size buffer.
> >>
> >>
> >> typedef unsigned char Color;
> >> typedef unsigned int UI;
> >> typedef struct { UI x, y; } Point;
> >> typedef unsigned int Index;
> >>
> >> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
> >> Color );
> >>
> >> void
> >> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old,
> >> Color new ){ static const Point deltas[4] = { {1,0}, {0,1},
> >> {-1,0}, {0,-1}, }; UI k = 0;
> >> UI n = 17;
> >> Point *todo = malloc( n * sizeof *todo );
> >>
> >> if( todo && change_it( w, h, pixels, p0, old, new ) )
> >> todo[k++] = p0;
> >>
> >> while( k > 0 ){
> >> Index j = n-k;
> >> memmove( todo + j, todo, k * sizeof *todo );
> >> k = 0;
> >>
> >> while( j < n ){
> >> Point p = todo[ j++ ];
> >> for( Index i = 0; i < 4; i++ ){
> >> Point q = { p.x + deltas[i].x, p.y + deltas[i].y
> >> }; if( ! change_it( w, h, pixels, q, old, new ) )
> >> continue; todo[ k++ ] = q;
> >> }
> >>
> >> if( j-k < 3 ){
> >> Index new_n = n+n/4;
> >> Index new_j = new_n - (n-j);
> >> Point *t = realloc( todo, new_n * sizeof *t );
> >> if( !t ){ k = 0; break; }
> >> memmove( t + new_j, t + j, (n-j) * sizeof *t );
> >> todo = t, n = new_n, j = new_j;
> >> }
> >> }
> >> }
> >>
> >> free( todo );
> >> }
> >>
> >> _Bool
> >> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old,
> >> Color new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] !=
> >> old ) return 0; return pixels[p.x][p.y] = new, 1;
> >> }
> >
> > This variant is significantly slower than Malcolm's.
> > 2x slower for solid rectangle, 6x slower for snake shape.
> > Is it the same algorithm?
> >
>
> No. Mine takes horizontal scan lines and extends them, then places
> the pixels above and below in a queue to be considered as seeds for
> the next scan line. (It's not mine, but I don't know who invented it.
> It wasn't me.)
>
> Tim, now what does it do? Essentially it's the recursive fill
> algorithm but with the data only on the stack instead of the call and
> the data. And todo is actually a queue rather than a stack.
>
> Now why would it be slower? Probaby because you usually only hit a
> pixel three times with mine - once below, once above, and once for
> the scan line itself, whilst you consider it 5 times for Tim's - once
> for each neighbour and once for itself. Then horizontally adjacent
> pixels are more likely to be in the same cache line than vertically
> adjacent pixels, so processing images in scan lines tends to be a bit
> faster.
>
I did a little more investigation gradually modifying Tim's code for
improved performance without changing the basic principle of the
algorithm. Yes, micro-optimization. Yes, I said earlier that doing so
in c.l.c it is bad sportsmanship. So what? I never claimed to be an
ideal sportsman.
The point is that after optimizations it's actually faster than the
best implementations of original recursive algorithm, including
implementation that uses explicit stack and is quite economical in its
memory consumption. Tim's algorithm is 8 times less economical (8 bytes
per saved node vs 1 byte in explicit stack) and nevertheless almost
twice faster for both shapes that I was testing.
So far, this algorithm is fastest among all "local" algorithms that I
tried. By "local" I mean algorithms that don't try to recolor more than
one pixel at time.
"Non-local" algorithms i.e. yours and my recursive algorithm that
recolors St. George cross, are somewhat faster, but I suspect that
it's because all shapes that I use for testing have either long
columns or long rows or both.
The nice thing about Tim's method is that we can expect that
performance depends on number of recolored pixels and almost nothing
else.
The second nice thing is that it is easy to understand. Not as easy as
original recursive method, but easier than the rest of them.
If you or somebody else is interested, here is [micro]optimized variant:
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
typedef unsigned char Color;
typedef int UI;
typedef struct { UI x, y; } Point;
static inline
Point* circularIncr(Point* p, Point* beg, Point* end) {
return p + 1 == end ? beg : p + 1;
}
static inline
Point mk_point(int x, int y) {
Point pt={x,y};
return pt;
}
int floodfill_r(
Color *pixels,
int w, int h,
int pt0_x, int pt0_y,
Color old, Color new)
{
if (pt0_x < 0 || pt0_x >= w || pt0_y < 0 || pt0_y >= h)
return 0;
if (pixels[pt0_y*w+pt0_x] != old)
return 0;
pixels[pt0_y*w+pt0_x] = new;
const ptrdiff_t INITIAL_TODO_SIZE = 125;
Point *todo = malloc( (INITIAL_TODO_SIZE+3) * sizeof *todo );
// +3 is extra size to assist wrap-around of wr
if (!todo)
return -1;
Point* todo_end = &todo[INITIAL_TODO_SIZE];
todo[0] = mk_point(pt0_x, pt0_y);
Point* wr = &todo[1];
Point* rd = todo;
ptrdiff_t free_space = INITIAL_TODO_SIZE - 1;
do {
Point pt = *rd;
rd = circularIncr(rd, todo, todo_end);
Point* prev_wr = wr;
if (pt.x > 0 && pixels[pt.y*w+pt.x-1] == old) {
pixels[pt.y*w+pt.x-1] = new;
*wr++ = mk_point(pt.x-1, pt.y);
}
if (pt.y > 0 && pixels[pt.y*w+pt.x-w] == old) {
pixels[pt.y*w+pt.x-w] = new;
*wr++ = mk_point(pt.x, pt.y-1);
}
if (pt.x+1 < w && pixels[pt.y*w+pt.x+1] == old) {
pixels[pt.y*w+pt.x+1] = new;
*wr++ = mk_point(pt.x+1, pt.y);
}
if (pt.y+1 < h && pixels[pt.y*w+pt.x+w] == old) {
pixels[pt.y*w+pt.x+w] = new;
*wr++ = mk_point(pt.x, pt.y+1);
}
free_space += 1 - (wr - prev_wr);
if (wr >= todo_end) {
memcpy(todo, todo_end, (wr - todo_end)*sizeof(*wr));
wr += todo - todo_end;
}
if (free_space < 4) {
ptrdiff_t rdi = rd-todo;
ptrdiff_t wri = wr-todo;
ptrdiff_t sz = todo_end - todo;
ptrdiff_t incr = sz/4;
Point* new_todo = realloc(todo, (sz+incr+3) * sizeof *todo );
// +3 is extra size to assist wrap-around of wr
if(!new_todo) {
free(todo);
return -1;
}
free_space += incr;
rd = &new_todo[rdi];
wr = &new_todo[wri];
todo = new_todo;
todo_end = &todo[sz+incr];
if (rd >= wr) {
memmove(&rd[incr], rd, (sz-rdi) * sizeof *todo );
rd = &rd[incr];
}
}
} while (rd != wr);
free( todo );
return 1;
}
[toc] | [prev] | [next] | [standalone]
| From | fir <fir@grunge.pl> |
|---|---|
| Date | 2024-03-20 09:27 +0100 |
| Message-ID | <ute6m3$2fah4$1@i2pn2.org> |
| In reply to | #383747 |
Michael S wrote:
> On Tue, 19 Mar 2024 11:57:53 +0000
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
>
>> On 19/03/2024 11:18, Michael S wrote:
>>> On Mon, 18 Mar 2024 22:42:14 -0700
>>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>>>
>>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes:
>>>>
>>>> [...]
>>>>
>>>> Here is the refinement that uses a resizing rather than
>>>> fixed-size buffer.
>>>>
>>>>
>>>> typedef unsigned char Color;
>>>> typedef unsigned int UI;
>>>> typedef struct { UI x, y; } Point;
>>>> typedef unsigned int Index;
>>>>
>>>> static _Bool change_it( UI w, UI h, Color [w][h], Point, Color,
>>>> Color );
>>>>
>>>> void
>>>> fill_area( UI w, UI h, Color pixels[w][h], Point p0, Color old,
>>>> Color new ){ static const Point deltas[4] = { {1,0}, {0,1},
>>>> {-1,0}, {0,-1}, }; UI k = 0;
>>>> UI n = 17;
>>>> Point *todo = malloc( n * sizeof *todo );
>>>>
>>>> if( todo && change_it( w, h, pixels, p0, old, new ) )
>>>> todo[k++] = p0;
>>>>
>>>> while( k > 0 ){
>>>> Index j = n-k;
>>>> memmove( todo + j, todo, k * sizeof *todo );
>>>> k = 0;
>>>>
>>>> while( j < n ){
>>>> Point p = todo[ j++ ];
>>>> for( Index i = 0; i < 4; i++ ){
>>>> Point q = { p.x + deltas[i].x, p.y + deltas[i].y
>>>> }; if( ! change_it( w, h, pixels, q, old, new ) )
>>>> continue; todo[ k++ ] = q;
>>>> }
>>>>
>>>> if( j-k < 3 ){
>>>> Index new_n = n+n/4;
>>>> Index new_j = new_n - (n-j);
>>>> Point *t = realloc( todo, new_n * sizeof *t );
>>>> if( !t ){ k = 0; break; }
>>>> memmove( t + new_j, t + j, (n-j) * sizeof *t );
>>>> todo = t, n = new_n, j = new_j;
>>>> }
>>>> }
>>>> }
>>>>
>>>> free( todo );
>>>> }
>>>>
>>>> _Bool
>>>> change_it( UI w, UI h, Color pixels[w][h], Point p, Color old,
>>>> Color new ){ if( p.x >= w || p.y >= h || pixels[p.x][p.y] !=
>>>> old ) return 0; return pixels[p.x][p.y] = new, 1;
>>>> }
>>>
>>> This variant is significantly slower than Malcolm's.
>>> 2x slower for solid rectangle, 6x slower for snake shape.
>>> Is it the same algorithm?
>>>
>>
>> No. Mine takes horizontal scan lines and extends them, then places
>> the pixels above and below in a queue to be considered as seeds for
>> the next scan line. (It's not mine, but I don't know who invented it.
>> It wasn't me.)
>>
>> Tim, now what does it do? Essentially it's the recursive fill
>> algorithm but with the data only on the stack instead of the call and
>> the data. And todo is actually a queue rather than a stack.
>>
>> Now why would it be slower? Probaby because you usually only hit a
>> pixel three times with mine - once below, once above, and once for
>> the scan line itself, whilst you consider it 5 times for Tim's - once
>> for each neighbour and once for itself. Then horizontally adjacent
>> pixels are more likely to be in the same cache line than vertically
>> adjacent pixels, so processing images in scan lines tends to be a bit
>> faster.
>>
>
> I did a little more investigation gradually modifying Tim's code for
> improved performance without changing the basic principle of the
> algorithm. Yes, micro-optimization. Yes, I said earlier that doing so
> in c.l.c it is bad sportsmanship. So what? I never claimed to be an
> ideal sportsman.
> The point is that after optimizations it's actually faster than the
> best implementations of original recursive algorithm, including
> implementation that uses explicit stack and is quite economical in its
> memory consumption. Tim's algorithm is 8 times less economical (8 bytes
> per saved node vs 1 byte in explicit stack) and nevertheless almost
> twice faster for both shapes that I was testing.
> So far, this algorithm is fastest among all "local" algorithms that I
> tried. By "local" I mean algorithms that don't try to recolor more than
> one pixel at time.
> "Non-local" algorithms i.e. yours and my recursive algorithm that
> recolors St. George cross, are somewhat faster, but I suspect that
> it's because all shapes that I use for testing have either long
> columns or long rows or both.
> The nice thing about Tim's method is that we can expect that
> performance depends on number of recolored pixels and almost nothing
> else.
> The second nice thing is that it is easy to understand. Not as easy as
> original recursive method, but easier than the rest of them.
>
> If you or somebody else is interested, here is [micro]optimized variant:
>
>
> #include <stdlib.h>
> #include <stddef.h>
> #include <string.h>
>
>
> typedef unsigned char Color;
> typedef int UI;
> typedef struct { UI x, y; } Point;
>
> static inline
> Point* circularIncr(Point* p, Point* beg, Point* end) {
> return p + 1 == end ? beg : p + 1;
> }
>
> static inline
> Point mk_point(int x, int y) {
> Point pt={x,y};
> return pt;
> }
>
> int floodfill_r(
> Color *pixels,
> int w, int h,
> int pt0_x, int pt0_y,
> Color old, Color new)
> {
> if (pt0_x < 0 || pt0_x >= w || pt0_y < 0 || pt0_y >= h)
> return 0;
>
> if (pixels[pt0_y*w+pt0_x] != old)
> return 0;
>
> pixels[pt0_y*w+pt0_x] = new;
>
> const ptrdiff_t INITIAL_TODO_SIZE = 125;
> Point *todo = malloc( (INITIAL_TODO_SIZE+3) * sizeof *todo );
> // +3 is extra size to assist wrap-around of wr
> if (!todo)
> return -1;
> Point* todo_end = &todo[INITIAL_TODO_SIZE];
>
> todo[0] = mk_point(pt0_x, pt0_y);
> Point* wr = &todo[1];
> Point* rd = todo;
> ptrdiff_t free_space = INITIAL_TODO_SIZE - 1;
> do {
> Point pt = *rd;
> rd = circularIncr(rd, todo, todo_end);
> Point* prev_wr = wr;
> if (pt.x > 0 && pixels[pt.y*w+pt.x-1] == old) {
> pixels[pt.y*w+pt.x-1] = new;
> *wr++ = mk_point(pt.x-1, pt.y);
> }
> if (pt.y > 0 && pixels[pt.y*w+pt.x-w] == old) {
> pixels[pt.y*w+pt.x-w] = new;
> *wr++ = mk_point(pt.x, pt.y-1);
> }
> if (pt.x+1 < w && pixels[pt.y*w+pt.x+1] == old) {
> pixels[pt.y*w+pt.x+1] = new;
> *wr++ = mk_point(pt.x+1, pt.y);
> }
> if (pt.y+1 < h && pixels[pt.y*w+pt.x+w] == old) {
> pixels[pt.y*w+pt.x+w] = new;
> *wr++ = mk_point(pt.x, pt.y+1);
> }
>
> free_space += 1 - (wr - prev_wr);
> if (wr >= todo_end) {
> memcpy(todo, todo_end, (wr - todo_end)*sizeof(*wr));
> wr += todo - todo_end;
> }
>
> if (free_space < 4) {
> ptrdiff_t rdi = rd-todo;
> ptrdiff_t wri = wr-todo;
> ptrdiff_t sz = todo_end - todo;
> ptrdiff_t incr = sz/4;
> Point* new_todo = realloc(todo, (sz+incr+3) * sizeof *todo );
> // +3 is extra size to assist wrap-around of wr
> if(!new_todo) {
> free(todo);
> return -1;
> }
> free_space += incr;
> rd = &new_todo[rdi];
> wr = &new_todo[wri];
> todo = new_todo;
> todo_end = &todo[sz+incr];
> if (rd >= wr) {
> memmove(&rd[incr], rd, (sz-rdi) * sizeof *todo );
> rd = &rd[incr];
> }
> }
> } while (rd != wr);
>
> free( todo );
> return 1;
> }
>
>
>
if i would write it non recursive it probably would be something like that
[1] (if in static table based simpler way, generally
in last years i prefer using reallock based resizable
ones so i would need yet revrite)
[2] not tested but it is draft of that code as i would attempt to write it
(come like short names so would change "list_of_pixels"
into "pixels" etc)
const int list_of_pixels_max = 10*1000*1000;
strauct {int x, y;} list_of_pixels[list_of_pixels_max];
int list_of_pixels_top = 0;
int list_of_pixels_bot = 0; //pointer to element to consume
inline void AddPixelToList(int x, int y)
{
list_of_pixels[list_of_pixels_top].x = x;
list_of_pixels[list_of_pixels_top].y = y;
list_of_pixels_top++;
// if(list_of_pixels_top>=list_of_pixels_max) ERROR_EXIT("overflow in
list of pixels")
}
int color_to_replace = 0;
int replacing_color = 0;
inline void RecolorizePixelAndSpawnNewPixelArea(int x, int y)
{
if(!IsInFrame(x,y)) return;
int color_here = GetPixelUnsafe(x,y);
if(color_here==color_to_replace)
{
StePixelUnsafe(x,y, replacement_color);
AddPixelToList( x+1, y);
AddPixelToList( x-1, y);
AddPixelToList( x, y+1);
AddPixelToList( x, y-1);
}
}
void RecolorizePixelArea(int x, int y, int color_to_replace_, int
replacing_color_)
{
color_to_replace = color_to_replace_;
replacing_color = replacing_color_;
list_of_pixels_top = 0;
list_of_pixels_bot = 0;
RecolorizePixelAndSpawnNewPixelArea(x,y);
while(list_of_pixels_bot<list_of_pixels_top)
{
RecolorizePixelAndSpawnNewPixelArea(list_of_pixels[list_of_pixels_bot].x,list_of_pixels[list_of_pixels_bot].y);
list_of_pixels_bot++;
}
}
[toc] | [prev] | [next] | [standalone]
| From | fir <fir@grunge.pl> |
|---|---|
| Date | 2024-03-20 09:39 +0100 |
| Message-ID | <ute7cf$2fbbm$1@i2pn2.org> |
| In reply to | #383767 |
fir wrote:
>
> inline void RecolorizePixelAndSpawnNewPixelArea(int x, int y)
> {
as i use word area in doble mining here it should be renamed like
inline void RecolorizePixelAndSpawnNewPixelImmediateVicinity(int x, int y)
(generally i use almost such log function names in my codes but not
write comments at all
than as everything is then self commenting imo..with variable names i
use shorter, but sometimes it seem that some can also be a bit longel
like here list_of_pixels_bot etc)
[toc] | [prev] | [next] | [standalone]
| From | fir <fir@grunge.pl> |
|---|---|
| Date | 2024-03-20 09:51 +0100 |
| Message-ID | <ute81n$2fc8p$1@i2pn2.org> |
| In reply to | #383767 |
fir wrote:
>
> RecolorizePixelAndSpawnNewPixelArea(x,y);
>
> while(list_of_pixels_bot<list_of_pixels_top)
> {
>
> RecolorizePixelAndSpawnNewPixelArea(list_of_pixels[list_of_pixels_bot].x,list_of_pixels[list_of_pixels_bot].y);
>
> list_of_pixels_bot++;
> }
>
> }
>
>
>
maybe this is an example os case when do {} while() would work better
than while,
do {
RecolorizePixelAndSpawnNewPixelImmediateVicinity(list_of_pixels[list_of_pixels_bot].x,list_of_pixels[list_of_pixels_bot].y);
} while(list_of_pixels_bot<list_of_pixels_top)
but that would be need to check as such loops are confusing
if so i think it is somewhat general sheme
do {something();} while(bot<top)
of rewriting recursion probably
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-20 07:27 -0700 |
| Message-ID | <86bk79m10l.fsf@linuxsc.com> |
| In reply to | #383747 |
Michael S <already5chosen@yahoo.com> writes: > On Tue, 19 Mar 2024 11:57:53 +0000 > Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: > >> On 19/03/2024 11:18, Michael S wrote: >> >>> On Mon, 18 Mar 2024 22:42:14 -0700 >>> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >>> >>>> Tim Rentsch <tr.17687@z991.linuxsc.com> writes: >>>> >>>> Here is the refinement that uses a resizing rather than >>>> fixed-size buffer. [...] > I did a little more investigation gradually modifying Tim's code > for improved performance without changing the basic principle of > the algorithm. [...] I appreciate your doing this. I developed independently a couple of versions along similar lines. > So far, this algorithm is fastest among all "local" algorithms > that I tried. By "local" I mean algorithms that don't try to > recolor more than one pixel at time. > > "Non-local" algorithms i.e. yours and my recursive algorithm that > recolors St. George cross, are somewhat faster, [...]. I was confused by this statement at first but now I see that "yours" refers to Malcolm's algorithm. > The nice thing about Tim's method is that we can expect that > performance depends on number of recolored pixels and almost > nothing else. One aspect that I consider a significant plus is my code never does poorly. Certainly it isn't the fastest in all cases, but it's never abysmally slow. > The second nice thing is that it is easy to understand. Not as > easy as original recursive method, but easier than the rest of > them. > > If you or somebody else is interested, here is [micro]optimized > variant: [...] Good show. I will try to get my latest version posted soon.
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-24 20:27 +0300 |
| Message-ID | <20240324202758.00001b75@yahoo.com> |
| In reply to | #383788 |
On Wed, 20 Mar 2024 07:27:38 -0700 Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > Michael S <already5chosen@yahoo.com> writes: > > > On Tue, 19 Mar 2024 11:57:53 +0000 > > Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: > > > > > The nice thing about Tim's method is that we can expect that > > performance depends on number of recolored pixels and almost > > nothing else. > > One aspect that I consider a significant plus is my code never > does poorly. Certainly it isn't the fastest in all cases, but > it's never abysmally slow. > To be fair, none of presented algorithms is abysmally slow. When compared by number of visited points, they all appear to be within factor of 2 or 2.5 of each other. Some of them for some patterns could be 10-15 times slower than others, but it does not happen for all patterns and when it happens it's because of problematic implementation rather because of differences in algorithms. Even original naive recursive algorithm is not too slow when implemented in optimized asm - 2.2x slower than the fastest for solid square shape and closer than that for other shapes. The big difference between algorithms is not a speed, but amount of auxiliary memory used in the worst case. Your algorithm appears to be the best in that department, Malcolm's algorithm it's also quite good and all others (plain recursion, stacks, my deferred stack, all my cross variants, lines-oriented recursion of : Peter 'Shaggy' Haywood) are a lot worse. But even by that metric, the difference between different implementations of the same algorithm is often much bigger than difference between algorithms. For example, solid 200x200 image with starting point in the corner recolored by code presented in first Malcolm's post (not his own algorithm, but recursive algorithm that he presented as a reference point) on x86-64/gcc consumes 5,094,784 bytes of stack. After small modification (all non-changing parameters aggregated in structure and passed by reference) the footprint falls to 2,547,328 B. Coding the same algorithm (well, almost the same) in asm reduces it to 32,0000 B. Coding it with explicit stack cuts it to 40,000 B. Now I didn't actually coded it, but I know how to compress explicit stack down to 2 bits per level of recursion. If implemented, it would be 10,000B, i.e. comparable with much more economical algorithm of Malcolm and 512x smaller than original implementation of [well, almost] the same algorithm!
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-24 13:26 -0700 |
| Message-ID | <86frwfjs0n.fsf@linuxsc.com> |
| In reply to | #383963 |
Michael S <already5chosen@yahoo.com> writes: > On Wed, 20 Mar 2024 07:27:38 -0700 > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: > >> Michael S <already5chosen@yahoo.com> writes: >> >>> On Tue, 19 Mar 2024 11:57:53 +0000 >>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: >>> [...] >>> The nice thing about Tim's method is that we can expect that >>> performance depends on number of recolored pixels and almost >>> nothing else. >> >> One aspect that I consider a significant plus is my code never >> does poorly. Certainly it isn't the fastest in all cases, but >> it's never abysmally slow. > > To be fair, none of presented algorithms is abysmally slow. When > compared by number of visited points, they all appear to be within > factor of 2 or 2.5 of each other. Certainly "abysmally slow" is subjective, but working in a large pixel field, filling the whole field starting at the center, Malcolm's code runs slower than my unoptimized code by a factor of 10 (and a tad slower than that compared to my optimized code). > Some of them for some patterns could be 10-15 times slower than > others, but it does not happen for all patterns and when it > happens it's because of problematic implementation rather because > of differences in algorithms. In the case of Malcolm's code I think it's the algorithm, because it doesn't scale linearly. Malcolm's code runs faster than mine for small colorings, but slows down dramatically as the image being colored gets bigger. > The big difference between algorithms is not a speed, but amount of > auxiliary memory used in the worst case. Your algorithm appears to be > the best in that department, [...] Yes, my unoptimized algorithm was designed to use as little memory as possible. The optimized version traded space for speed: it runs a little bit faster but incurs a non-trivial cost in terms of space used. I think it's still not too bad, an upper bound of a small multiple of N for an NxN pixel field. > But even by that metric, the difference between different > implementations of the same algorithm is often much bigger than > difference between algorithms. If I am not mistaken the original naive recursive algorithm has a space cost that is O( N**2 ) for an NxN pixel field. The big-O difference swamps everything else, just like the big-O difference in runtime does for that metric. > For example, solid 200x200 image with starting point in the corner > [...] On small pixel fields almost any algorithm is probably not too bad. These days any serious algorithm should scale well up to at least 4K by 4K, and tested up to at least 16K x 16K. Tricks that make some things faster for small images sometimes fall on their face when confronted with a larger image. My code isn't likely to win many races on small images, but on large images I expect it will always be competitive even if it doesn't finish in first place.
[toc] | [prev] | [next] | [standalone]
| From | "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> |
|---|---|
| Date | 2024-03-24 14:26 -0700 |
| Message-ID | <utq5qt$jldo$1@dont-email.me> |
| In reply to | #383971 |
On 3/24/2024 1:26 PM, Tim Rentsch wrote: > Michael S <already5chosen@yahoo.com> writes: > >> On Wed, 20 Mar 2024 07:27:38 -0700 >> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote: >> >>> Michael S <already5chosen@yahoo.com> writes: >>> >>>> On Tue, 19 Mar 2024 11:57:53 +0000 >>>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote: >>>> [...] >>>> The nice thing about Tim's method is that we can expect that >>>> performance depends on number of recolored pixels and almost >>>> nothing else. >>> >>> One aspect that I consider a significant plus is my code never >>> does poorly. Certainly it isn't the fastest in all cases, but >>> it's never abysmally slow. >> >> To be fair, none of presented algorithms is abysmally slow. When >> compared by number of visited points, they all appear to be within >> factor of 2 or 2.5 of each other. > > Certainly "abysmally slow" is subjective, but working in a large > pixel field, filling the whole field starting at the center, > Malcolm's code runs slower than my unoptimized code by a factor of > 10 (and a tad slower than that compared to my optimized code). > >> Some of them for some patterns could be 10-15 times slower than >> others, but it does not happen for all patterns and when it >> happens it's because of problematic implementation rather because >> of differences in algorithms. > > In the case of Malcolm's code I think it's the algorithm, because > it doesn't scale linearly. Malcolm's code runs faster than mine > for small colorings, but slows down dramatically as the image > being colored gets bigger. > >> The big difference between algorithms is not a speed, but amount of >> auxiliary memory used in the worst case. Your algorithm appears to be >> the best in that department, [...] > > Yes, my unoptimized algorithm was designed to use as little > memory as possible. The optimized version traded space for > speed: it runs a little bit faster but incurs a non-trivial cost > in terms of space used. I think it's still not too bad, an upper > bound of a small multiple of N for an NxN pixel field. > >> But even by that metric, the difference between different >> implementations of the same algorithm is often much bigger than >> difference between algorithms. > > If I am not mistaken the original naive recursive algorithm has a > space cost that is O( N**2 ) for an NxN pixel field. The big-O > difference swamps everything else, just like the big-O difference > in runtime does for that metric. > > >> For example, solid 200x200 image with starting point in the corner >> [...] > > On small pixel fields almost any algorithm is probably not too > bad. These days any serious algorithm should scale well up > to at least 4K by 4K, and tested up to at least 16K x 16K. > Tricks that make some things faster for small images sometimes > fall on their face when confronted with a larger image. My code > isn't likely to win many races on small images, but on large > images I expect it will always be competitive even if it doesn't > finish in first place. This might be relevant: https://developer.download.nvidia.com/video/gputechconf/gtc/2019/presentation/s9111-a-new-direct-connected-component-labeling-and-analysis-algorithm-for-gpus.pdf
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-25 01:28 +0300 |
| Message-ID | <20240325012844.0000685b@yahoo.com> |
| In reply to | #383971 |
On Sun, 24 Mar 2024 13:26:16 -0700
Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> Michael S <already5chosen@yahoo.com> writes:
>
> > On Wed, 20 Mar 2024 07:27:38 -0700
> > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> >
> >> Michael S <already5chosen@yahoo.com> writes:
> >>
> >>> On Tue, 19 Mar 2024 11:57:53 +0000
> >>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> >>> [...]
> >>> The nice thing about Tim's method is that we can expect that
> >>> performance depends on number of recolored pixels and almost
> >>> nothing else.
> >>
> >> One aspect that I consider a significant plus is my code never
> >> does poorly. Certainly it isn't the fastest in all cases, but
> >> it's never abysmally slow.
> >
> > To be fair, none of presented algorithms is abysmally slow. When
> > compared by number of visited points, they all appear to be within
> > factor of 2 or 2.5 of each other.
>
> Certainly "abysmally slow" is subjective, but working in a large
> pixel field, filling the whole field starting at the center,
> Malcolm's code runs slower than my unoptimized code by a factor of
> 10 (and a tad slower than that compared to my optimized code).
>
> > Some of them for some patterns could be 10-15 times slower than
> > others, but it does not happen for all patterns and when it
> > happens it's because of problematic implementation rather because
> > of differences in algorithms.
>
> In the case of Malcolm's code I think it's the algorithm, because
> it doesn't scale linearly. Malcolm's code runs faster than mine
> for small colorings, but slows down dramatically as the image
> being colored gets bigger.
>
> > The big difference between algorithms is not a speed, but amount of
> > auxiliary memory used in the worst case. Your algorithm appears to
> > be the best in that department, [...]
>
> Yes, my unoptimized algorithm was designed to use as little
> memory as possible. The optimized version traded space for
> speed: it runs a little bit faster but incurs a non-trivial cost
> in terms of space used. I think it's still not too bad, an upper
> bound of a small multiple of N for an NxN pixel field.
>
> > But even by that metric, the difference between different
> > implementations of the same algorithm is often much bigger than
> > difference between algorithms.
>
> If I am not mistaken the original naive recursive algorithm has a
> space cost that is O( N**2 ) for an NxN pixel field. The big-O
> difference swamps everything else, just like the big-O difference
> in runtime does for that metric.
>
>
> > For example, solid 200x200 image with starting point in the corner
> > [...]
>
> On small pixel fields almost any algorithm is probably not too
> bad. These days any serious algorithm should scale well up
> to at least 4K by 4K, and tested up to at least 16K x 16K.
> Tricks that make some things faster for small images sometimes
> fall on their face when confronted with a larger image. My code
> isn't likely to win many races on small images, but on large
> images I expect it will always be competitive even if it doesn't
> finish in first place.
You are right. At 1920*1080 except for few special patterns, your
code is faster than Malcolm's by factor of 1.5x to 1.8. Same for 4K.
Auxiliary memory arrays of Malcolm are still quite small at these image
sizes, but speed suffers.
I wonder if it is a problem of algorithm or of implementation. Since I
still didn't figure out his idea, I can't improve his implementation in
order check it.
One thing that I were not expecting at this bigger pictures, is good
performance of simple recursive algorithm. Of course, not of original
form of it, but of variation with explicit stack.
For many shapes it has quite large memory footprint and despite that it
is not slow. Probably the stack has very good locality of reference.
Here is the code:
#include <stdlib.h>
#include <stddef.h>
typedef unsigned char Color;
int floodfill4(
Color *image,
int width,
int height,
int x0,
int y0,
Color old,
Color new)
{
if (width <= 0 || height <= 0)
return 0;
if (x0 < 0 || x0 >= width || y0 < 0 || y0 >= height)
return 0;
const size_t w = width;
Color* image_end = &image[w*height];
size_t x = x0;
Color* row = &image[w*y0];
if (row[x] != old)
return 0;
const ptrdiff_t INITIAL_STACK_SZ = 256;
unsigned char* stack = malloc(INITIAL_STACK_SZ*sizeof(*stack));
if (!stack)
return -1;
unsigned char* sp = stack;
unsigned char* end_stack = &stack[INITIAL_STACK_SZ];
enum { ST_LEFT, ST_RIGHT, ST_UP, ST_DOWN, ST_BEG };
recursive_call:
row[x] = new;
if (sp==end_stack) {
ptrdiff_t size = sp - stack;
ptrdiff_t new_size = size+size/2;
unsigned char* new_stack = realloc(stack, new_size *
sizeof(*stack)); if (!new_stack) {
free(stack);
return -1;
}
stack = new_stack;
sp = &stack[size];
end_stack = &stack[new_size];
}
for (unsigned state = ST_BEG;;) {
switch (state) {
case ST_BEG:
++x;
if (x != width) {
if (row[x] == old) {
*sp++ = ST_RIGHT; goto recursive_call; // recursive call
}
}
case ST_RIGHT:
--x;
if (x > 0) {
--x;
if (row[x] == old) {
*sp++ = ST_LEFT; goto recursive_call; // recursive call
}
case ST_LEFT:
++x;
}
if (row != image) {
row -= w;
if (row[x] == old) {
*sp++ = ST_UP; goto recursive_call; // recursive call
}
case ST_UP:
row += w;
}
row += w;
if (row != image_end) {
if (row[x] == old) {
*sp++ = ST_DOWN; goto recursive_call; // recursive call
}
case ST_DOWN:
}
row -= w;
break;
}
if (sp == stack)
break;
state = *--sp; // pop stack (back to caller)
}
free(stack);
return 1; // done
}
[toc] | [prev] | [next] | [standalone]
| From | Michael S <already5chosen@yahoo.com> |
|---|---|
| Date | 2024-03-26 17:52 +0200 |
| Message-ID | <20240326185218.00005397@yahoo.com> |
| In reply to | #383978 |
On Mon, 25 Mar 2024 01:28:44 +0300
Michael S <already5chosen@yahoo.com> wrote:
> On Sun, 24 Mar 2024 13:26:16 -0700
> Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
>
> > Michael S <already5chosen@yahoo.com> writes:
> >
> > > On Wed, 20 Mar 2024 07:27:38 -0700
> > > Tim Rentsch <tr.17687@z991.linuxsc.com> wrote:
> > >
> > >> Michael S <already5chosen@yahoo.com> writes:
> > >>
> > >>> On Tue, 19 Mar 2024 11:57:53 +0000
> > >>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> wrote:
> > >>> [...]
> > >>> The nice thing about Tim's method is that we can expect that
> > >>> performance depends on number of recolored pixels and almost
> > >>> nothing else.
> > >>
> > >> One aspect that I consider a significant plus is my code never
> > >> does poorly. Certainly it isn't the fastest in all cases, but
> > >> it's never abysmally slow.
> > >
> > > To be fair, none of presented algorithms is abysmally slow. When
> > > compared by number of visited points, they all appear to be within
> > > factor of 2 or 2.5 of each other.
> >
> > Certainly "abysmally slow" is subjective, but working in a large
> > pixel field, filling the whole field starting at the center,
> > Malcolm's code runs slower than my unoptimized code by a factor of
> > 10 (and a tad slower than that compared to my optimized code).
> >
> > > Some of them for some patterns could be 10-15 times slower than
> > > others, but it does not happen for all patterns and when it
> > > happens it's because of problematic implementation rather because
> > > of differences in algorithms.
> >
> > In the case of Malcolm's code I think it's the algorithm, because
> > it doesn't scale linearly. Malcolm's code runs faster than mine
> > for small colorings, but slows down dramatically as the image
> > being colored gets bigger.
> >
> > > The big difference between algorithms is not a speed, but amount
> > > of auxiliary memory used in the worst case. Your algorithm
> > > appears to be the best in that department, [...]
> >
> > Yes, my unoptimized algorithm was designed to use as little
> > memory as possible. The optimized version traded space for
> > speed: it runs a little bit faster but incurs a non-trivial cost
> > in terms of space used. I think it's still not too bad, an upper
> > bound of a small multiple of N for an NxN pixel field.
> >
> > > But even by that metric, the difference between different
> > > implementations of the same algorithm is often much bigger than
> > > difference between algorithms.
> >
> > If I am not mistaken the original naive recursive algorithm has a
> > space cost that is O( N**2 ) for an NxN pixel field. The big-O
> > difference swamps everything else, just like the big-O difference
> > in runtime does for that metric.
> >
> >
> > > For example, solid 200x200 image with starting point in the corner
> > > [...]
> >
> > On small pixel fields almost any algorithm is probably not too
> > bad. These days any serious algorithm should scale well up
> > to at least 4K by 4K, and tested up to at least 16K x 16K.
> > Tricks that make some things faster for small images sometimes
> > fall on their face when confronted with a larger image. My code
> > isn't likely to win many races on small images, but on large
> > images I expect it will always be competitive even if it doesn't
> > finish in first place.
>
> You are right. At 1920*1080 except for few special patterns, your
> code is faster than Malcolm's by factor of 1.5x to 1.8. Same for 4K.
> Auxiliary memory arrays of Malcolm are still quite small at these
> image sizes, but speed suffers.
> I wonder if it is a problem of algorithm or of implementation. Since I
> still didn't figure out his idea, I can't improve his implementation
> in order check it.
>
> One thing that I were not expecting at this bigger pictures, is good
> performance of simple recursive algorithm. Of course, not of original
> form of it, but of variation with explicit stack.
> For many shapes it has quite large memory footprint and despite that
> it is not slow. Probably the stack has very good locality of
> reference.
>
> Here is the code:
> <snip>
The most robust code that I found so far that performs well both with
small pictures and with large and huge, is a variation on the same
theme of explicit stack, may be, more properly called trace back.
It operates on 2x2 squares instead of individual pixels.
The worst case auxiliary memory footprint of this variant is rather big,
up to picture_size/4 bytes. The code is *not* simple, but complexity
appears to be necessary for robust performance with various shapes and
sizes.
Todo queue based variants have very low memory footprint and perform
well for as long as recolored shape fits in the fast levels of
cache hierarchy, but suffer sharp slowdown when shape grows beyond
that. It seems, the problem of this algorithms is that the front
of recoloring is interleaved and focus of processing jumps randomly
across the front which leads to poor locality and to trashing of the
cache. May be, for huge pictures some sort of priority queue will
perform better than simple FIFO ? May be, implemented as binary heap?
https://en.wikipedia.org/wiki/Binary_heap
Thought are interesting, but it's unlikely that it could lead to faster
code than one presented below.
#include <stdlib.h>
#include <stddef.h>
typedef unsigned char Color;
static __inline
unsigned check_column(Color *row, size_t x, size_t w, Color *end_image,
Color old)
{
unsigned b = row[x+0] == old ? 1<<0 : 0;
if (row+w != end_image && row[x+w] == old)
b |= 1 << 2;
return b;
}
static __inline
unsigned check_row(Color *row, size_t x, size_t w, Color old)
{
unsigned b = row[x+0] == old ? 1<<0 : 0;
if (x+1 != w && row[x+1] == old)
b |= 1 << 1;
return b;
}
int floodfill4(
Color *image,
int width,
int height,
int x0,
int y0,
Color old,
Color new)
{
if (width <= 0 || height <= 0)
return 0;
if (x0 < 0 || x0 >= width || y0 < 0 || y0 >= height)
return 0;
const size_t w = width;
size_t col0 = x0;
Color* row0 = &image[w * y0];
if (row0[col0] != old)
return 0;
int offs = 0;
if (y0 & 1) {
row0 -= w;
offs = 2;
}
if (col0 & 1) {
col0 -= 1;
offs |= 1;
}
Color* end_image = &image[w * height];
const ptrdiff_t INITIAL_STACK_SZ = 256;
unsigned char* stack = malloc(INITIAL_STACK_SZ*sizeof(*stack));
if (!stack)
return -1;
unsigned char* sp = stack;
unsigned char* end_stack = &stack[INITIAL_STACK_SZ];
enum {
// state
ST_LEFT, ST_RIGHT, ST_UP, ST_DOWN,
ST_BEG,
STATE_BITS = 3,
// mask
MSK_B00 = 1 << 2, MSK_B01 = 1 << 3,
MSK_B10 = 1 << 4, MSK_B11 = 1 << 5,
MSK_B0x = MSK_B00 | MSK_B01,
MSK_B1x = MSK_B10 | MSK_B11,
MSK_Bx0 = MSK_B00 | MSK_B10,
MSK_Bx1 = MSK_B01 | MSK_B11,
MSK_Bxx = MSK_Bx0 | MSK_Bx1,
MSK_BITS = MSK_Bxx,
// from
FROM_LEFT = 0 << 6,
FROM_RIGHT = 1 << 6,
FROM_UP = 2 << 6,
FROM_DOWN = 3 << 6,
FROM_BITS = 3 << 6,
};
unsigned bit_mask0 = check_row(row0, col0, w, old)*MSK_B00;
if (row0+w != end_image)
bit_mask0 |= check_row(row0+w, col0, w, old)*MSK_B10;
static const unsigned char kill_diag_tab[4][2] = {
{MSK_B01 | MSK_B10, ~MSK_B11},
{MSK_B00 | MSK_B11, ~MSK_B10},
{MSK_B00 | MSK_B11, ~MSK_B01},
{MSK_B01 | MSK_B10, ~MSK_B00},
};
if ((bit_mask0 & kill_diag_tab[offs][0])==0)
bit_mask0 &= kill_diag_tab[offs][1];
for (int rep = 0; rep < 2; ++rep) {
unsigned bit_mask = bit_mask0;
Color* row = row0;
size_t x = col0;
unsigned from = rep == 0 ? FROM_DOWN : FROM_LEFT;
recursive_call:
if (bit_mask & MSK_B00) row[x+0] = new;
if (bit_mask & MSK_B01) row[x+1] = new;
if (bit_mask & MSK_B10) row[x+w+0] = new;
if (bit_mask & MSK_B11) row[x+w+1] = new;
if (sp==end_stack) {
ptrdiff_t size = sp - stack;
ptrdiff_t new_size = size+size/2;
unsigned char* new_stack = realloc(stack, new_size *
sizeof(*stack));
if (!new_stack) {
free(stack);
return -1;
}
stack = new_stack;
sp = &stack[size];
end_stack = &stack[new_size];
}
for (unsigned state = ST_BEG;;) {
switch (state) {
case ST_BEG:
if (from != FROM_RIGHT && bit_mask & MSK_Bx1) { // look right
x += 2;
if (x != w) {
unsigned bx0 = check_column(row, x, w, end_image, old);
if (bx0 & (bit_mask/MSK_B01)) {
// recursive call
*sp++ = bit_mask | from | ST_RIGHT;
bit_mask = bx0*MSK_B00;
x += 1;
if (x != w) {
unsigned bx1 = check_column(row, x, w, end_image, old);
if (bx0 & bx1)
bit_mask |= bx1*MSK_B01;
}
x -= 1;
from = FROM_LEFT;
goto recursive_call;
}
}
case ST_RIGHT:
x -= 2;
}
if (from != FROM_LEFT && bit_mask & MSK_Bx0) { // look left
if (x > 0) {
unsigned bx1 = check_column(row, x-1, w, end_image, old);
if (bx1 & (bit_mask/MSK_B00)) {
// recursive call
*sp++ = bit_mask | from | ST_LEFT;
bit_mask = bx1*MSK_B01;
x -= 2;
unsigned bx0 = check_column(row, x, w, end_image, old);
if (bx0 & bx1)
bit_mask |= bx0*MSK_B00;
from = FROM_RIGHT;
goto recursive_call;
case ST_LEFT:
x += 2;
}
}
}
if (from != FROM_UP && bit_mask & MSK_B0x) { // look up
if (row != image) {
row -= w;
unsigned b1x = check_row(row, x, w, old);
row -= w;
if (b1x & (bit_mask/MSK_B00)) {
// recursive call
*sp++ = bit_mask | from | ST_UP;
bit_mask = b1x*MSK_B10;
unsigned b0x = check_row(row, x, w, old);
if (b0x & b1x)
bit_mask |= b0x*MSK_B00;
from = FROM_DOWN;
goto recursive_call;
case ST_UP:
}
row += w*2;
}
}
if (from != FROM_DOWN && bit_mask & MSK_B1x) { // look down
row += w*2;
if (row != end_image) {
unsigned b0x = check_row(row, x, w, old);
if (b0x & (bit_mask/MSK_B10)) {
// recursive call
*sp++ = bit_mask | from | ST_DOWN;
bit_mask = b0x*MSK_B00;
row += w;
if (row != end_image) {
unsigned b1x = check_row(row, x, w, old);
if (b0x & b1x)
bit_mask |= b1x*MSK_B10;
}
row -= w;
from = FROM_UP;
goto recursive_call;
}
}
case ST_DOWN:
row -= w*2;
}
break;
}
if (sp == stack)
break;
unsigned stack_val = *--sp; // pop stack (back to caller)
state = stack_val & STATE_BITS;
bit_mask = stack_val & MSK_BITS;
from = stack_val & FROM_BITS;
}
}
free(stack);
return 1; // done
}
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2024-03-30 00:54 -0700 |
| Message-ID | <86ttkoi28k.fsf@linuxsc.com> |
| In reply to | #384030 |
Michael S <already5chosen@yahoo.com> writes: [...] > The most robust code that I found so far that performs well both > with small pictures and with large and huge, is a variation on the > same theme of explicit stack, may be, more properly called trace > back. It operates on 2x2 squares instead of individual pixels. > > The worst case auxiliary memory footprint of this variant is rather > big, up to picture_size/4 bytes. The code is *not* simple, but > complexity appears to be necessary for robust performance with > various shapes and sizes. > > [...] I took a cursory look just now, after reading your other later posting. I think I have a general sense, especially in conjunction with the explanatory comments. I'm still hoping to find a method that is both fast and has good memory use, which is to say O(N) for an NxN pixel field. Something that would help is to have a library of test cases, by which I mean patterns to be colored, so that a set of methods could be tried, and timed, over all the patterns in the library. Do you have something like that? So far all my testing has been ad hoc. Incidentally, it looks like your code assumes X varies more rapidly than Y, so a "by row" order, whereas my code assumes Y varies more rapidly than X, a "by column" order. The difference doesn't matter as long as the pixel field is square and the test cases either are symmetric about the X == Y axis or duplicate a non-symmetric pattern about the X == Y axis. I would like to be able to run comparisons between different methods and get usable results without having to jump around because of different orientations. I'm not sure how to accommodate that.
[toc] | [prev] | [next] | [standalone]
Page 6 of 9 — ← Prev page 1 2 3 4 5 [6] 7 8 9 Next page →
Back to top | Article view | comp.lang.c
csiph-web