Solved

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

Posted on 2002-06-17
5
436 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
  • 3
5 Comments
 

Expert Comment

by:jamanat
Comment Utility
-------  ----  ----  ----
|  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
Comment Utility
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
Comment Utility
any ideas?
0
 
LVL 3

Accepted Solution

by:
ygal02 earned 500 total points
Comment Utility
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
Comment Utility
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

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
java constructor error 8 86
Fix45 challenge 15 83
hasOne  challenge 59 88
c++ reading data from file into two dimensional array 3 23
I know it’s not a new topic to discuss and it has lots of online contents already available over the net. But Then I thought it would be useful to this site’s visitors and can have online repository on vim most commonly used commands. This post h…
Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
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 …
In this fifth video of the Xpdf series, we discuss and demonstrate the PDFdetach utility, which is able to list and, more importantly, extract attachments that are embedded in PDF files. It does this via a command line interface, making it suitable …

772 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now