search

AnonMiraj / fig

FIG (Fortran Intuitive Graphics)
MIT License
27 stars 2 forks source link

Area fill #7

Closed johandweber closed 7 months ago

johandweber commented 7 months ago

I have now implemented the subroutine fig_fill_area which implements the flood fill algorithm with a queue. ( https://en.wikipedia.org/wiki/Flood_fill )

The color of a contiguous area defined by a starting point is changed.

Additionally, I have added the test program fill_area.f90 .

I do not think my algorithm is well-optimized.

For example, each of the fill operation requires the allocation of two arrays where the number of elements is (in total) 3 times the number of pixels in the canvas, independently of the actually filled area.

So one might implement an more efficent queue structure.

AnonMiraj commented 7 months ago

Very interesting, thanks I really like the example; it makes me want to implement Bezier curve lines and anti-aliasing even more.

But I have a question: How would a recursive approach compare? They should be similar, but I wonder if one of them is more efficient than the other.

johandweber commented 7 months ago

I tried it, but got a memory error (stack overflow?).

johandweber commented 7 months ago

The issue is that for large surfaces, the recursion depth could be several thousands. On the other hand it should be more efficient for small surfaces.

Maybe a stack with flexible size would be the best solution.

AnonMiraj commented 7 months ago

i will investigate it and possible alternative implementation later