Shape generator help (Armin Hofmann's 'rubber band' shape generator)

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

13 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 =)

Hello @abk,

Thanks for this topic!

My initial efforts:

Hofmann 1 0 0

The rest will have to wait for a rainy day.

:)

2 Likes

I am selecting them manually for now… using the right mouse button to select 1 of 4 lines to join them and storing these selections in an array.

Manually plotting may help me see patterns and work towards an algorithm later to automate this.

I only used trigonometry for the tangents and angles with PVectors for tracking and plotting points. That was the easy part for me…

This diversion is on the backburner for now but worthy of further exploration.

:)

1 Like

Hello @abk,

Can you elaborate?

I am aware of this book but have not seen the content:

It states:

… this new edition is divided into computer-system-friendly sections. Thus adapting Hofmann’s methods to the requirement of modern design practices and serving as a valuable handbook for a new generation of designers.

:)

1 Like

Yes that is a great book for figuring out basic graphic patters that can easily be remade with processing/p5. The one posted here might be one of the more complex though.

Great work. One question (please).

I think I could select a permutation of a number of circles from the set of circles. No problem.

I also think given any number of circles I could make the nice shape that contains them. I would take a very different approach to yours, but I am not so clever.

My problem with the complete puzzle (@abk) is how to avoid the ‘rubber band’ crossing itself. Did you solve this, or do you have any likely solutions?

The intersection problem almost needs to be a topic on its own!

Hi, I actually gave it quite some thoughts but gave up after some times. I’m at the same point as in my 07/11/21’s answer.

I agree that this question could be a problem on its own.

To sum up my thoughts:

  1. Keep generating shapes until one is not self-intersecting. I wrote that the algorithm is not that trivial but it is just some line/line intersections and line/arcs intersection to be done. But as I wrote, it seems quite rare to find a non intersecting shape randomly and the method is quite inefficient.

  2. Find a more systemic approach. This is where I spent most of my time thinking. My idea was the following: start with just 3 circles (it always works) and find a way to identify in which area of the plane we could pick a new pin without creating any self intersections and then pick one randomly from that zone. Repeat the same process over and over until the desire number of pins is added. Sadly I could not figure any way to compute the “OK” zone easily.
    To define that safe zone, I started to think about the simple shape created by connecting the center of each selected pin instead of the more complicated one with the arcs. Then on a piece of paper I was mapping the safe zone for different scenarii and trying to find common rules but no luck so far.

  3. Instead of generating random shapes, the pins could be manually selected by the user. In this case no need to check for self intersection, the user would do it itself.

Anyway, if you find some insight on this problem, I would like to read it. Maybe I’ll go back to think about it.

2 Likes

Instead of thinking about the discs, one could think of the rubber-band closed path that is also the perimeter of the filled shape.

This path is made from a number of shorter paths. It’s a bit like a child’s railway track.

These paths can be in one of three states, available to use but unused, unavailable to use and unused, or used.

As soon as some paths have been picked and used, this makes some of the yet unused paths unavailable.

So, when you switch a path on, the code also switches some paths to unavailable.

Light blue: available and unused.
Green: used.
White: unavailable and unused.

1 Like

Could you please elaborate?
I fail to see how it can produce the shape at the end.
What are the rules to deactivate the connections when one is turned on?

1 Like

Apparently you can make quite a lot of money with this kinf of generative art :sweat_smile:

2 Likes

Today I came across Dubins paths and remembered this thread. They seem describe exactly the same problem, and Dubins path are a well studied topic in the field of (robotic) motion planning.

In geometry, the term Dubins path typically refers to the shortest curve that connects two points in the two-dimensional Euclidean plane (i.e. x-y plane) with a constraint on the curvature of the path and with prescribed initial and terminal tangents to the path, and an assumption that the vehicle traveling the path can only travel forward.

In 1957, Lester Eli Dubins proved that any such path will consist of maximum curvature and/or straight line segments. In other words, the shortest path will be made by joining circular arcs of maximum curvature and straight lines.


On github, there just was a single well-stared (C++) library for Dubins curve generation (all Java repositories were hobby projects at best). So I’ve just ported it that library to Java and it’s available here:

