0

I'm looking for an algorithm that can cut a shape with holes into shapes without holes. Language is preferably C#.

Here's an example image of such a shape. original shape

I'd like to cut that shape into the least amount of smaller shapes without holes getting rid of most of the empty space (white). In this case this might probabyl be a bunch of rectangles. But the original shape might be more complex with rounded holes for example.

For me this sounds like some sort of a bin packing problem and therefore might be solved best with a genetical algorithm.

But in case you know a better approach, it's why I ask.

//edit: alright, I've obviously got some things to explain:

  1. The shape is a Geometry object (WPF) resulting from the subtraction of a bunch of small Geometries from a larger Geometry. So I guess there are vertex points stored somewhere.

  2. The amount of resulting shapes should be minimized, yes, the smallest set.

  3. The resulting shapes should have edges that are as straight as possible with the smallest amount of corners possible.

  4. Unfortunately, I can't provide any code, yet, since I have no clou whatsoever how to practically approach this programmatically. I'm really sorry.

  5. The resulting shapes should be complex but don't have to.

To explain the reason for this: I'm working on a textile crafting (in particular patchworking) program with which one can create patchworks and calculate how much fabric is needed and the cost. Placing the patches on the fabric panel already works somehow using a Tetris like algorithm where patches get placed as close together as possible to reduce waste.

Additionally, everywhere the shape gets cut I need to add a seam allowance to the resulting parts (that's what you can already see in green in the example image).

//edit 2 An acceptable solution might look as follows. Red lines show where shape gets cut in order to get an amount of resulting shapes that don't have holes. The result set contains six large and 25 small rectangles:

red lines show where shape gets cut

However depending on the original shape which might look totally different, even with rounded edges (circular holes), acceptable solutions also might look different. The goal is to get rid of the white areas as far as possible while maintaining some convenience regarding the later actual cutting of the fabric. It'd be somehow counter-productive to have lots of shred that has to be sewed together again (and hence all need seam allowances) only to save a little bit fabric more.

Hendrik Wiese
  • 2,010
  • 3
  • 22
  • 49
  • 3
    A lot of this is going to depend on how the "shape" is currently defined. Is it an image? A collection of points? – user7116 Jul 30 '13 at 15:07
  • Does the resulting group of shapes need to be a smallest set? Or is any number of shapes acceptable? Additionally, does the algorithm need to be able to handle shapes with curves and non 90 degree angles? – Luke Willis Jul 30 '13 at 15:11
  • Please provide some code you've attempted and a set of more rigorous definitions and conditions. I think that would answer the comments' questions so far. – Jesse Smith Jul 30 '13 at 15:13
  • Do the resulting shapes need to be convex? – Patricia Shanahan Jul 30 '13 at 15:14
  • One possibility for a related field is [mesh generation](http://www-users.informatik.rwth-aachen.de/~roberts/meshgeneration.html). [Automesh2D comes to mind and is nice](http://www.automesh2d.com/default.htm). – user7116 Jul 30 '13 at 15:18
  • this may help http://stackoverflow.com/questions/9257435/cut-holes-in-a-texture2d – Bit Jul 30 '13 at 15:31
  • genetical algorithms ftw – Thick_propheT Jul 30 '13 at 15:37
  • 1
    Can you please submit a set of acceptable solutions to the problem? You should either clearly define "shape" and/or "hole". If, for instance, a "hole" is defined as whitespace that has no connection to the outside area, then a solution to the example image might be to sever the figure along four horizontal cuts, each slicing through a row of holes. This solution will give you five polylines; all without holes. – Tormod Jul 30 '13 at 16:11
  • Erm, yes, a hole is a whitespace area. It might however also have a connection to the ouside area. The final goal is to cut the shape into several smaller shapes that can be optimally placed on a fabric panel to save fabric and reduce cost. – Hendrik Wiese Jul 30 '13 at 17:46
  • 1
    The result-picture you posted is actually not the smallest way to subdivide it without holes. It consists of 31 parts, and there is a way to do it with 23 parts (I don't know whether that's minimal) – harold Jul 30 '13 at 17:48
  • Maybe you just need to search for the right term, try this: Breaking a concave polygon into convex ones – the_lotus Jul 30 '13 at 17:58
  • harold: Yah, I see. It's just an example that also takes cutting convenience and esthetics of the final product into account. Well, I assume a specialized algorithm would become way too complex. A genetical approach might be far easier to implement. the_lotus: Maybe. I'll have a look at the results to that search term. Thanks. – Hendrik Wiese Jul 30 '13 at 18:37
  • Do the final shapes in the result have to be rectangles? If not, what are the restrictions? Do they have to be convex? For example, you haven't specified any rules that would disqualify @Tormod's suggestion of 4 horizontal cuts through the center of the holes. – mbeckish Jul 30 '13 at 18:51
  • They should be mostly rectangles, however if that's not possible due to remaining parts of the original shape that can't be efficiently split into rectangles of a reasonable size (each additional cut also adds fabric necessary for seam allowance) the resulting shape can also be different. Imagine a rectangular original shape with a quadratic hole, rotated by 45°, close to one of its corners but still some cm off the borders of the orig. shape. The orig. shape can easily be cut into four rectangles that are tangent to the hole. The remaining parts of the fabric are four triangles. – Hendrik Wiese Jul 30 '13 at 19:38
  • Furthermore they should be convex but don't have to as long as they can be efficiently placed on the fabric panel without producing too much waste. Tormod's suggestion isn't necessarily bad at all. There's just an optimization rule that would probably reduce its value due to too much waste when it comes to real cutting of the fabric. – Hendrik Wiese Jul 30 '13 at 19:42
  • @SeveQ - How do we calculate waste? Is it `waste = (area of rectangular region bounding the fabric layout) - (area of fabric pieces actually used to assemble the final shape)`? – mbeckish Jul 30 '13 at 19:57
  • @harold: I got 23 parts as well, but if you can only "cut" from the outside the problem may not be much simpler. – user7116 Jul 30 '13 at 21:08
  • Waste is actually basically any fabric that can't be used in the current project and occupies space on the panel that could be used by other pieces if the pieces were cut and packed more efficiently. Regarding the example, if I placed the shape on the panel as it is, waste would be every white area in the picture. So, yes, @mbeckish, your calculation of waste is correct for every single piece of fabric the final product is made of. The optimal solution would be `rectangular region bounding the piece = fabric actually used in the final shape => waste = 0` – Hendrik Wiese Jul 31 '13 at 19:30

1 Answers1

0

I'm not sure how you want the resulting shapes to be but I'm going to assume that you want them in Polygon. As in an object Polygon which is a vector of 2D vertex points (x,y). What you can do now is use this Clipper library for solving geometric spatial problems. It does polygon subtraction, addition, intersection, and a bit more. Its also fast, free, and no license is needed.

http://sourceforge.net/projects/polyclipping/

Afterwards, you can calculate your seam lengths by just finding the distances along each polygon vertex and adding them up. However, this library does not support curved contours.

sgtHale
  • 1,507
  • 1
  • 16
  • 28