Hacker News

points by zimpenfish 2 days ago | 0 comments

Huh, that's useful because I had to write a floodfill a couple of days ago and it was a pain in the arse.

I'll be converting my code to the stackless version toot sweet.

Why were you needing floodfill?

To find connected regions on a map. I could probably have been smarter about the initial generation and connected things as they were generated (but that has only just occurred to me. Worth a go, I suppose.)

[–] kragen 2 days ago

Use union-find to find connected regions on a map, not flood-fill.

[–] zimpenfish 2 days ago

I assume you mean "connected-component labeling" with union-find as the underlying "manage the sets" algorithm? If not, a link would be helpful.

[–] kragen 2 days ago

What I mean could be described that way, but I'm not sure if you mean the same thing. Just in case, I elicited an implementation from Opus 5.5. I have carefully verified that this implementation implements what I mean: http://canonical.org/~kragen/sw/union-find-components.html

[–] cyberax 2 days ago

I also wrote a floodfill a while ago! We have a mapping app, and our imagery provider returns half-filled tiles at the edge of their coverage. And annoyingly, they don't have any metadata within the tile itself that indicates the coverage. They just return black pixels for a part of the tile.

So I needed a way to detect that, and doing a floodfill from the edge of the image turned out to be the easiest way.