CODEWITHSUNDEEP
algorithmpolygoncomputational-geometryrectangles
Zhr Saghaie
Zhr Saghaie

Reputation: 1071

an algorithm for fitting a rectangle inside a polygon

I have a kind of cutting problem. There is an irregular polygon that doesn't have any holes and a list of standard sized of rectangular tiles and their values.

I want an efficient algorithm to find the single best valued tile that fit in this polygon; or an algorithm that just says if a single tile can fit inside the polygon. And it should run in deterministic time for irregular polygons with less than 100 vertices.

Please consider that you can rotate the polygon and tiles. Answers/hints for both convex and non-convex polygons are appreciated.

Upvotes: 9

Views: 11589

Answers (3)

Darien Pardinas
Darien Pardinas

Reputation: 6196

This might help. It comes with the source code written Java

http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2003/DanielSud/

Upvotes: 2

Zhr Saghaie
Zhr Saghaie

Reputation: 1071

After many hopeless searches, I think there isn't any specific algorithm for this problem. Until, I found this old paper about polygon containment problem.
That mentioned article, present a really good algorithm to consider if a polygon with n points can fit a polygon with m points or not.
The algorithm is of O(n^3 m^3(n+m)log(n+m)) in general for two transportable and rotatable 2D polygon.

I hope it can help you, if you are searching for such an irregular algorithm in computational geometry.

Upvotes: 5

stormCloud
stormCloud

Reputation: 993

Disclaimer: I've never read any literature on this, so there might be a better way of doing this. This solution is just what I've thought about after having read your question.

A rectangle has two important measurements - it's height and it's width

now if we start with a polygon and a rectangle:

polygon and rectangle

1: go around the perimeter of the polygon and take note of all the places the height of the rectangle will fit in the polygon (you can store this as a polygon*):

where will the hight fit?

2: go around the perimeter of the new polygon you just made and take note of all the places the width of the rectangle will fit in the polygon (again, you can store this as a polygon):

where will the width fit?

3: the rectangle should fit within this new polygon (just be careful that you position the rectangle inside the polygon correctly, as this is a polygon - not a rectangle. If you align the top left node of the rectangle with the top left node of this new polygon, you should be ok)

4: if no area can be found that the rectangle will fit in, rotate the polygon by a couple of degrees, and try again.

*Note: in some polygons, you will get more than one place a rectangle can be fitted:

more than one rectangle can be fitted here

Upvotes: 7

Related Questions