@jb4x Perhaps this would make your code simpler? To find the rubber band between two pins all you’d have to supply is the pin coordinates and the heading angles (one of N,S,E,W I believe).

In time I’d like to have a go myself at applying this library to the grid of circles to generate the shapes.


The shortest dubins path between two points (fixed terminating heading angle).
dubins2

All possible (6) dubins paths between two points.
dubins

Dubins curves are similar to Reeds-Shepp curves, only that the Reeds-Shepp “car” can move reverse, so some paths are shorter:

3 Likes

Reading this back again I realize there’s an obvious approach regarding the arrangement of the pins, and it happens that some fine gentlemen of this forum already discussed it here.

If you consider the set of selected pins as a collection of nodes in a graph then generating a “valid” shape amounts to finding a possible non-self-intersecting Hamiltonian path that is cycling through them.

While not perfect this method has 2 benefits:

  • deterministic aspect: it mitigates randomness, no need to generate different orders/arrangements of pins by trial and error as the procedure will find a solution for a given set.

  • combinatorial aspect: because it will traverse a graph and explore its different branchings the procedure will output, not one, but all the solutions to a given set.

Steps:

  • Randomly select a specific amount of circles/pins from a grid
  • Find all non-intersecting lines between all pairs of circles (center to center). Consider those selected lines as the edges of an undirected graph.
  • Create an adjacency matrix representing the topology of this graph.
  • Traverse the graph and find all Hamiltonian cycles that aren’t self-intersecting on a 2D plane. A cycle is an ordered list of indices that will pave the way for a possible Dubins paths.

Taking the example set of pins (in any order) chosen by @jb4x earlier, this algorithm will output the following:

The shape made by jb4x can be spot at position B10. All the rest are the other possible path combinations given the same set of nodes.

Now for fun, displaying just a portion of the solution space for a set of 16 nodes (whole 4x4 grid):

A few notes:

  • I’m creating a graph whose edges are the center lines between pairs of circles. Normally one would choose the internal and external tangents instead. However doing so would create an adjacency matrix too large to be processed in reasonable time (not because of the number of tangents but because of the number of tiny small arcs that would create around each pin as a result) . As a consequence some edges create connections between pairs of circles that normally couldn’t be joined by tangents. This will sometimes result in Dubins paths slightly intersecting themselves. In this case, either discard the solution or reduce the radii of the pins.

  • It’s often said that one of Hofmann’s rule is to wrap around each circle once and once only. I believe this is not true. If you look at the examples provided in his original publication (sample image at the top of this thread) you’ll see that one of the shapes (top right, middle row) has a pin that is wrapped around twice. This is not trivial as it means one would have to come up with a different / more specific set of rules. In that case, using a grid system with pins of different sizes may be useful.
10 Likes

Hello!
Could you please share the code? I’m too dumb to understand how to do it myself :smiling_face_with_tear:

1 Like

Hi @JoWood,

Sorry for the late reply, I’m swamped with work lately and don’t have much time to check to forum.

I won’t be posting the full code here but if you share some of your attempts and clarify which part is giving you a hard time we can sure try to help you achieve your goals.

Also no one is “dumb”, just:

  • don’t be afraid to ask questions (I do ask a lot of questions myself)
  • and give you some time to digest the answer

Hope we can help.

PS: I see what you did with your PP :wink:

3 Likes

How do you offset the Start [x,y], End [x,y], and tangents so they wrap around the circles?

With all the versions I’ve read about and seen examples of online for Dubins Path there is a Start Point and End Point with their respective tangent directions. However, I haven’t been able to work out a consistent way to get the path to wrap around the circles instead of the center of the circles. Any tips from much smarter people than myself?

This is a simplified version but I’d like to expand it to a grid.

Rather than connecting circles think about the problem in terms of connecting pins on the circles. Each circle has 4 pins located at N,S,E,W on its perimeter. These are the coordinates dubin’s paths expect; the paths will wrap the circles automatically once these are given.

So the problem is no longer which circles to connect, but which pins between successive circles on a chosen circle sequence to connect.

To illustrate, your example would connect the W pin of the leftmost circle to the S pin of the other circle with a RSR dubin’s path.

It also looks like your path’s radius is twice as large as it should be (probably using circle diameter rather than radius for the path radius).

2 Likes