Solved

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

Posted on 2002-06-17
5
437 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
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 500 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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

RIA (Rich Internet Application) tools are interactive internet applications which have many of the characteristics of desktop applications. The RIA tools typically deliver output either by the way of a site-specific browser or via browser plug-in. T…
Whether you've completed a degree in computer sciences or you're a self-taught programmer, writing your first lines of code in the real world is always a challenge. Here are some of the most common pitfalls for new programmers.
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 …

943 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

6 Experts available now in Live!

Get 1:1 Help Now