zdaraveak said:
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.