Grasshopper

algorithmic modeling for Rhino

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).

cb

Views: 8241

Attachments:

Replies to This Discussion

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?!? ;-)

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 :

1. a closed curve on XY plane and
2. 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:

Hi Laurent!

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.

Cheers,

Christian

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:

Thanks a lot!

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

Cheers!

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:

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

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 ?

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?