Shape generator help

Hi

I’m trying to create a Hofmann’esque shape generator based on a grid of circles:


I have the basic structure of the grid done, but I’m totally stuck on where to go from here? How do I make this into a combined shape? Here’s my code so far:

color bg = #FFFFFF;
color fc = #000000;

void setup() {
  size(800, 800);
  frameRate(2);
}

void draw() {
  background(bg);
  noStroke();

  float tilesX = 4;
  float tilesY = tilesX;
  float gap = 16;
  
  float tileW = width / tilesX;
  float tileH = height / tilesY;
  
  for (int x = 0; x < tilesX; x++) {
    for (int y = 0; y < tilesY; y++) {
    
    float posX = tileW * x - gap;
    float posY = tileH * y - gap;
    int randomSquare = floor(random(2));
    
    pushMatrix();
    
    translate(posX +(tileW/2), posY+ (tileH/2));
    
    if (randomSquare == 0) {
      fill(fc);
    } else {
      noFill();
    }
    
    ellipse(gap, gap, tileW - gap, tileH - gap);
    
    popMatrix();
    
    }
  }
  
  //noLoop();

}

Hope that someone can help me out and point me in the right direction :blush:

2 Likes

Are there any rules? For example, the outline cannot go to the same circle more than once? Or, the outline can go to any of the other legitimate circles.

Who is Hofmann? Armin?

Yes the outline can only wrap around one of the circles once and should detect all the other visible circles and use some of the nonvisible points to wrap around as well? I don’t know if that makes sense? Image two is the desired output and the first one with the lines (that is only meant as a reference to how the logic works). Been trying to wrap my head around this for this and still can’t make it work…

Yes Armin Hofmann :slight_smile: I’m just going through a lot of his sketches to learn processing/p5.

The Processing part should be quite easy. But there are other questions before we start that.

Is the line allowed to cross itself? And, last question, how do you get the line to be a closed loop? This is deeper than it sounds. If the line went around two circles and closed like that. Is that allowed? Or is the line meant to involve eight of the circles, and so find the its end after rolling around seven.

The line shouldn’t cross itself and yes it should close around itself after the last circle :blush:

Just this to sort out. It might be important.

It’s only allowed to wrap around all of the visible circles in each iteration, so that it’s one single shape. So if there are 8 circles it wraps around all of them and not in groups of 2 and 6 for example. But if only two circles are visible then of course it’s only going to involve those 2 circles.

How is your project going? I think the first step is to choose the circles and their order. If the circles have a number (circle 1, circle 2, etc.), then we are talking about permutations. Is there an elegant way to generate the permutations of all the members of a set? - #9 by paulstgeorge

Once you have the circles and the sequence in which they will be ordered, you have the tricky problem of avoiding the line crossing itself. Do you want to do this programmatically, or will you just not use the results that do not obey your rules?

When you are beyond those two steps, the drawing should be quite easy.

I haven’t really had time to look at it during the last week. I’ve been trying to generate all the points in the circle and using a bezier curve to connect them and then from there trying to make the points connect from circle to circle. I’ll keep you posted when I make any significant progress with this :grin:

Hello @abk,

It’s been a while since you posted your original question so I’m not sure you are still looking for some answer.

If that’s the case, I finally had the time to think about it and I came up with a good solution I think. It was actually harder than I originally thought and a lot of fun to figure out.

I don’t have the time to really explain how I did it tonight, but I’ll come back as soon as possible to detail the main ideas.

In the meanwhile, here’s an example output of the program:

2 Likes

Yes! Looks amazing :blush: Can’t wait to see how you figured this out.

Unfortunately, I haven’t had time to look at it for some time, but I’m pretty sure that I wouldn’t have been able to figure it out on my own anyway.

Hello again,

Please find below the explanation of the process. I won’t share the full code as it is a huge mess but I’ll try to share relevant links.

The first step is to create grid of circles. You can play with the size and spacing of the circles but for simplicity I kept them the same size and on a strict grid as it is in the example that you shared:

Then, the idea is to select some circles that will act as pins to wrap a thread around. In that step, it is also key to define the order in which the thread will wrap around:

Once the pins and their orders are known, we can start to define in which orientation the thread will need to wrap around the pins.
The way to do it is to check the position of the previous pin, the current pin and the next pin. They form a triangle and we need to define if we traverse the triangle clockwise or counterclockwise.

