Find the largest possible rectangle inside an irregular closed curve

Hello,

I'm working through a uni project in which I'm trying to optimize a form based on program spaces that need to be placed inside. I'm having trouble with testing the form based on the program spaces, which will need to have specific dimensions and proportions.

In short, I need to do one of the following:

1. Find the largest possible rectangle at any orientation that can fit completely inside a specified blob-like curve.

2. Given a specific size and shape of rectangle, can it fit inside a specified blob-like form from any orientation?

I first came up with a method for finding the largest possible rectangle within a specific form that was much more regular (attached as FindAreaRect.gh), but I've since moved on to other more irregular geometries, and so far it won't work when applied to an irregular blob with possible holes (attached as MetaballBlob.gh).

Thanks in advance for any advice!

Attachments:

FindAreaRect.gh, 22 KB
MetaballBlob.gh, 14 KB

Replies to This Discussion

Permalink Reply by David Rutten on February 14, 2015 at 2:11pm

There is no straight forward algorithm for doing this. Finding minimum bounding boxes is reasonably doable (especially in 2D) because you just have to sample a couple hundred times, then improve upon the best answer.

But fitting a rectangle inside a shape is much harder as there are many more possible positions. There's also no quick way to test each state, as is the case with bounding boxes. You'll need to perform expensive curve|curve intersections, slowing down an iterative process even further.

Finding a large circle in a shape is somewhat more doable, as you can use Delaunay meshing:

Attachments:

findlargestcircle.gh, 27 KB

Permalink Reply by Christopher James Botham on February 14, 2015 at 7:46pm

Thanks David, this is really interesting. I see the complexity behind adding in scale and rotation, so this seems like the better way to look at the problem.

Thanks again!

Permalink Reply by Daniel Fink on February 15, 2015 at 2:20am

It's not so trivial even for convex polygons:

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

Permalink Reply by peter fotiadis on February 16, 2015 at 4:25am

That's very interesting. Since I have already a convex hull (see that working in parallel with a del mesh script) algo I'm going to convert Java to C# ASAP.

thanks for sharing the link.

Attachments:

Convex_hull_and_del_mesh_V1.gh, 305 KB

Permalink Reply by peter fotiadis on February 16, 2015 at 12:33pm

Find some time to convert the java (pointed by Daniel above). I believe that tomorrow I'll post the C# thing for GH.

Permalink Reply by Riccardo Majewski on February 15, 2015 at 7:23am

I tried with kangaroo, but no luck.

My idea was filling your shapes with random positioned and oriented small rectangles;

then "growing" them with iteration, keeping the 4 angles of the rectangles at 90° and keeping rectangles inside your shapes (with particle inside brep/mesh);

finally keepeing the 4 sides of each rectangle to interact with your shape borders, but somehow lineline component is really too heavy for my cpu or I'm using it really bad... btw very ugly results..

(rectangles "gluing" to shape etc....)

Now I'm trying with direct approach, no iterations, just math (fear!)

I needed quad points (those points where inclination of the curve is m=0...

But as I haven't find any other method, I built my own:

I "bended" the derivative graph from an XY Cartesian space to a "rolled up" torus space (what?! is this even correct?)

With quad points every 90° I can now rotate "evaluating plane" (for quad points).

For now I'm here:

I'm trying to continue, I'll keep updated here!

(there are already tools for oriented curve "quad" points? Mine weight alot....

Christopher, for now I can tell you...

For "my method" and maybe also others... you would probably need to rebuild and simplify the meatblob resulting curves...

Them are 1° grade polylines with (really) too much points/control-points....

I think any method will suffer with this huge amount of points.

And specifically for my method, it needs a smooth nurbs curve.. where the curvature graph is also well smooth... 1° grade curve will never work with my method XP.

Also what is the difference between your 1° and 2° question/point?

Won't solving 1° be enough also for 2° ?

Permalink Reply by David Rutten on February 15, 2015 at 9:50am

How about you use bounding boxes to find interior rectangles? You'll have to 'invert' the actual curve, so the inside becomes the outside, and those points nearest the rectangle seed will be furthest.

Permalink Reply by Riccardo Majewski on February 15, 2015 at 10:00am

Ugh.. sorry... I can't follow what you said.. XP

Invert the curve?

You mean something related to this?

https://spacesymmetrystructure.files.wordpress.com/2007/08/stanford...

Some of my neurons suggest me what you aim to... but I can't picture it...

Wouldn't the bounding box created be again "inverted"?

So we have to flip it again and it become .... a "star" "quatrefoil"?

I'm going random...

Permalink Reply by David Rutten on February 16, 2015 at 4:51am

Never mind, I was wrong. I forgot that inverting a box will turn all edges into circular arcs...

Plus the green shape sometimes still pokes out of the red shape, so clearly even the wrong logic doesn't work all the time...

Attachments:

inversion.gh, 11 KB

Permalink Reply by Riccardo Majewski on February 16, 2015 at 5:51am

btw, thanks for attachment... every small portion of code is useful...

nom!

like now, I need a "method" to find the largest possible rectangle, starting from an array of lines; my output lines are grouped by "orientation" (a line for the bottom of the rectangle will never be used for top (does this have sense?))

for rectangle solution {orientation[4branches]; possible line for every orientation}

for triangle solution {3;x}

for pentagonal solution {5;x}

etc

and probably finding a good method for this next step will require c# or similar...

(I need something similar to "CreateSolid" command in rhino, but to work in 2d with lines...)

Permalink Reply by Christian Assmann on May 27, 2016 at 3:15am