Search code examples
algorithmvector-graphicsshortest-pathflood-fill

Find out how to flood fill a polygon with the smallest number of vector lines

Say I have a vector polygon with holes. I need to flood fill it by drawing connected segments. Of course, since there are holes, I can't fill it using a single continous polyline: I'll need to interrupt my path sometimes, then move to an area which was skipped and start another polyline there.

My goal is to find a set of polylines needed to fill the whole polygon. Better if I can find the smallest set (that is, the way I can fill the polygon with the minimum number of interruptions).

Bonus question: how could I do that for partial density fills? Say, I don't want to fill at 100% density but I want a 50% (this will require that fill lines, supposing they're parallel each other and have a single-unit width, are put at a distance of two units).

I couldn't find a similar question here, although there are many related to flood-fill algorithms.

Any ideas or pointers?

Update: this picture from Wikipedia shows a good hypotetical flood path. I believe I could do that using a bitmap. However I've got a vector polygon. Should I rasterize it?

Path example

Solution

  • I'm assuming here that the distance between lines is 1 unit. A crude implementation, with no guarantee to find the minimum number of polyline, is:

    1. Start with an empty set of polylines.
    2. Determine minx and maxx of the polygon.
    3. Loop x from xmin to xmax, with a step of 1. Line L is the vertical line at x.
      • Intersect vertical line L with your polygon (quick algorithm, easy to find). That will give you a set of segments: {(x,y1)-(x,y2)}.
      • For all polylines, and all segments, merge segment + end of polylines (see note 1 below). When you merge a segment and a polyline, append a small stretch at the end of the polyline (to joint it to the segment), and the segment itself. For all segments that you can't merge using that, add a new polyline in the global set.
    4. At the end, try to merge again polylines if possible (ends close together).

    Optimal algorithm for merging new segments to existing polylines should be easy to find (hashing on y), or a brute force algorithm may suffice:

    1. number of new segments per line scan should not be too high if your polygons do not have zillions of holes,
    2. number of global polylines at every step should not be too large,
    3. you compare only with the end segment of each polylines, not the whole of it.

    Added note (1): To cover the case where your polygon has nearly-vertical edges, the merge process should not look only at y-delta, but allow a merge if any two y range overlaps (that means end of polyline y-range overlap segment y-range).