[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
?
Solved

Fill an Area with 4 differnet size rectangles (in a random order) [1000 points]

Posted on 2002-06-17
5
Medium Priority
?
444 Views
Last Modified: 2007-12-19
I have 3 squares and 1 rectangle with these sizes:

200 x 200
300 x 300
400 x 400

and 1 rectangle

200 x 400

What I need to do is given a larger rectangle which will always change, fill it with random amounts of the above four shapes in random orders. I would need to be able to change the shapes from time to time as well (they will always be square or rectangles though).

Does anyone have any idea how I can do this?  I am not looking for code, just some pointers.



0
Comment
Question by:gegege
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
5 Comments
 

Expert Comment

by:jamanat
ID: 7087732
-------  ----  ----  ----
|  A   | | B | | C | | D |
|------| |---| |---| |---|

Now above are the figures you gave A(rectangle) B,C,D(squares) right? suppose you have a larger rectangle F.
   Here are some of the questions:
  1. F will always change it's size and position?
  2. A,B,C,D has to perfectly fit in F? or partially will do?
  3. Do you need to fill F completely? or some open space will do?
  4. overlap of A,B,C,D is ok? or there shouldn't be any overlap?

  Final question, do you need logic for filling F? or you need logic for creating F also?

  I may be able to think if you answer these questions.. thanks.

Jamanat
0
 
LVL 1

Author Comment

by:gegege
ID: 7087832
hi jamanat,

1 - F will be different, I will let the user decide the actual size, but I am going to say it will always be a rectange.

2 - They don't have to fit perfectly, they can go outside of F, but by the smallest amount possible

3 - I need to fill it completly

4 - there can't be any overlap - but if it is not possible that the shapes fit together (as one is 300 (as opposed to 200 or 400) and so they won't be even) then it is possible to cut the shapes but I would like to avoid this as much as possible.

I just need the logic for filling f.

thanks, I am really not sure how to do this so any help you can give would be great.
0
 
LVL 1

Author Comment

by:gegege
ID: 7096529
any ideas?
0
 
LVL 3

Accepted Solution

by:
ygal02 earned 2000 total points
ID: 7101598
An idea (a simple to implement, but, unefficient way):
Because the sizes are pre-defined and constant, you can work on a discete grid (like a matrix).
You can actually say that the sizes are 2,3 & 4, and then multiply them by 100 after solving the problem.
So:
Lets say that the area (A) is of size NxM (after deviding it by 100).
-Create an area of size (N+4)x(M+4) at least (call it F).
-Take a random shape, try to fit the shapes into F (by tring to put each shape to the first available point it fits, scanning row by row). If it fit's nowhere, try the next shape (until trying all of them)
-When getting stuck (can't fit anymore shapes), check if there is an area in F of size NxM which is totally filled up, if yes then take it as A, if no repeat the process from the beginning.

If you will take larger F area the avarege number of repeatitions will be smaller, but each repeatition will take longer.

Good Luck.
0
 
LVL 1

Author Comment

by:gegege
ID: 7103194
yeah, i got a mate to explain it at the weekend and this is basically what he said so I think this is what I will do.

cheers
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Although it can be difficult to imagine, someday your child will have a career of his or her own. He or she will likely start a family, buy a home and start having their own children. So, while being a kid is still extremely important, it’s also …
Computer science students often experience many of the same frustrations when going through their engineering courses. This article presents seven tips I found useful when completing a bachelors and masters degree in computing which I believe may he…
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …

649 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question