An example with the pin 0. We can see that if we go from pin 10 to pin 0 to pin 1 and back to pin 10 again, we move in the clockwise orientation. We can then set our pin 0 to be a clockwise pin:

Some times, when the are aligned, there is no really defined orientation. In that case will leave the orientation and undefined for the time being:

In practice, you can use the determinant of the triangle to determine it’s orientation. If A, B, C are the 3 points, in order, of your triangle, then you can define the orientation matrix as followed:

image

if det(O) is negative then the triangle is oriented clockwise, and counterclockwise if positive.
Keep in mind that it works for a 2D space where x is pointing right and left pointing top. In processing y is pointing down so the results are reversed: clockwise when positive and counterclockwise when negative.

After doing it for all pins, we have the following result:

The next step would be to find how to connect each pin between them.

First let’s find the different tangents. You can write a piece of code to take care of all possible scenarios but since I know the circles have the same size and never cross each other, I know that only 4 tangents exists and simplified the code as much as possible.

My code is based on the second figure of this page to find the 2 green tangents in the following figure.

For the 2 red tangents, you can obtain them by computing the vector u (in blue) with a magnitude equal to the radius of the circles and with the direction from the center of the first circle to the center of the second circle. Then by rotating it -90° or +90°, it can give you the start and end points of the 2 tangents:

Now we know how to find the tangents, we need a way to select the one(s) that work(s). For this we will use the pin orientation that we determined earlier. The idea is that the tangent should go in the same direction than the pin.

If we look at the example of the link between the pin 0 and the pin 1, it is quite intuitive that only the green tangent would work:

In code, we can verify that the tangent is correctly oriented by creating a vector v (in purple) perpendicular to the vector (in blue) that goes from the center of the circle to the point of the tangent on that circle:

By construction (rotation of -90° of the blue vector), we know that this vector v is in the clockwise direction. If the pin is in the clockwise direction, then we know the tangent goes in the right direction if it is pointing the same way of v. If the pin is in the counterclockwise direction, then we know the tangent goes in the right direction if it is pointing in the opposite direction of v.

We can check if 2 vectors are heading in the same direction by taking their dot product. If it is positive, they have the same direction, if negative, the go opposite direction. It is equal to 0 if the are orthogonal.

Repeat for the end point of the tangent to check if the tangent is also valid with the direction of the second pin.

For pin without defined orientation, it means that several tangents are possible. In that case, I put them in a stack of possible tangents and picked one at random. That’s the case between pin 4 and pin 5, 2 options are possible (in green):

But once selected, it also now define the orientation of the pin. In the example below, pin 5 must now be oriented counterclockwise:

By repeating this process over each pair of pins, you end up with the final set of tangents:

All left to do is to connect the dots to create the shape. Sadly ther is no arcVertex() function so I had to create mine by approximating a circle arc with the bezierVertex() function.
I used PM 2ring’s answer for the math. What was left to do was to determine the full angle span of the arc and if higher than 90° split it in as many several parts as needed to apply the approximation on each arc section.

One thing I haven’t done is to check for the shape intersecting itself. If done you could keep generating new shapes until a proper one pop up.

Hope this help. Do not hesitate if you have any questions =)

8 Likes

Wow! Thank you so much. I’ll have a look at it this weekend.

I’m a bit unsure about how I’m going to figure out some of the math in a few of the steps. Would you mind sharing the code so that I can reference it with the detailed steps that you already provided?

And again, thanks for the help!

1 Like

This is pure gold! I like how much effort you put into this! :heart_eyes:

2 Likes

Hey thanks a lot @josephh :flushed:

But to be honest my answer is not fully complete. The one thing I haven’t detailed is the selection of the pins. In the example above, I handpicked some that I knew would work and would offer a nice variety of situations.

Lately I have been reworking my code to make it more… presentable and I had to tackle that part.
The way I’m trying to do it is to check for self intersection and generate a new shape until there are none. Two things are bothering me with that approach though:

  1. The algorithm is not really trivial to implement
  2. After generating quite a few shape I have the feeling that the non self-intersecting shapes are quite rare. Meaning it would need to generate a lot of shapes before finding a good one.

This second points is the one that bother me the most as it sounds really ineffective and I’m wondering if there would be a more systemic approach to select the pins to avoid self-intersection and generate a good shape on the first try.

If anyone has any ideas, I’ll be happy to hear it =)