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 Christian Assmann on May 27, 2016 at 7:17am

Would Reccardos approach, in conjunction with an evolutionary solver and this "sequence" make sense, or would it be too hefty?

I'll try and post my findings, but if anybody has experience and foresight in the field please give a hint?!? ;-)

Permalink Reply by Laurent DELRIEU on June 1, 2016 at 2:06pm

I did begin something, surely not optimized but it could help you elaborate a solution to find the maximum.

At the moment my component in C# accept :

a closed curve on XY plane and
points.

Each point are considered as the center of the rectangle.

It outputs bigger rectangle for each point

An angle characteristic of the rectange, angle. Angle is always lesser or equal to PI/2. angle = PI/2 => it is a square.

An orientation angle if 0 the rectangle has its longer side parallel to X

The surface of rectangle.

If useful, I can add/give explanations.

Attachments:

bounding inner rectangle.gh, 24 KB

Permalink Reply by Christian Assmann on June 17, 2016 at 6:27am

Hi Laurent!

Finally had some time to play with your code...

Thank you so much!!!! What I came up with took half an hour to compute (galapagos time) and came up with pretty much the same result.

I guess it's not worth posting then.

Made my day for sure!

Cheers,

Christian

Permalink Reply by franco ferreiro on April 3, 2017 at 4:43pm

Hi Laurent, thanks for your component !!. Worked ok !, but it lacks performance for what i need... .5 sec per point is way too much for my use case ... is that what it should be ? .

tweaked some stuff around and added my tests in the attach, hope helps someone else.

Im looking for components - like this one - for tagging labels into cnc machined pieces , and also looking for solutions for nesting ("open gh definitions") and for unrolling surfaces (generic for any weird curvature :) ie by smart tesselation) if you or someone else happen to know about ...

best !

Franco

Attachments:

bounding_inner_rectangle - laurent_delrieu - FSFB tweaked.gh, 78 KB

Permalink Reply by peter fotiadis on May 28, 2016 at 12:44am

... solved/forgotten ...

rather (completely) forgotten ... but check these (a "similar" problem)

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

http://mathoverflow.net/questions/105837/get-largest-inscribed-rect...

https://www.google.gr/url?sa=t&rct=j&q=&esrc=s&sour...

http://gis.stackexchange.com/questions/59215/how-to-find-the-maximu...

http://www.drdobbs.com/database/the-maximal-rectangle-problem/18441...

And this as well

https://www.google.gr/url?sa=t&rct=j&q=&esrc=s&sour...

Permalink Reply by Christian Assmann on May 30, 2016 at 4:01am

Thanks a lot!

will try to get through 'em and post whatever I can concoct.

Cheers!

Permalink Reply by Daniel Fink on July 27, 2016 at 3:05pm

While this isn't exactly an answer to the original question (solving for arbitrary curves, let alone concave ones), I've managed to solve this for convex polygons with the rectangle aligned to any of the polygon's segments (effectively the Alt Hsu Snoeyink paper "Computing the largest inscribed isothetic rectangle"), although I don't assume its as fast as their O(log n) algorithm.

The problem is constructed as a nonlinear optimization with linear constraints, using a nonlinear (in this case Interior Point method) solver: define the variables as (x,y) origin of the rectangle, the objective as its width*height, and then the constraints are the polygon segments' Cartesian line inequations.

Thankfully the C# FuncLib library (https://funclib.codeplex.com/) provides nice representation of objectives & constraints to the IPOPT library (https://projects.coin-or.org/Ipopt) by handling all the matrix operations & determinants etc. The compiled binaries from the codeplex site are x86 only, but you can compile them to x64 using the '3.9.2' binaries at http://www.coin-or.org/download/binary/Ipopt/

I've attached the GH + C# script and x64 FuncLib DLLs. Make sure to unblock & reference the assemblies etc

Hope this helps!

Attachments:

largest rectangle in convex poly (ipopt).gh, 7 KB
FuncLibIpopt.dll, 31 KB
FuncLib.dll, 316 KB

Permalink Reply by franco ferreiro on April 3, 2017 at 2:23pm

Hi Daniel, i guess i unblocked the dll but haven't a clue on how to reference them... if it's what i think...(i would probably need to install huge MS stuff in my case - no sense in this case !-) , so could be possible for you to bundle them in an installer ? x64 ?

tnks

Permalink Reply by avi.pterodactyl on October 10, 2016 at 9:24pm

hi Daniel Fink

i am working on a UNI project and wanted a similar output as you have shown in the image. i have download the GH file and library as you have instructed after which i got the error as below.

1. An attempt was made to load a program with an incorrect format. (Exception from HRESULT: 0x8007000B) (line: 0)

can you help me fix this ?

Permalink Reply by Daniel Fink on January 16, 2017 at 12:55pm

Hi Avi

Apologies for delay in replying. I'm not sure exactly why you received the error, but it usually is a sign of 32-bit & 64-bit incompatibilities. What version of Rhino & Windows are you running?