Geometry Algorithm

Hi all,

I had a geometry algorithm which has to been implemented in Java or PHP. I had no idea at all. Might I seek help from you.

Problem:
I have an irregular shape, such as star, circle and any shape you can imagine and a large rectangle. I will place several irregular shape (same shape) on the large rectangle.

How many irregular shape can be placed on the rectangle in Maximum?

What information do I need first? such as width and length of Rectangle, and what else?

Please advise.

thats an impossible question - it depends completely on what shape it is, how well they tessellate, how tightly they can be packed and finally on the rectangle itself. Can the shapes be reflected or rotated?

The best I think you can do is find some approximations like "it can definitely fit at least X but definitely no more than Y" That wouldn't be too hard.

After investigation, this problem seems as an NP-completeness problem.

My way will be

- Given all irregular shape is the same in shape and size
- Given all irregular shape's dimension is known
- Given the rectangle's dimension is known
- Given all irregular shape can rotate but not flip
- Consider the irregular shape is a polygon

Steps
1. Start 1 irregular shape
2. Pack it on the rectangle from the corner.
3. If Step 2 is possible, then keeping the previous pattern, add 1 more irregular shape and repeat Step 2.
4. else stop and return the previous pattern.

What do you think about? But even if it is possible, Step 2 is still a big problem, how can I solve it?

I think this is an amazing alg to bite into for sure.

I agree I would take the first item and put it in a corner. After that I might disagree though.

Have you thought about recalculating the area again of the "board" you are putting the item on. If you recalculate, based on the fact that you cannot put another peice there, you come up with a new board. I would then figure out where the smallest possible place is to put the next peice.

Realizing you will always have small portions of the board not getitng used so you want to minimize those small portions.

When I get a few more minutes I would really love to hash out more about this for sure. Hopefully by this weekend.

md

Well I showed the problem to one of my friends and he informed me that he would certainly use a genetic algorithm. More information can be found at URL The third page actually contains information which is somewhat close to the problem you were discussing.

Thanks a lot for providing information of Genetic Programming.

Sorry for my fool, I could not understand the principle fully. Can anyone simply explain it, please?

Regarding to testing the positions of all shapes in each round, I think it would degrade the performance and seems impossible to run. Even for three shapes, there are too many combination on a rectangle. What should we do?

your goal should be to leave the smallest possible unused space. It is hard to describe with words but say you have a square and you are putting it in a rectange. You would want the square to go all the way into the corner. This would leave no extra space on two sides of the object but will leave extra space on the other two sides.

My friend Darren told me to tell you

"A genetic algorithm provides a solution through trial and error, where intermediate solutions that are closest to solving the goal are built upon, combined, and mutated to potentially get the algorithm closer and closer to an optimal solution.. GAs really scale well with large solution spaces, and while they might not stumble upon the #1 optimal solution, they can give a very very close approximation."

This does nothing to get you closer to your answer, but I wanted to say I am impressed how you guys dug in on this. It's a tough problem, I remember only a couple of years ago someone finally made a proof of the most space efficient way to stack oranges. 1 extra dimension, but the same problem I guess, just least leftover space. Anyway, certainly makes the forums an interesting read.

GA sounds the best solution for this problem.
But how can we find out a "trial and error" strategy?

For example in this case, where should we begin? You know, some various shapes need to rotate to test itself. What do you think about that?

I would personally select a corner, lets say bottom right just for fun.

Next we have to think about rotating the object, remembering our goal is to have the least amount of wasted space on the bottom and on the right hand side of the object.

Define "wasted space" - wasted space would be space smaller than the object. Meaning we could not put another object in there. NOTE: this means there could be wasted space to the top of the object and to the left of the object as well if the object is large compared to the rectangle it is put in.

You will want to rotate the object 360 degrees while testing the area of wasted space at each degree (well unless the object is a circle or some other object which is the same on some sides, then you wont need to test as much).

However, to start the alg I would personally just keep the object as you get it and then mess around with rotating it later. Although, the GA would help greatly in this in that it would figure out if rotating was helping or not.

I hope this helps you with a starting point though.

Well actually your problem is part of the bin packing concept. It is definetely a NP complete problem that cannot be solve by itself.

The only real way to do it is to use the no fit polygon concept which is as follows.

Consider a static polygon with n facets P1 and a moving polygon with n facets P2. What you want is to get the closest position between P1 and P2 without any intersection while one or more point of P1 will touch one or more point of P2.

The concept is pretty simple, Move along the vectors of P1 the Polygon P2 keeping track of the position of one of the P2 vector point. Log in each point as you move the P2 polygon.

When you have moved P2 along all the P1 vectors, link sequentially all the points you have loged in. This new polygon P3 is the no fit polygon.

You can now move the P2 polygon anywhere on this P3 polygon using the P2 vector point you use as your login point.

To find the most optimal position, you can calculate the overall rectangular surface or use other concept to determine the most suitable position.

Just forgot.

You cannot rotate the P2 polygone during this process. You will to restart each NFP process with the P2 rotated with some angles.