geometry problem

[IcyMint]

Hi, I'm trying to write a program that's able to place boxes into a
room. Basically it's an empty rectangular room with different sizes of
boxes in it. The program will need to figure out where to place the new
boxes. I'm thinking of marking out the place taken by the boxes in the
room then compare if the coordinate of the new box overlaps with them.
But now, the problem is, I don't know how to start. Can you please help
me? Thanks a lot!

 

[usenet]

But now, the problem is, I don't know how to start.

I'll be happy to tell you where to start. Start here:
http://www.augustmail.com/~tadmc/clpmisc/clpmisc_guidelines.html

 

[IcyMint]

Thanks a lot!

 

[John Bokma]

Hi, I'm trying to write a program that's able to place boxes into a
room. Basically it's an empty rectangular room with different sizes of
boxes in it. The program will need to figure out where to place the new
boxes.

If you want to do it near optimal, it sounds like 2D bin packing:

http://en.wikipedia.org/wiki/Bin_packing
http://en.wikipedia.org/wiki/Packing_problem

I'm thinking of marking out the place taken by the boxes in the
room then compare if the coordinate of the new box overlaps with them.

So you want to test if one rectangle overlaps another..

Google will give you plenty of solutions to that geometric problem.

 

[Ben Morrow]

If you want to do it near optimal, it sounds like 2D bin packing:

http://en.wikipedia.org/wiki/Bin_packing
http://en.wikipedia.org/wiki/Packing_problem

Heh

So you want to test if one rectangle overlaps another..

Google will give you plenty of solutions to that geometric problem.

s/Google/Common sense/, surely?

Ben

 

[IcyMint]

Hi John, Thanks a lot for the links. After browsing through those links
and some googling, I think my problem is the bin packing thing. Will
look for more info about it later. Thanks for your help!

 

[John Bokma]

Quoth John Bokma <[email protected]>:

[ overlapping rectangles ]

s/Google/Common sense/, surely?

Nah, some problems that look very easy have now and then very elegant
solutions that are not that easy to come up with common sense. Common
sense makes a O(n^2) bubble sort :-D

(which is not bad for small n, and might outperform other solutions, but
that's no longer common sense as in given context :-D)

 

[IcyMint]

Hi, thank you all for your feedbacks. I'm really glad to be pointed to
all the informations I needed. I think that the Geo::SpaceManager is
quite good, I'll be using it unless something better comes along.
Thanks a lot!