calling all Linux hackers...

Page 4 of 4  
Walt wrote:

I said "development environment" not "operating system."
--
Michael McIntyre ---- Silvan < snipped-for-privacy@users.sourceforge.net>
Linux fanatic, and certified Geek; registered Linux user #243621
  Click to see the full signature.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

Man you are one paranoid individual.

Well, if you were smart, yes. Low salary equals low taxes.

I would be willing to bet that they're worried less about Linux than you're worried about Microsoft and what Bill Gates is up to. Just be happy that you've "outsmarted" them and get on with life before you have a coronary.
-Bill
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Silvan wrote:

I am, unfortunately, not available to help code this, but some ideas that may help:
- Separate the logic of the program from it's GUI presentation. That allows you to start out without a GUI and have it just spit out textual descriptions of the cuts initially until you have that part of it under control. Then you can write the GUI piece last to turn those descriptions into a visible cut picture. IOW, make it _right_ then make it _pretty_.
- A _Very_ good and easy to maintain environment for this kind of thing is the Python language with Tkinter GUI framework. The nice thing about it that your program will run on Win32, Linux, FreeBSD, and probably even Macs. I wrote a reasonably complex program like this some time ago and was VERY happy with environment: http://www.tundraware.com/Software/twander /
- Recognize that taking a list of desired cuts and fitting them to a given sheet size (or sizes) is not some absolute mathematical process. It requires a heuristic approach because these kinds of problems are what are called "NP-Complete" - you cannot possibly try every combination of fit to get an optimized cutting arrangement. You need some general rules to help the program limit the number of tries until you get one that is "good enough". You may want to do some reaseach on this to see if anyone has done this heurstic work in a way that could apply to your problem.
- This is not an inconsequential program, so be prepared to spent some time with the design, especially of the layout engine.
- Don't forget to factor in the kerf width :)
--
----------------------------------------------------------------------------
Tim Daneliuk snipped-for-privacy@tundraware.com
  Click to see the full signature.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Tim Daneliuk wrote:

Definitely. My thinking has been going in that direction too. We need to solve the underlying problem first, before even thinking about what features the thing should have.

Interesting. I'll have a look. I've not done anything with Pyton, but I think I have a beginner's guide around here somewhere. Python or Ruby, I forget which. It looks kinda nasty to learn.

Definitely. I've spent some time thinking about the problem, and inconsequential is quite an understatement. :)
In fact, I have to admit that after thinking on this for a couple of days, I picked out a whole list of things that I need to do to clean up messes I've left behind in Rosegarden before I can think about getting involved with something this enormous.
Nothing like a seemingly insurmountable challenge to make those old, irritating bugs look like an appealing use of time, is there? :)
--
Michael McIntyre ---- Silvan < snipped-for-privacy@users.sourceforge.net>
Linux fanatic, and certified Geek; registered Linux user #243621
  Click to see the full signature.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Silvan wrote:

