2

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?

Wasabi Fan
  • 1,763
  • 3
  • 22
  • 36

2 Answers2

2

  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
Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • So, as I understand it, your proposal is to split it in to triangles and solve each individually? That would mean that the path would double back and otherwise go off a straight line in each section, making it much longer that it would need to be. Any ideas for how to join the separated paths? – Wasabi Fan Sep 02 '14 at 04:29
  • @WasabiFan split to convex polygons not triangles (rendering convex polygon is the same as rendering triangle you just fill the boundary buffers with more then 3 polylines before rendering). that is just first step, you can for example hold all horizontal lines in some list and try to join some later ... – Spektre Sep 02 '14 at 05:46
  • @WasabiFan btw do you need to met any special condition ? like growing on previous layer or rendering near already rendered lines if can (like for some 3D printer process), or prefer specific shape/pattern of filling (this one is common for engraving machines) or you need just smaller distance (vector displays) – Spektre Sep 02 '14 at 05:53
  • My setup is very similar to something like an engraving machine algorithm. I would prefer something like what you illustrated in your diagram (a systematic pattern of horizontal or vertical lines). – Wasabi Fan Sep 06 '14 at 00:38
  • @WasabiFan that is easy just start with the triangle/convex polygon rasterisation (you can start with filling pixels on the screen) when you got it working right then you change it to output geometry instead of horizontal lines ... it is pretty straight forward. this kind of filling creates special aliasing on the engraved surface you can change it by changing the distance between lines in respect to tool width +/- some overlap/gap. I was experimenting with spiral filling which was desired for some engraving aliasing effects but that is extremly complicated ... – Spektre Sep 06 '14 at 08:40
1

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.

mcdowella
  • 19,301
  • 2
  • 19
  • 25
  • What about the filling of the black areas themselves, assuming we forget about traveling between them? I mean, what would be the best way for me to go about finding a path to fill any given black blob? – Wasabi Fan Sep 01 '14 at 05:08
  • Spektre's answer seems entirely reasonable for filling the black areas. You might be able to do better if you had a much clearer idea of the cost of filling a small area or drawing a raster line, and if you were prepared to solve the TSP to work out how best to join adjacent convex components or triangles, but this looks a good fit to what you have said so far. – mcdowella Sep 01 '14 at 17:21