Can't figure out a formula for calculation

[Kent Searight]

Hi all,

I've been going nuts trying to figure out a formula, so I'm throwing in the proverbial towel and requesting help from one of you calculation gurus. Here's what I'm hoping to accomplish:

A calculation that determines how many pieces of material of a given known size (W x L) can be cut out of sheet of material that's a larger size. I've written a calculation that gives me the result for the number of pieces in a tidy little x-y configuration. FYI It goes as follows:

Case (

//test to see which orientation of axes yields the most pieces

Floor( materialSizeW / pieceSizeW ) * Floor( materialSizeL / pieceSizeL ) ≥ Floor( materialSizeW / pieceSizeL ) * Floor( materialSizeL / pieceSizeW );

Floor( materialSizeW / pieceSizeW ) * Floor( materialSizeL / pieceSizeL );

Floor( materialSizeW / pieceSizeL ) * Floor( materialSizeL / pieceSizeW ))

---------------

The problem comes in when I want to deviate from that "tidy" x-y configuration.

An example of that deviation would be:

piece = 8 x 14

material = 17 x 23

desired result = 3 (see drawing)

With my calculation the result would = 2 because it would calculate 2-8's out of 17 and 1-14 out of 23 (2 x 1 = 2 : ). This is just a simple example. Some of the more complex examples might involve hundreds of pieces cut from a single sheet.

Thanks in advance for any help you can offer.

[-Queue-]

This is probably too simplistic, and I haven't tested it very much, but what if you divide the surface area of the material by that of the piece and take the integer result?

Div( materialSizeL * materialSizeW; pieceSizeL * pieceSizeW )

I am sure there are probably situations where this breaks, but it may at least give you an idea.

[Ender]

Looks like an interesting problem. Can we assume the pieces being cut out are always the same size?

Although I don't have it all worked out, my initial thought here is to use a recursive custom function to analyse the remaining materials and test each remaining piece to see if it there's enough remaining. I'd start by having it check the piece size against the materials orientation (longest piece length against shortest materials width,) and if that doesn't fit, try it the other way.

The trick, I suppose, would be decrementing the materials remaining for the successive recursive steps. Simply chopping off the piece width from the materials width might cut off useful material from the bottom.

I have a bad feeling this problem is going to end up in my dreams... :dreaming:

[SlimJim]

I am not surprised that you are finding this hard I believe this is a hard mathematical problem and I don't think you will find a solution in a simple formula. The problem goes under various names: rectangle packing and rectangular stock-cutting problem are two of them; and a Google search will reveal the complexity of the problem.

[Kent Searight]

Looks like an interesting problem. Can we assume the pieces being cut out are always the same size?

Every piece will always be the same size on any one cutting layout, if that's what you're asking...but the physical dimensions of the pieces and the material sheets change from one project to the next.

