Algorithm for cutting a polygon into specific shapes

[zdaraveak]

Hello everybody,

I have a shape (polygon) made up from pixels (squares) similar to the image below. I need an algorithm to cut it into "lines" i.e. shapes of 1x[1..20] pixels. The lines should not be necessarily straight, but they should fill the entire area.

Any ideas on where to start working on this? Is there a similar math algorithm out there or should I just try and "fit" the different shapes starting from the larger ones and then filling it up with 1x1's?

Thanks a lot for any input

 

[chiro]

Hey zdaraveak and welcome to the forums.

I think I can give you answer but I would need to see one or two examples of what you want to generate exactly.

It would be helpful if you used a paint program for two examples and generates the lines using a line tool.

Do you just want to create squares of sorts to cover the shape in black? It's a little hard to know exactly what you want to do.

 

[zdaraveak]

Hello chiro,

Below you have an example of what I have in mind together with a list of shapes that are allowed and a list of those that aren't. An "allowed" line is basically the line that you could draw from start to finish without going through the same pixel twice.

I color coded the lines of different lengths so that you could see better what's going on.

Thanks

 

[chiro]

Hello chiro,

Below you have an example of what I have in mind together with a list of shapes that are allowed and a list of those that aren't. An "allowed" line is basically the line that you could draw from start to finish without going through the same pixel twice.

I color coded the lines of different lengths so that you could see better what's going on.

Thanks

Ok this is a lot more complicated than what I anticipated, but never the less I think I can give you some useful advice.

The first thing I need to know is what constraints you have. From the above picture it seems that the only constraint you have is that you have a bunch of lines of a certain length that have to be continuous in some fashion (this includes diagonals) and that you have to fill up your shape in this manner.

With this description your constraints are really really huge. In fact the number of solutions for this kind of problem is so big that I wouldn't know where to start to give you ideas for generating them. You could use statistical methods which is what I would recommend but again this is more for generating them randomly instead of understanding how to generate them deterministically.

There is a problem that is known as the bin packing problem that might interest you. What the bin packing problem is in a nutshell, is that you have objects in certain dimensions and you have to find out the maximum number of objects you can fit in a number of bins while minimizing the empty space in your bins.

As an example consider that you have to cut steel of a variety of different measurements (an array of numbers) and that at the steel cutting plant you have precut blocks of say 50 metres long and you have a list of arbitrary measurements. You have to basically use those 50 metre long steel rods as the 'bins' and find out the exact configuration of matching your sizes in your data to those rods or 'bins' in a way that minimizes waste.

This is not an easy problem, but if you have very specific shapes in mind (in your example you can make any shape with your lines but in the bin packing problem, the number of different shapes you can use is fixed), then you need to read about the bin packing problem in two-dimensions. It actually has a lot of applications especially in engineering so I think you should be able to find enough if you look hard enough.

So before we continue, I need to ask you whether you can generate abritrary shapes like you did in your picture, or whether you want the actual number of allowed shapes to be fixed as to minimize the the waste that is generated when you use a certain number of shapes.

Also before I forget, another thing that you can do is to specify a fixed number of shapes and then add one block pixels or other shapes to the missing parts.

 

[zdaraveak]

OK, so I set up a small console app to calculate all the possible combinations and for this shape (~300px) using lines of lengths 1..6, there are over 33 million solutions :D

Of course I can filter quite a few ones out, like the ones where there are too many lines of the same size, also minimize the number of 1px and 2px lines. The forms of the shapes are pretty fixed (in that I can define them explicitly).

I will take a look at the bin packing problem and hope that I will find something that will help me out.

Thanks a lot for the tip.

 

[Edgardo]

When I read your problem I immediately thought of graph theory. The allowed shapes seem to be chains. Here is a paper that examines sets called C_k. A set C_k consists of k disjoint paths (chains) such that every vertex (pixel) is visited exactly once.

Another thing I thought of are Polyominoes. Given a set of polyominoes your task is to tile a region. There are some books on amazon dealing with this topic.