Largest possible rectangle inside closed curve

[user23]

Hi All,

Am trying to get a continued answer to the below forum:

Find the largest possible rectangle inside an irregular closed curve

I also have a problem and cannot get the C# component to work inside grasshopper.
Are there any other similar forums?

Thank you!

[PeterFotiadis (Pfotiad0)]

@user23

cannot get the C# component to work

That’s strange: what exactly is the issue?

BTW: if the Curve is convex [or the derived Polyline - within some reasonable accuracy - is convex] there’s tons of papers/threads around.

BTW: this is the best approach (as described in the paper - Note: algorithm is O(N^3) ) so far:

How to get the largest possible rectangle contained inside polygon

[user23]

Hi There!
This is the error that i get

[PeterFotiadis (Pfotiad0)]

Well … I do hope that you know(*) how to load dll’s. Like (playing with ShapeOp):

(*) In case that you don’t search around with appropriate keywords.See this as well:

Wrapping Native Libraries

Other than that Laurent’s thingy has certainly potential (a thing or two is required, mind like get rid of the rect cent pt):

[wim (Wim Dekeyser)]

Dag Emma -

@user23

This is the error that i get

Could you upload your gh file? Make sure to internalize Rhino geometry in the Curve component.
Also, please run the Rhino SystemInfo command and copy-paste the result here.
-wim

[PeterFotiadis (Pfotiad0)]

@PeterFotiadis

Laurent’s thingy has certainly potential

Well … I did a big U turn:

1. “Pixelize” the Curve in a nullable DataTree (of type Rectangle3d).
2. By doing so get a Matrix [Rows=yRes, Columns=xRes] as well [0: null / 1: Rectangle3d];
3. Get the max Rectangle in the Matrix (that’s very easy and real-time fast: classic Matrix stuff).

Expected Elapsed time for some reasonable x/y res: 10 milliseconds max.

More after the Spanish MotoGP

[Joseph_Oster]

Find the largest possible rectangle inside an irregular closed curve

Largest ellipse inscribed in a polygon

Hello all. I am looking for a way to inscribe the largest possible ellipse in a convex polygon. With some effort looking, I have found a possible approach, as: Biggest ellipse included in a convex polygon which has code, written in matlab, that appears to work well, based off of approach suggested by chapter 8 of Boyd & Vandenberghe’s Convex Optimization Unfortunately I never have learned matlab, and am unsure how to convert this code to C or Python. Has anyone coded up an approach for this…

[user23]

Dag Wim en badankt!

Rhino 7 SR15 2022-2-8 (Rhino 7, 7.15.22039.13001, Git hash:master @ 2833e18992fc4b5cf99bb29c4d8e8add4f02074d)
License type: Commercial, build 2022-02-08
License details: Cloud Zoo

Windows 10.0.19044 SR0.0 or greater (Physical RAM: 16Gb)

Computer platform: DESKTOP

Standard graphics configuration.
Primary display and OpenGL: AMD Radeon Pro WX 3200 Series (AMD) Memory: 4GB, Driver date: 9-7-2021 (M-D-Y). OpenGL Ver: 4.6.14761 Compatibility Profile Context FireGL 21.30.18 30.0.13018.2
> Accelerated graphics device with 6 adapter port(s)
- Secondary monitor attached to adapter port #0
- Windows Main Display attached to adapter port #1

Secondary graphics devices.
Intel(R) UHD Graphics P630 (Intel) Memory: 1GB, Driver date: 4-3-2022 (M-D-Y).
> Integrated graphics device with 3 adapter port(s)
- There are no monitors attached to this device!

OpenGL Settings
Safe mode: Off
Use accelerated hardware modes: On
Redraw scene when viewports are exposed: On
Graphics level being used: OpenGL 4.6 (primary GPU’s maximum)

Anti-alias mode: 4x
Mip Map Filtering: Linear
Anisotropic Filtering Mode: High

Vendor Name: ATI Technologies Inc.
Render version: 4.6
Shading Language: 4.60
Driver Date: 9-7-2021
Driver Version: 30.0.13018.2
Maximum Texture size: 16384 x 16384
Z-Buffer depth: 24 bits
Maximum Viewport size: 16384 x 16384
Total Video Memory: 4 GB

Rhino plugins that do not ship with Rhino

