CODEWITHSUNDEEP
c#algorithmimage-processingaforge
Wasabi Fan
Wasabi Fan

Reputation: 1863

Finding a single path to fill all shaded regions of an image in C#

I have a black-and-white (binary) image. It contains a set of black blobs, surrounded by white. I am trying to write a C# program that will find a single path to cross through all of the shaded area, while leaving out as much of the white area as possible. This is very similar to finding a toolhead path for a 3D printer for any given layer; it needs to fill the solid parts, while only crossing in to empty space when it needs to get to another separate blob.

For example, here's a test image that I have created, that includes most of the challenges that I am facing (with only two blobs for simplicity):

example blobs

I would want to find a path that would cross through all the black areas, while only crossing the white once to jump between the two shapes (where they are closest). I would also want the path to be as short as possible.

My program is written in C#, and I am already using AForge for image manipulation up to this point, so I already have that accessible.

So far, the closest that I got was with a flood-fill-like algorithm. It would start at a corner, and find the closest pixel(horizontally first, then vertically), to continue the path. But the paths didn't always go everywhere, and crossing over usually created a long and largely extraneous path. I also tried tracing the edges and going inward, but it still didn't work very well when a blob had a non-straight path. Searching didn't come up with much either; I tried searching for things relating to 3D printing algorithms, flood-fills, etc, but not much came up.

So, how should I tackle this?

Upvotes: 2

Views: 776

Answers (2)

Spektre
Spektre

Reputation: 51903

  1. filling the blobs

    • they are just filled polygon
    • convert them to set of closed convex polygon
    • or triangulate it
    • then render like closed polygon filling + triangle/convex polygon rasterisation
    • booth use the same rasterisation
    • so you will get a set of horisontal/or vertical lines (depend on how you code it)
    • so just join them together to single polyline enter image description here
    • there are other ways to fill the are but this one is easiest and error prone

  2. movements between blobs

    • this is indeed TSP which is NP complete (see mcdowella answer)
    • handle all closed polygons as separate blobs
    • use heuristics (join blobs in close proximity)
    • limit the movement length as solution criteria

Upvotes: 2

mcdowella
mcdowella

Reputation: 19621

In the case when the black areas shrink to points, this seems to be turning into the traveling salesman problem, so I suspect that there is no easy answer.

This suggests to me that you work out the closest distance between all pairs of black regions and then use some approximate solution to the traveling salesman problem on this distance matrix. A search finds a closest distance algorithm described at http://cgm.cs.mcgill.ca/~orm/mind2p.html. The TSP approximation algorithms that come to mind are those based on http://en.wikipedia.org/wiki/Minimum_spanning_tree, and on bitonic tours - e.g. in http://www.cs.helsinki.fi/u/jwkangas/daaa2013/sol-II.pdf.

Upvotes: 1

Related Questions