On Mon 23 Nov 2020 at 06:23:50 (+0100), Emanuel Berg wrote: > > I don't understand what you mean by "sensible" data. > > Your example > > > > ......... > > ...sss... > > ..skkks.. > > ..sssss.. > > ....ss... > > > > is a completely convex blob. Are we to understand that as > > a constraint? Or are re-entrant shaped loops allowed? What sort > > of re-entrants? > > I have described the intention using everyday language. > > Then I described the algorithm that would accomplish this. > > Finally, I provided this ascii art example. > > If that still isn't enough, well, you know what they say, it ain't > worth it explaining to someone who doesn't understand.
Fair enough, but I thought you were worth explaining it to, so here goes with some ascii art. I started with a larger image than yours at https://lists.debian.org/debian-user/2020/11/msg00496.html but using the same notation, and I carried out your algorithm at https://lists.debian.org/debian-user/2020/11/msg00494.html but showing my working by leaving arrows as the scan passed. The first pass is simple, with 'd' turning into →. In the second pass, I've only shown ↓ where there was still a 'd' to be dropped, so there aren't any ↓ marks down the lefthand side or along the top, as those have already been dropped. (If you're unconvinced, a 'trampling' version is attached.) Similarly for the third and fourth passes. This last scan does nothing of course because it either scans up over points already dropped, or hits an 's' and stops. As you can see, there are several 'd's left at the end of all four scans, which your algorithm misses because the 's' loop stopped the scan from reaching them. Original Scanned ddddddddddddddddddddddddd →→→→→→→→→→→→→→→→→→→→→→→→→ ddddddddddddddddddddddddd →→→→→→→→→→→→→→→→→→→→→→→→→ ddddsssssssssssssssssdddd →→→→sssssssssssssssss↓↓↓↓ ddddskkkkkkkkkkkkkkksdddd →→→→skkkkkkkkkkkkkkks↓↓↓↓ ddddskkkkkkkkkkkkkkksdddd →→→→skkkkkkkkkkkkkkks↓↓↓↓ ddddskkkkkkkssssskkksdddd →→→→skkkkkkkssssskkks↓↓↓↓ ddddskkkkkkksddddskksdddd →→→→skkkkkkksddddskks↓↓↓↓ ddddskkkkkkksdddddsssdddd →→→→skkkkkkksdddddsss↓↓↓↓ ddddskkkkkkksdddddddddddd →→→→skkkkkkks←←←←←←←←↓↓↓↓ ddddskkkkkkksdddddddddddd →→→→skkkkkkks←←←←←←←←↓↓↓↓ ddddskkkkkkksdddddddddddd →→→→skkkkkkks←←←←←←←←↓↓↓↓ ddddskkkkkkksdddddddddddd →→→→skkkkkkks←←←←←←←←↓↓↓↓ ddddskkkkkkksdddddddddddd →→→→skkkkkkks←←←←←←←←↓↓↓↓ dddddskkkkkkksddddddddddd →→→→→skkkkkkks←←←←←←←↓↓↓↓ ddddddskkkkkkksdddddddddd →→→→→→skkkkkkks←←←←←←↓↓↓↓ dddddddskkkkkkksddddddddd →→→→→→→skkkkkkks←←←←←↓↓↓↓ ddddddskkkkkkkkksdddddddd →→→→→→skkkkkkkkks←←←←↓↓↓↓ dddddskkkkkkkkkkksddddddd →→→→→skkkkkkkkkkks←←←↓↓↓↓ ddddskkkkkkkkkkkkksdddddd →→→→skkkkkkkkkkkkks←←↓↓↓↓ ddddssssssssssssssssddddd →→→→ssssssssssssssss←↓↓↓↓ ddddddddddddddddddddddddd →→→→→→→→→→→→→→→→→→→→→→→→→ ddddddddddddddddddddddddd →→→→→→→→→→→→→→→→→→→→→→→→→ Achieved Desired ......................... ......................... ......................... ......................... ....sssssssssssssssss.... ....sssssssssssssssss.... ....skkkkkkkkkkkkkkks.... ....skkkkkkkkkkkkkkks.... ....skkkkkkkkkkkkkkks.... ....skkkkkkkkkkkkkkks.... ....skkkkkkkssssskkks.... ....skkkkkkkssssskkks.... ....skkkkkkksddddskks.... ....skkkkkkks....skks.... ....skkkkkkksdddddsss.... ....skkkkkkks.....sss.... ....skkkkkkks............ ....skkkkkkks............ ....skkkkkkks............ ....skkkkkkks............ ....skkkkkkks............ ....skkkkkkks............ ....skkkkkkks............ ....skkkkkkks............ ....skkkkkkks............ ....skkkkkkks............ .....skkkkkkks........... .....skkkkkkks........... ......skkkkkkks.......... ......skkkkkkks.......... .......skkkkkkks......... .......skkkkkkks......... ......skkkkkkkkks........ ......skkkkkkkkks........ .....skkkkkkkkkkks....... .....skkkkkkkkkkks....... ....skkkkkkkkkkkkks...... ....skkkkkkkkkkkkks...... ....ssssssssssssssss..... ....ssssssssssssssss..... ......................... ......................... ......................... ......................... Cheers, David.
Trampled ↑↑↑↑←←←←←←←←←←←←←←←←←↑↑↑↑ ↑↑↑↑←←←←←←←←←←←←←←←←←↑↑↑↑ ↑↑↑↑sssssssssssssssss↑↑↑↑ ↑↑↑↑skkkkkkkkkkkkkkks↑↑↑↑ ↑↑↑↑skkkkkkkkkkkkkkks↑↑↑↑ ↑↑↑↑skkkkkkkssssskkks↑↑↑↑ ↑↑↑↑skkkkkkksddddskks↑↑↑↑ ↑↑↑↑skkkkkkksdddddsss↑↑↑↑ ↑↑↑↑skkkkkkks←←←←←←←↑↑↑↑↑ ↑↑↑↑skkkkkkks←←←←←←←↑↑↑↑↑ ↑↑↑↑skkkkkkks←←←←←←←↑↑↑↑↑ ↑↑↑↑skkkkkkks←←←←←←←↑↑↑↑↑ ↑↑↑↑skkkkkkks←←←←←←←↑↑↑↑↑ ↑↑↑↑→skkkkkkks←←←←←←↑↑↑↑↑ ↑↑↑↑→→skkkkkkks←←←←←↑↑↑↑↑ ↑↑↑↑→→→skkkkkkks←←←←↑↑↑↑↑ ↑↑↑↑→→skkkkkkkkks←←←↑↑↑↑↑ ↑↑↑↑→skkkkkkkkkkks←←↑↑↑↑↑ ↑↑↑↑skkkkkkkkkkkkks←↑↑↑↑↑ ↑↑↑↑ssssssssssssssss↑↑↑↑↑ ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ ↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