Rhino plugins that ship with Rhino
C:\Program Files\Rhino 7\Plug-ins\Commands.rhp “Commands” 7.15.22039.13001
C:\Program Files\Rhino 7\Plug-ins\rdk.rhp “Renderer Development Kit”
C:\Program Files\Rhino 7\Plug-ins\RhinoRenderCycles.rhp “Rhino Render” 7.15.22039.13001
C:\Program Files\Rhino 7\Plug-ins\rdk_etoui.rhp “RDK_EtoUI” 7.15.22039.13001
C:\Program Files\Rhino 7\Plug-ins\rdk_ui.rhp “Renderer Development Kit UI”
C:\Program Files\Rhino 7\Plug-ins\NamedSnapshots.rhp “Snapshots”
C:\Program Files\Rhino 7\Plug-ins\IronPython\RhinoDLR_Python.rhp “IronPython” 7.15.22039.13001
C:\Program Files\Rhino 7\Plug-ins\RhinoCycles.rhp “RhinoCycles” 7.15.22039.13001
C:\Program Files\Rhino 7\Plug-ins\Grasshopper\GrasshopperPlugin.rhp “Grasshopper” 7.15.22039.13001
C:\Program Files\Rhino 7\Plug-ins\Toolbars\Toolbars.rhp “Toolbars” 7.15.22039.13001
C:\Program Files\Rhino 7\Plug-ins\3dxrhino.rhp “3Dconnexion 3D Mouse”
C:\Program Files\Rhino 7\Plug-ins\Displacement.rhp “Displacement”
C:\Users\emma.dehaan\AppData\Roaming\McNeel\Rhinoceros\packages\7.0\PanelingTools\2021.3.2.446\PanelingTools.rhp “PanelingTools”

largestrectangleinconvexpolyipopt.gh (6.7 KB)

[PeterFotiadis (Pfotiad0)]

@PeterFotiadis

10 milliseconds max.

Update (MotoGP FP2 was pathetic … and I hate Fabio):

If we combine this (Existed C#: Real-time Matrix max rect “area”):

With this (WIP : testing some // stuff for less milliseconds - shown very low Resolutions for inspecting the Matrix values):

The problem is rather solved. But is the 10 milliseconds goal achievable? (Rotations as shown [and a bounce solver] are obviously required). That’s the big question.

More after the Qualifying (Forza Ducati) tomorrow.

[anon39580149]

I try this , every point on the curve have many possibilities.
Maybe the idea with scripting work faster

[user23]

The solution with the blue 'x’s seem to work! Would it be possible to share this script?

Thank you so much!

[Thom_Bindels]

Dear Peter,

I am currently working on the same issue that is solved by your solution here.
Would it be possible to share the C# script that determines the max rectangular submatrix?

Thank you!

[PeterFotiadis (Pfotiad0)]

Well … I’m 1M miles away from base (summer windsurfing period not ended - more is more). When I’ll be back (when? you tell me) I’ll see what I can do on that matter.

[RadovanG (Radovan Grmusa)]

Here is one solution, brute-forse approach with precision determined by grid resolution. Curve should be closed and placed in XY plane.

1. Grid resolution is defined by number of points (gridAxisCount) along longest axis of BoundingBox of closed curve.
2. Grid resolution is calculated as
   input:
   • curve
   • gridAxisCount
     result:
     gridResolution = Math.Max(bbox.Max.X - bbox.Min.X, bbox.Max.Y - bbox.Min.Y) / gridAxisCount;
3. Bounding box of curve is now filled with grid/(matrix)/(rectangular array) of Points where x and y distance of points = gridResolution.
4. For each Point_i in grid (Bounding box) we try to construct rectangle where Rectangle.Min = Point_i and Rectangle_i.Max is one of another point inside grid …
5. Such rectangles have edges parallel with x and y axis, we keep information about the largest rectangle
   Now we rotate curve around AreaCentroid for given angle and perform tasks 1.-5. for each new rotated curve.
   Totalangle (TotalAngle) should be kept at value of 90 degrees, angle count is number of iterations.
   At the end we check for which angle we get largest rectangle, and return it as result:
   = largest rectangle (by area) for given gridResolution and given number of angle iterations
   MaxRectangleInsideCurve.gh (13.1 KB)

[paul.metzger]

Works perfectly well. Thank you! Very useful!