Pack equal sized circles into arbitrary polygon

[Tim Booher]

If I have a polygon defined by vectors X and Y and I want to
fit as many circles of radius R into this polygon. Is there
an existing algorithm for this?

Any idea on a starting place?

best,

tim

[John D'Errico]

Post by Tim Booher
If I have a polygon defined by vectors X and Y and I want to
fit as many circles of radius R into this polygon. Is there
an existing algorithm for this?
Any idea on a starting place?

http://mathworld.wolfram.com/CirclePacking.html

John

[Tim Booher]

Thanks for the link. However, I can see the results of
Mathematica code there, but no real reference to algorithms
involving circle packing.

Any links to matlab implementations?

best,

tim
message <fgohkh$guo

Post by John D'Errico

Post by Tim Booher
If I have a polygon defined by vectors X and Y and I want to
fit as many circles of radius R into this polygon. Is there
an existing algorithm for this?
Any idea on a starting place?

http://mathworld.wolfram.com/CirclePacking.html
John

[Richard Pongers]

Hi,

I'm sorry I can't help you, but I have a similar question.
I'm looking for a matlab implementation of the
optimisation problem on 'packing multiple rectangles in
larger (multiple) rectangle(s)', so that cutting losses
are minimized. I was thinking about using something
like: 'fmincon' or quadratic programming like solutions,
but I would not want to 're-invent the wheel', because I
think it's not very trivial. I'm also aware of free demo
versions of downloadable programs that do this kind of
things (for example on www.astrokettle.com), but the thing
is that I would like to do this myself in Matlab (so I
actually learn from it). Can anyone help me to get me
started?

Thanks,

Richard.

Post by Tim Booher
Thanks for the link. However, I can see the results of
Mathematica code there, but no real reference to

algorithms

Post by Tim Booher
involving circle packing.
Any links to matlab implementations?
best,
tim
message <fgohkh$guo

Post by John D'Errico

Post by Tim Booher
If I have a polygon defined by vectors X and Y and I

want to

Post by Tim Booher

Post by John D'Errico

Post by Tim Booher
fit as many circles of radius R into this polygon.

Is there

Post by Tim Booher

Post by John D'Errico

Post by Tim Booher
an existing algorithm for this?
Any idea on a starting place?

http://mathworld.wolfram.com/CirclePacking.html
John

[John D'Errico]

Post by Richard Pongers
I'm looking for a matlab implementation of the
optimisation problem on 'packing multiple rectangles in
larger (multiple) rectangle(s)', so that cutting losses
are minimized. I was thinking about using something
like: 'fmincon' or quadratic programming like solutions,
but I would not want to 're-invent the wheel', because I
think it's not very trivial. I'm also aware of free demo
versions of downloadable programs that do this kind of
things (for example on www.astrokettle.com), but the thing
is that I would like to do this myself in Matlab (so I
actually learn from it). Can anyone help me to get me
started?

This is known as a variation of the "cutting
stock problem". Google is your friend.

The solution is usually via an integer
programming solver, since you don't know
in advance how many pieces will fit into
each sheet.

John

[Richard Pongers]

"Richard Pongers"

Post by Richard Pongers
I'm looking for a matlab implementation of the
optimisation problem on 'packing multiple rectangles

in

Post by Richard Pongers
larger (multiple) rectangle(s)', so that cutting

losses

Post by Richard Pongers
are minimized. I was thinking about using something
like: 'fmincon' or quadratic programming like

solutions,

Post by Richard Pongers
but I would not want to 're-invent the wheel', because

I

Post by Richard Pongers
think it's not very trivial. I'm also aware of free

demo

Post by Richard Pongers
versions of downloadable programs that do this kind of
things (for example on www.astrokettle.com), but the

thing

Post by Richard Pongers
is that I would like to do this myself in Matlab (so I
actually learn from it). Can anyone help me to get me
started?

This is known as a variation of the "cutting
stock problem". Google is your friend.
The solution is usually via an integer
programming solver, since you don't know
in advance how many pieces will fit into
each sheet.
John

John,

Thanks for your reaction.

I already 'googled' quite a bit on this, but I couldn't
find an actual matlab implementation of any of the
suggested algorithms, but maybe I'm not such a
good 'googler' and I need to try some more.

Regards,

Richard.

[John D'Errico]

Post by Richard Pongers
I already 'googled' quite a bit on this, but I couldn't
find an actual matlab implementation of any of the
suggested algorithms, but maybe I'm not such a
good 'googler' and I need to try some more.

Were it me, I'd wander by my local university.
I'd ask around for someone with expertise in
the cutting stock problem, and ask them for
ideas.

Or, I'd ask on sci.math.numerical-analysis,
or on a mechanical engineering group.

John