I believe that it may be possible to do this as a recursive calc, following the line of logic you presented. Unfortunately, I haven't been able to come up with anything and I've been working on it for over a month now (not sure if that's a good thing to admit to : ). It seems to me that a row of pieces needs to be figured into the calculation and then a calculation for the quantity of pieces turned 90 degrees to the orientation of the 1st row would yield the number pieces you'd get out of that grid...then the calc would loop through the same calc but with another row added parallel to the initial, so forth and so on.

Then, when all those calculations are exhausted using the "row plus grid" method, a "column plus grid" method calculation would be looped through. Is this making any sense??? I know what I want to say but I'm not sure I'm conveying my idea very well.

To Slim Jim;

I know what you're talking about because I found info on that when I realized I was getting nowhere. I "simply" am looking for a way to calculate a maximum of 2 x-y grids of pieces cut from a sheet. What you're referring to is an infinite number of cutting combinations, sometimes with unusual shapes. FYI An industry that uses that formulation to its fullest potential is the exotic leather and animal hide industries, as they try to minimize the waste of what can be an enormously expensive material. (I learned this as part of my search for a formula on the web)

[Ender]

Kent,

I like your idea to do a check of pieces in rows then columns. It seems to me that most cases would require the material to be sliced in both directions like that. I believe there are some exceptions that you'd want to account for, but this should be possible. (I haven't researched this as you have, so I may be covering stuff you've already seen.)

In my attached diagram, I'm guessing there's three types of slicing that may be required (there may be more!?)

A. The typical case where you can first slice out the rows, then slice out columns with the remainder (then, if there's enough left, do additional row slices.)

B. The case where the length of the piece can only be cut in one direction. This should be easy to detect, and therefore easy to count.

C. The case where the making slices in both directions would be less efficient than doing them all in the same direction.

In all cases, I think you would first do an easy check to see how many slices could be made vertically (on the horizontal material.) Keep this count around for comparison later. This is a "C" case we want to check in addition to the other horizontal-vertical check.

Next we proceed with counting horizontal slices (1-5 in diagram A.) Next, we'd check for the best count from either the "A" case and the "C" case. Run the counts for the columns with row remainders ("A" case,) and compare that to another set of horizontal rows (the "C" case.)

Then compare the best count at each branch and total the best ones.

That's my big idea anyway. I think the algorithm is sound, so long as you don't throw in parallelograms or something. Implementing this probably could be done without a custom function, using let() variables or multiple fields to keep track of the best count from each branch.

Edited October 13, 2005 by Guest
Fixed file format.

[Kent Searight]

Part A of your diagram is the Holy Grail for the solution, because if the calc can figure that then it's already figured B and C to get there, at least in my logic.

You've given me some ideas, so I'm going back to the drawing board to try to hash this out a bit more.

I'll post the results if I figure something out (but don't wait up for me on this one)! :zzz:

[Inky Phil]

Kent,

I do not know if you are working this out for an industry in which you are expert or for someone else but in my industry, printing, the grain direction of the base material in some cases matters and in others doesn't.

So Enders Part B and/or C would be the norm but part A might also be a possibility.

Forgive me for raising this if it is obvious to you but I realised that you have a hill to climb with this one and I didn't want you to sweat too much only for the customer to discard the work because of this consideration

Regards

Phil

[Ender]

Inky's important point aside, another possibility occured to me: If the piece length is less than a third the materials length. In this case, you would begin with the A algorithm (1-9,) and then have to repeat it with the remainder. So again, I'm thinking a recursive custom function may be needed.

I think this could be generalized further. You start by getting as many rows down as possible on the material's horizontal (like in A 1-5,) then recusively do the same with the remainder (always adjusting the remaining material to be in a horizontal orientation.) You'd still test for the special cases of B and C in each iteration.

[Kent Searight]

I knew that someone with ink under their nails would figure out what industry I'm doing this for. It does deal with cutting pieces out of parent stock, so yes, grain direction can be important.

I worked in the printing industry for almost 25 years, but I don't consider myself an expert. (there are already enough of those in printing : ) But I do feel comfortable engineering layouts on [printing] forms, since I've literally done 10's of thousands (probably more, actually).

Anyway, thanks for raising a valid issue that might come back to sting someone with less knowledge about the industry for which they're designing a solution.

FYI In addition to checking to see if grain direction is critical, I'm also checking for watermarked stock, patterned stock (laids), etc. If any of these factors are present, the calculation is actually much simpler so I've already got that part covered.

Sooo, Inky Phil, any ideas on how I can solve this?

[Kent Searight]

Hi Ender,

This is my logic, and what I see as variables...first the variables that have known values entered in their respective fields:

pieceAxisA = dimension of piece, axis A

pieceAxisB = dimension of piece, axis B

materialAxisA = dimension of material, axis A

materialAxisB= dimension of material, axis B

Let (

//now I find out how many pieces can come out of 1 row of axis A of material when axis A of piece is parallel to axis A of material

[ AACount1 = Floor ( materialAxisA / pieceAxisA ) ;

//I do the same for axes B

BBCount1 = Floor ( materialAxisB / pieceAxisB ) ;

//then I turn the piece 90 degrees to see how many pieces come out of axis A of material when axis B of piece is parallel to axis A of material

ABCount1 = Floor ( materialAxisA / pieceAxisB ) ;

//etc.

BACount1 = Floor ( materialAxisB / pieceAxisA ) ;

//Now I test for how much material is left on axis B of material when a row of pieces is subtracted from material via the method of AACount1

MaterialLeftBMethodAA = materialAxisB - (pieceAxisB * countMethodAA);

//Now, hopefully, you'll understand my syntax and see where I'm going with this, from this point on...and you may notice a problem...I haven't addressed the variables "countMethodAA, countMethodBB, etc., because I can't figure out how to assign values to them. They represent the number of rows (or columns) that are being factored into the calculation. How can I count and loop through them?

MaterialLeftAMethodBB = materialAxisA - (pieceAxisA * countMethodBB);

MaterialLeftBMethodAB = materialAxisA - (pieceAxisB * countMethodAB);

MaterialLeftAMethodBA = materialAxisB - (pieceAxisA * countMethodBA)] ;

//End Let

//Calculation goes here - my logic is that if I subtract a row or column of any given combination of piece-to-material axes from the material, that's my new material size that I have left over to work with and then I can calculate the most efficient grid, using the simpler calc I started off with. Then, that number of pieces is added to the number of pieces of the row(s) or column(s) that exist for that portion of the calculation. Does this make sense to you??? I'm having a hard time following it myself

)

I really hope that my logic doesn't get anyone going down the wrong path. I'm not sure how valid it is...and I'll be the first to admit that this is by far the toughest calc I've ever dealt with...help is greatly appreciated (and much needed)

[Inky Phil]

Hi Kent,

Well, no but here goes...

I presume that you are working on an estimating system. I am in the middle of re-writing my own in 7 as we speak

I am sure you are aware that there are proprietory solutions out there that contain coding that will do this job so it isn't impossible, however...if SlimJim says it isn't easy (he is particularly qualified in maths things) and he doesn't offer to get stuck in (he enjoys a good tussle with numbers) then I think it is safe to assume that it isn't that it isn't easy - It is HARD!

As I said I am developing my own estimating system and I seem to recall that when I was doing my research into how everybody else in the market place approached such things I was told that people bought the algorithms (at a not inconsequential price)so that they could include this funcionality in their solutions.

I decided therefore to approach it in a different way.

There was another reason for this decision.

I initially wanted to arrive at a solution that anyone could get a price out of but because of the complexities of our industry (ie every item is bespoke),I soon realised that a fully expert system would be incredibly complex.

Indeed the complexity of the existing systems was the main reason that I decided to tackle this for myself.

I came to the following conclusions

1/ To let a complete novice attempt a quotation was asking for trouble. There were just too many considerations.

2/ For someone to use an expert system they had to have some knowledge of the processes involved otherwise they would not understand the expert system

3/If they had some knowledge then with a minimum of questions (2 fields to be entered in addition to the quantity required)I could arrive at the stock required to be bought and to be run.

For 99% of the quotes done their answers to the 2 questions would come automatically (because they just know!)and this gives an instant result. For the other 1% (the unusual jobs)they would have to give it a little thought before they filled in the fields but the result would then be correct. I considered this a fair trade off.

Listen, I have gone on long enough now(I could bore for Britain about print estimating systems) and any further info would be industry specific and not very interesting to others in the forum.

If you want any more info PM me and I will let you have a sample but please bear in mind my solution only suits the general commercial sheetfed market and my trade off would not be suitable for any more specialised area.

Regards

Phil

[Ender]

Hi Kent,

Here's a custom function using the algorithm I described earlier. It seems to work for all the cases I talked about.

RectCount ( PieceA ; PieceB ; MaterialA; MaterialB ) =

//RectCount ( PieceA ; PieceB ; MaterialA; MaterialB )



//Returns the number of rectangles (with dimensions PieceA x PieceB,) that 

//can be cut from an area of materials (with dimensions MaterialA x MaterialB.)



//10-13-2005

//By Mike Hackett





Let(

[

PieceLongSide = Case(PieceA

PieceShortSide = Case(PieceA≥PieceB;PieceB;PieceA);

MaterialLongSide = Case(MaterialA

MaterialShortSide = Case(MaterialA≥MaterialB;MaterialB;MaterialA);



/*Check the count with first cutting hozontal pieces from horizontal material.*/

CountRows = Case(MaterialLongSide≥PieceLongSide and Div(MaterialShortSide;PieceShortSide)>0; 

                               Div(MaterialShortSide;PieceShortSide) + 

                                    RectCount(PieceA;PieceB;MaterialShortSide;MaterialLongSide-PieceLongSide));



/*Check the count with first cutting vertical pieces from horizontal material.*/

CountColumns = Case(MaterialShortSide≥PieceLongSide and Div(MaterialLongSide;PieceShortSide)>0; 

                               Div(MaterialLongSide;PieceShortSide) + 

                                    RectCount(PieceA;PieceB;MaterialLongSide;MaterialShortSide-PieceLongSide))

];

/*Return the greater count*/

Max(countrows;countcolumns)

)

Attached is a demo file.

RectanglePieces.fp7.zip

[Kent Searight]

Wow Mike!!!

I'm floored and in total awe!!! Thank you!!!

I've thus far tested it with a variety of dimensions that produce both single-grid and "Dutch cuts", and I can't get it to fail.

Now...I just need to understand it. I've stared at it for a while now and I have the feeling that I'll get it soon. The only question I have for now may seem a little obvious but I just want to clarify what I already suspect is true.

You use the Custom Function "RectCount" within itself using parameter values that are different from the values in the fields that the calculation calls upon. (this confuses me even when I try to articulate it : ) Is this how the function becomes recursive??? This is the part where my understanding of the algorithm breaks down.

Once again, many, many thanks for coming up with a solution. I hope I can help you in turn sometime!

[Ender]

Hey Kent,

I know I made that CF code pretty compact. The calls inside the function to RectCount() are indeed recursive calls. What it does, is count the number of pieces possible going up and down + RectCount() on the remaining material, and compares that to the number of pieces possible going across + RectCount() on the remaining material in that direction, and returns the highest number.

A closer look at the recursive part should make things clearer. In the attached diagram, you can see how we first count the rows up and down, then have the recursive call to RectCount() on the remainder. Each call to RectCount() re-orients the remainder, so we can do the same exact same thing, counting the rows up and down and then looking at the remainder (in fact, both orientations are tried at each call, and the best count returned.)

The only reason the 'CountColumns' part is necessary, is to account for that darned case "C" that we talked about before.

Hope that clears it up. If you haven't used recursive CFs before, I think you'll enjoy exploring their power. :

[Ender]

Oops, ignore the missing piece 6 in the diagam!

[Inky Phil]

Wow!! indeed Ender

I am now going to consider including this function in my solution and if I do ... and if I go commercial with it... and if it makes me any money... I will send you some !!

In the meantime all I can give you is RESPECT man!

Phil

ps KENT - dont forget gutters and trims when entering your sizes.

[SlimJim]

A fascinating thread - although I have no interest in the specifics - I had no idea that Filemaker was capable of recursive function definitions it lifts calculations to a new level.

[Inky Phil]

Just a thought,

If we (and by we I don't include me) don't give the user a graphic representation of how this function got that number of pieces out of the given material then they could spend more time working out how to fit '33' into the given size as it would for them to work it out for themselves in the first place :

Like I say, just a thought...

Phil

[Ender]

All they have to know is it works, right!

I suppose if a diagram of the cuts were needed, it could be done. I'm wokring on some shape computation stuff with the xmChart plugin right now, though my shapes are much simpler that these diagrams would be. A diagram creator would still be a recursive calc, but it would return the points or positions of the shapes in a big string (the string is then processed and sent to the charting plug-in.) Sounds like fun. :wink2:

[Ender]

SlimJiim, I'm shocked that you haven't got you feet wet in recursive custom functions yet. They are the real power of custom functions. You should check out some of the cool custom functions in the Custom Function forum.

[Kent Searight]

I agree with Inky Phil...that the user could potentially become confused by an array that doesn't conform to an xy grid pattern. My short term solution to this is to compare the results of Ender's calc to the results of the calc I presented earlier and if Ender's calc is > the results of my calc, then a flag (graphic in container, red text if Dutch cut, or something along those lines) of some sort will appear on the UI to let the user know that a Dutch cut is the result. I might even take it so far as to let a radio button toggle which value is returned, i.e. If radio button has value "Yes", then Dutch cuts are allowed, if "No", then only single grid configurations will be returned.

Like almost all instances in UI design, there are many options for handling something like this. The key is to figure out which one is most user friendly! :

My long term goal is precisely what Ender mentions above...draw the layout with the help of xmChart plug-in. That would just be the cat's meow!

[SlimJim]

SlimJiim, I'm shocked that you haven't got you feet wet in recursive custom functions yet. They are the real power of custom functions. You should check out some of the cool custom functions in the Custom Function forum.

It has now come to the top of my list of things to do!!

FMP8 Advanced is my first foray into Developer editions and I am still enjoying all the other advantages.

[jstaphase]

I'm also working on the "Swing" or "Dutch" aspect for a printing company. I plan to use XMChart for the visual aspect of it. Now if I can figure out how to use the custom function. Thanks for that.

[Ender]

If you manage to get a CF to build the chart string (to plot the rectangles with xmChart,) let us know what it is. I imagine this could be done with a recursive CF as well, giving the function a new x-y range for each recursive call and calculating the bounds for each rectange within.

[jstaphase]

ender, I just re-read all the replies, and noticed that you are using XMChart also.

I have a few calculations that I test my file with, and I think I found a problem with the CF. I've attached a picture of a layout which is 19x25 with 15- 4x7 pieces being cut out of it.

The CF says I will get 16 out.

[Ender]

Well, rather than analyze the function, I decided to try to get sixteen 4x7 pieces to fit in a 19x25 space. I looked and looked, and kept counting only 15 in whatever arrangement I could think of. But eventually, I found the magic configuration (see attachment.)

Fortunately, the CF tries all arrangements and returns the best one, even if it's hard for humans to see (or cut.) B)

[jstaphase]

I wonder how many estimators and planners would have come up with that one. It looks like a trick question for printers. I'll test our planning guy Monday.

I haven't got to the charting plugin yet. I'll let you know what I come up with. Also, I'll never doubt you again. :

Edited November 3, 2005 by Guest

[Ender]

I decided to build CFs to draw the resulting rectangles. They can be found here:

RectCoordinates()

RectCoordinatesSub()

RectCount()

DrawRect()

There is an example file in with the RectCoordinates() CF. You'll need the xmChart plugin to refresh the charts (a demo version of the xmChart plugin can be found at www.x2max.com ).

[SpunDeep]

I came across this topic a week or do ago... Sheer genius

I have been attempting to calc this myself for quite some time,

Born with ink and paint under my finger nails spending most of my holidays 'racking' for the qualified tradies

Or making my own stickers signs prints what ever when I wasn't required,

This has been quite a journey reading through it, I'm about to download the charting demo and give it a whirl....

Bound to have plenty of questions, and a few more parameters that I would like to through into the mix

That function is written so tight I'm not quite sure where to factor these other parameters in.....