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

**URL:** <https://discourse.processing.org/t/shape-generator-help-armin-hofmanns-rubber-band-shape-generator/33190>\
**Category:** Coding Questions\
**Tags:** homework\
**Created:** [October 31, 2021, 2:15pm UTC](https://discourse.processing.org/t/shape-generator-help-armin-hofmanns-rubber-band-shape-generator/33190 "2021-10-31T14:15:16Z")\
**Posts on this page:** 1\
**Showing post:** 40

<div class="post-metadata">

**Author:** ![solub](https://yyz2.discourse-cdn.com/flex036/user_avatar/discourse.processing.org/solub/32/333_2.png) [@solub](https://discourse.processing.org/u/solub)\
**Post date:** [August 6, 2024, 6:16pm UTC](https://discourse.processing.org/t/shape-generator-help-armin-hofmanns-rubber-band-shape-generator/33190/40 "2024-08-06T18:16:14Z")

</div>

@eightohnine

> … it may even be the source (or result) of this thread?

This thread predates the project you mentioned; won’t say more than that.

@micycle

> To find a valid ordering for a large amount of pegs, find the concave hull of the point set (versus finding a Hamiltonian cycle, which is very slow).

I respectfully beg to differ. This statement is questionable, if not false, on several counts:

- A concave hull is an envelope in the shape of a concave polygon that encompasses all the points. It does not necessarily have to pass through every point. The one showed in your example, however, seems to be a variant (a very special case) of a concave hull that visits each and every point in the set before returning to the starting point. Note that this is the perfect definition of a [Hamiltonian cycle](https://en.wikipedia.org/wiki/Hamiltonian_path). As a matter of fact, the special concave hull you are showing _ **is** _ an example of a Hamiltonian cycle, so comparing / opposing them isn’t really relevant.

- A “valid” ordering does not depend on any particular procedure. As we’ve already discussed [here](https://discourse.processing.org/t/random-shape-generator/28843/6), any technique that finds a non-intersecting Hamiltonian cycle is appropriate (yours included!). A few other examples could include:

 ![illu1](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/3X/0/b/0b3a2b354a34cecf8fe61b629d95e8082bcb6ecf.jpeg)

 ![illu2](https://canada1.discourse-cdn.com/flex036/uploads/processingfoundation1/original/3X/6/0/605a1d238d7ad0bd43074fd2f5c619248f56cf2f.jpeg)

- Unless your goal is to _enumerate_ a set of solutions (all possible permutations of a set of points), speed is hardly an issue. For the successive _generation_ of a single solution, the problem does not arise. Some of the techniques mentioned above are likely even faster than the one you’re presenting. Even in the case of the Shortest Path approximation and with moderately sized instances (a few thousand points), a simple metaheuristic algorithm such as [Simulated Annealing](https://en.wikipedia.org/wiki/Simulated_annealing) with just two operators (”swap” and “transport”) can find a solution in just a few hundred milliseconds (in Python). For even larger instances, you can still resort to the [Concorde](https://en.wikipedia.org/wiki/Concorde_TSP_Solver) solver ([world record](https://www.math.uwaterloo.ca/tsp/concorde/benchmarks/bench99.html): 85 900 cities / pegs in .06 seconds).

Following the popularity of this thread and a few questions I had received privately, I wrote a comprehensive blog post on the topic, which I illustrated with code and some personal work (2D/3D abstract visuals, lots of renderings, and typographic work). Unfortunately, I encountered some technical issues and this site is no longer online today. Moreover, I was bitterly disappointed to see that some of the visuals I had posted had ‘inspired’ some individuals who subsequently published strikingly similar works without ever bothering to cite their source. I have nothing against copying; in fact, I am even flattered by it, but it seems to me that referencing one’s sources of inspiration, even subtly, is a matter of basic courtesy.

I hope one day to find the courage to rebuild this website and to share this work with those who are interested.

---

_[View the full topic](https://discourse.processing.org/t/shape-generator-help-armin-hofmanns-rubber-band-shape-generator/33190)._