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

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.
11 Likes