No. If you have ever programmed in any modern language (perl, C, C++, java, pascal, BASIC, etc.) Python will be the _easiest_ language you ever learned. If I were still teaching (thank goodness I am not), I would use Python for beginning programmers...
---------------------------------------------------------------------------- Tim Daneliuk snipped-for-privacy@tundraware.com PGP Key: http://www.tundraware.com/PGP /
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
As a professional software designer, I've been following this thread with some interest, to see where it goes. Although I already have CutList Plus, and it more than suits my needs, it would be nice to have a Linux native application as well.
Although Linux is my preferred environment, I'm not a Windows basher. In fact, I have two nearly identical computers, 1 running Linux, 1 running Windows. My biggest gripe with Windows is that I don't like the level of integration between the OS and the applications. IMO, it is this level of integration that has lead to all the security problems, and it is what enables an application to crash the entire system. I want my OS to be an OS, no more, no less.
I've been reading all the "requirements" lists that have been posted, and I shake my head. Unless someone steps up and says, "ENOUGH", this project will be killed by feature bloat before the first line of code is written. Now, you could say that this is just brainstorming, and that's fine, as long as someone steps up and says so. But, at some point, a small group of people needs to gather all these suggested features, and whittle it down to the absolute essentials for an initial release. This is a tough thing to do, and there will no doubt be disagreements about what is essential, and what isn't.
I've seen too many first release projects killed by feature creep. I've even been involved in one where all the senior designers (including myself) wanted to build a Chevy and push it out the door, but the architects kept convincing the powers that be, that a Cadillac was required. The project was killed because we were way late, over budget, and missed the market window. If we kept to the Chevy, it would have met the customer's needs (if not their perceived requirements), and we would have been first to the market.
Just thought I would throw that out there, to kind of reel this thing back in a little.
...Mike
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
This will be a simple 'command-line' program; reads all inputs from files,and produces another file as it's output.
It works with a _single_ type of material in any given run.
It assumes all input is: (a)syntactically correct, and (b) rational
INPUTS: 1) Inventory: A list of available material to cut pieces from. Each item consists of W and L dimension, and a quantity. there is a 'special value' for indicating an "infinite" resource. 2) Targets: A numbered (implicitly or explicitly) list of pieces to be cut. Each item is described by a W and L dimension, _and_ a flag as to whether the item can or can *not* be 'rotated' (For simplicity, if there are multiple items of the same dimension, they are listed individually.)
3) Parametric settings: A) Material lost to a cut (the blade 'kerf') B) "Oversize" adjustment -- either an absolute amount, or a percentage,      by which pieces are "rough cut" larger than specified, to allow for      later finishing to actual specified dimension. C) "Goals" The "percentage waste" points at which the program should      output a set of results. A series of increasingly tighter tolerances      the program should try to meet -- e.g. 50%, 30%, 20%, 15%, 10%, 7%, 5% D) "Time Limit", the point at which the program 'gives up', and outputs      the "best match found so far", *IF* all the goals have -not- been met.
OUTPUTS: 1) List of items from inventory used: W and L of the inventory item      W and L of each 'target' piece that comes from this inventory item.      H and V 'offset' (from starting corner of inventory piece) for the      starting corner of this 'target' piece. The sequence of 'cut' operations required,
CORE LOGIC:
MAIN PROGRAM: 1) read all inputs into internal data structures 2) initialize goal-seeking function     set time-limit     set current_goal to 1st goal value 3) invoke GOAL-SEEKING function 4) invoke OUTPUT function for saved 'best arrangement' 5) EXIT program
GOAL-SEEKING function: 01) set 'best prior arrangement' to "infinitely bad" 02) WHILE (any goals not met AND time-limit not exceeded) 03) examine next arrangement 04) IF less wasteful than best prior arrangement 05) save percentage waste factor for current ("best") arrangement 06) save current ("best") arrangement 07) IF less wasteful than current goal 08) invoke INTERMEDIATE-OUTPUT function 08) IF current_goal is tightest-tolerance goal 09) EXIT goal-seeking function 10) else 11) set current_goal to next tighter tolerance goal 12) END WHILE 13) EXIT function     
INTERMEDIATE_OUTPUT function: 1) open scratch file to write at beginning of file 2) write timestamp to scratch file 3) write 'start of arrangement' header to scratch file 4) write 'percentage waste' value for saved arrangement to scratch file 5) write saved 'best arrangement' to scratch file 6) write 'end of arrangement' footer. to scratch file 7) close scratch file 8) EXIT function
OUTPUT function: 1) write 'start of arrangement' header to primary output 2) write 'percentage waste' value for saved arrangement to primary output 3) write saved 'best arrangement' to primary output 4) write 'end of arrangement' footer. to primary output 5) EXIT function
========================= COMMENTS: The program obviously 'generalizes' to handle multiple 'kinds' of items, simply by making multiple passes, processing a single kind in each pass.
Trivial input enhancement to allow specifying a 'quantity' of a particular 'target' piece is *deliberately* excluded. whatever 'front-end' generates the list will be responsible for expanding any such "multiples".
*ALL* the 'hard stuff' is the 'goal seeking function'.
First enhancement would be some 'statistics' reporting: total sq. ft. used from 'inventory'. % waste etc.
Obviously, it is 'trivial' to add a 'cost' component to inventory items. and report a total cost at the end. Enhancement includes "cost of pieces", "cost of waste", "cost of stock returned to inventory", and "cost of scrap". "billable cost" would be 'cost of pieces' plus 'cost of scrap'.
A _separate_ program will take a generated cut-list, and do a "pull from inventory" operation, reducing inventory by the 'items used'. and adding any unused off-cuts back into inventory. It'll need saved parameters for minimum 'usable' stock size. anything below those minimums (length, width, and/or 'area') gets put in the 'scrap' list.
Another separate program will do "add to inventory", for items purchased.
*EVENTUALLY* 'inventory' _and_ the 'target' list are probably going to be implemented as "database". That lets people 'transparently' stick whatever other data desired onto the items, _without_ any impact on _this_ program.
WISH-LIST (*WAY* down the road): To be able to include "defects" in the 'inventory item' descriptions, and have the program 'work around' those defects, when doing the layout. this is pretty much irrelevant for sheet stock, but significant for lumber.
It complicates the goal-seeking logic _somewhat_ -- in that it's now not just fitting rectangular pieces into simple rectangular 'container objects'.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Robert Bonomi wrote:
< snip >

I've written a 2D nesting program that nests non-rectangular shapes in rectangular areas. I can provide some help in this area, if you want. It really is not all that difficult. A defect would simply be considered as an area where something was already nested.
Remove the NOT from my address, if you want to communicate with me.
--
BambiKiller #3, BS #214, DogMasher #1

