Largest Rectangle Inside Regular or Irregular Shape?

[Anonymous]

I have an assignment where I need to determine the largest rectangle that can be drawn inside of any shape.

Think about these objects:

• Triangles
• Circles
• Ovals
• Parallelograms
• Irregular shapes

Does anyone know of a way with AutoCad.NET or just a general algorithm that could be used to determine the largest possible rectangle inside of any of these shapes?

Robert

[Anonymous]

for your first 4 kinds of shape, it does have some geometry algorithms, but i have not heard a general algorithm for any given curve.

[Anonymous]

Of course the irregular shapes are the most difficult to treat. I don't know of a generic algorithm, but if you can make some assumptions you may find a smart way.

For example, if the centroid of the shape is likely to lay also inside the rectangle, you may collect a number of points from the shape/curve and sort them out above, below, on the right and on the left of the centroid, finding the minumum and maximum. You should get a definite number of rectangle, not many my guess...

This if you assume the shape is already aligned with one side of the rectangle, if not, you have to rotate the shape to find the largest rectangle...

I speak of oassumption because generally speaking such requests have connection to the real world and some shortcuts or assumptions may be valid.

[Anonymous]

Thank you for your insight!  I will think about it more.

In my case I'm trying to automatically lay out rectangular solar panels on a roof.  If the roof is rectangular then of course this is rather easy but I'm trying to come up with an algorithm that will work in a more general sense.

I'm thinking that the simplest way to do this is to start laying out the panels in the center and then laying out additional ones in +x, -x, +y, & -y directions, looking for intersections with the exterior boundary.  I'm not 100% certain of this approach yet but am going to give it a try.

[Anonymous]

Ah! This is an altogether different problem! Since you have definite panel sizes, it's more a matter of 2D cut optimization. I believe you can also make use of some software already available, or maybe study some algorithm from open source c# projects and see if something may fit your needs.

You have a number of assumpion here you can use to semplify your work, like:

- solar panels are rectangular and of fixed sizes;

- panels are generally layout aligned to one side (I mean not freely rotated);

- roofs are generally planar, at least roofs where you want to install solar panels;

- roofs are generally rectangular themselves, even if some obstacles may lay around;

However, the techique I was speaking about in the previuos post may help you to find the origin of the biggest rectangles and start building a grid from there, it may even work with shaped roof, as long as the roof is planar.

Once you filled the biggest rectangle, you start again with the remaining space filling other smaller rectangles, just keeping the origins aligned to the same grid, to maintain a regular layout.

[Anonymous]

Excellent insight!  Thank YOU.