Finding the biggest rectangle in a spline with galapagos

hello fellow grasshoppers,

I’ve started a grasshopper course at university, and our first task is to draw a random closed spline (2D) and let galapagos find the largest possible rectangle that would fit in that area.

Only problem is while the professor started explaining some steps I was at a job interview and now I dont even know where to actually start or go. Watching the introduction videos by david rutten didnt help much.

It should be a fairly simple solution, since its the first task of a basics course.

Anyone could help? I would love to get into grasshopper so much as to return the favor and help others with their problems.

Thanks in advance!

Hello,
you have 2 choices or we do the job for you and you learn nothing or you do it. I prefer the second option, but I can say you this question was already asked. So you can search on this forum and old grasshopper forum and you will find some scripts and strategies. It is not a so simple task. Search with inscribed rectangle grasshopper
Not always Galapagos here but could help




2 Likes

Wow, they throw you in the deep end right away don’t they?

1 Like

Pretty much all problems that involve Galapagos are approached the same way. First you set up a bunch of sliders that together can create a specific solution (in your case, a rectangle in the XY plane). There’s various ways of doing this, for example:

  • Use 6 sliders, each of which sets a single coordinate x or y in 3 points. To slider 1 is used to control the x-component of point A, slider 2 controls the y-component of point A, slider 3 controls the x-component of point B and so on. Once you have three points you can create a rectangle using the Rectangle 3pt component.
  • Use 5 sliders, and this time slider 1 and slider 2 are used to generate a single point somewhere in the XY plane. You create a plane centred at this point. Slider 3 is then used to rotate this plane around the vertical axis. Lastly, sliders 4 and 5 are used to set the width and height of the rectangle. There’s a component called Rectangle which creates a rectangle from a plane and width/height intervals.
  • There’s more ways to create rectangles, really, lots of ways.

You need to pick one. Ideally you’d pick a method which has clearly defined outer limits. For example the 3-point approach can actually generate some pretty unexpected outcomes, so probably the plane+rotation+width+height approach is better.

Once you’ve picked your method, you then need to set your slider limits to be big enough so that the right answer is definitely somewhere inside the currently possible states. Galapagos will only search within sliders, it will not automatically extend the search domain.

Good, you’re almost set, you have a file which can in theory generate the correct answer, except nobody knows what exact values the sliders need to assume to get this answer. This is what Galapagos does; it twiddles all the sliders trying to find better and better answers in a way that is more efficient than just trying all possible combinations, which could easily take years.

The last thing you have to do is make Galapagos understand the problem. It’s really stupid, and doesn’t understand anything about geometry or intersections or areas or whatever. All it knows is that it can twiddle sliders, and that either leads to a better answer or a worse one.

In this case, you have to set up a fitness function which allows Galapagos to validate and compare different slider values. You’re looking for the biggest rectangle, so the fitness you’re maximising is just the rectangle area. However you only want to consider rectangles that are fully on the interior of some curve. So you also have to figure out whether your rectangle and your curve intersect. If they do (that is, if the number of intersection points is bigger than zero), you want to reject that solution entirely.

I would implement this second goal as a subtraction of the area. So let’s say you have a rectangle of area 500 but it intersects the curve in two places. The final fitness is then 500 - 2*\text{one-million}. It’s a fitness penalty, and it has to be so big as to dwarf the area contribution.

2 Likes

Seems like it to me now but I don’t want to blame the professor.
He explicitly said the first three lectures/tasks will be relatively hard to the rest of the semester because although we start at zero we move pretty fast forward, so I’m sure I wouldn’t be that stuck if I would’ve followed the whole lecture.

Thank you very much! I really appreciate the time you put into this.
I’ll let you know when I solved this.

Greetings from Austria.