01 FLHTCUI <-- Black
  Click to see the full signature.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
snipped-for-privacy@host122.r-bonomi.com (Robert Bonomi) writes:

Inventory should include Width, Length, Thickness, Species, Type (lumber, plywood, osb, etc), and grain direction and perhaps an indication of quarter, flat or plain sawn.

Target should include Width, Length, Thickness, Species, Type and grain direction.

Iterative algorithm. Aren't there already some better algorithms in the public literature? DAGS pentominos.
How is "less wasteful" quantified?
scott
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Scott Lurndal wrote:

Put your inventory in XML or otherwise use XML for the intermediate format. 90% of your parsing and sorting work is already finished for you then.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

Thickness, species, type, and 'indiction of quarter, flat, or plain sawn' are _irrelevant_ at "Phase I"
READ THE SPECIFICATION -- "it works with a _single_ type of material..."

For reasons identified above, at "phase I", 'thickness, species, and type' are *irrelevant*.
As such they are *deliberately* omitted.

The 2-d packing problem is known to be NP-complete. It is _not_possible_ to write a finite algorithm to come up with the 'best' solution.
You are left with "try it and find out" approaches.
The *ONLY* way to tell which of two (or more) arrangements is better is to _compare_ the candidates.
The postulated 'better algorithm' applies _only_ to the selection of the "next arrangement" to be evaluated

The total surface ares of the stock removed from inventory is broken down into three components: area of desired pieces area of off-cuts big enough to return to inventory area of 'scrap'
The smaller the total area removed from inventory, the the less wasteful the layout.
For "equivalent" demands from inventory, the one with the smaller amount of 'scrap' is preferable.
By design, one makes the 'less wasteful' evaluation a _separate_ function, so that anyone can 'relatively trivially' swap out any provided methodology for one that meets _their_ 'individualized' needs.
For similar reasons the selection of the 'next arrangement' to evaluate is also modularized -- allowing one to insert a 'better' routine, if/when it is developed, and/or *test* different selection algorithms.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
[SET MOOD = PLAYFUL]
On Thu, 11 Dec 2003 08:27:24 +0000, snipped-for-privacy@host122.r-bonomi.com (Robert Bonomi) brought forth from the murky depths:

Hah, with THIS group? (He make joke, Davey)

This is especially helpful with axe cuts. 5 settings oughta do 'er. Thin kerf, regular kerf, wide kerf, chainsaw kerf, and axe kerf.

Like determining OSB grain direction?

"I'm sorry, but the waste level on this project is 100%. What did you expect when using jum^H^H^Hpineywood?"
-------------------------------------------------------------------- I sent in my $5, so * http://www.diversify.com/stees.html why haven't I been 'saved'? * Graphic Design - Humorous T-shirts
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

[SET RESPONSE = "appropriate to questions"]

Nah! Only 5 is woefully inadequate.
Gotta consider the size of the blade for circular saws -- a 48" dia sawmill blade takes a MUCH bigger cut than a 10" WWII thin-kerf.
For chain-saws, it depends on the size (width) of the chain.
As for axes, it is *obvious* that you have to allow for a 'bit' more losses with a double-bitted axe than a single-bitted one. *snicker*

That's _trivial_! "BY DEFINITION", grain runs the 'length' of the stock. If you want it running across the 'short direction', you just define the piece as having a "width" that is greater than the 'length'. "No problemo."

100% waste, or more is _not_ unheard of. If you figure 'waste' as size of off-cuts and scrap vs size of 'needed' pieces.
Trivial example. You need a 2'x2' piece of ply, and all you have is full sheets.
28 sq ft of 'waste', vs 4 sq ft of 'needed'.
"waste level" is SEVEN HUNDRED PERCENT (!!) <grin>
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Robert Bonomi wrote:

Crikey. Looks like a good recipe for a logical, focused beginning, but I can also clearly see that I am *way* out of my league here.
Maybe I would be better equipped to hack on the eventual front-end for this thing.
Run with it, please, by all means, but I don't think I have anything useful to offer at this stage.
--
Michael McIntyre ---- Silvan < snipped-for-privacy@users.sourceforge.net>
Linux fanatic, and certified Geek; registered Linux user #243621
  Click to see the full signature.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Robert Bonomi wrote:

wow, I'm beginning to think this might even work with a CNC machine. You know that router thingey that slides around and cuts panels, then spits them out as furniture.
Great first Draft, think I'll sit back and watch the progress in amazement. I can do a lot of things but my mind sure don't work like that.
Rich
--
"You can lead them to LINUX
but you can't make them THINK"
  Click to see the full signature.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

Related Threads

    HomeOwnersHub.com is a website for homeowners and building and maintenance pros. It is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.