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:
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.
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.
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.
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?
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).
All possible (6) dubins paths between two points.
Dubins curves are similar to Reeds-Shepp curves, only that the Reeds-Shepp “car” can move reverse, so some paths are shorter:
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.
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.
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)
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).
Dubins path is a formula which describes how to draw the shortest curve to connect two points. The influential Swiss designer Armin Hofmann notably made use of these ideas in his 1965 book Graphic Design Manual: Principles and Practice to illustrate a study in variations of ‘growing, fluid structures’. In their approach, ANTI harnessed Dubin’s equation and, together with the mathematics scientist Øystein Klemetsdal and developers from TRY, ANTI created a bespoke piece of software for generating shapes out of Dubins paths. By picking a series of random points in a grid, then using Dubins path to connect them all, the tool can generate a near-infinite number of different shapes.
I randomly bumped into this project on Behance, it may even be the source (or result) of this thread?
There’s a whole progression of projects based on the base mechanic and every single step is deliberate and very well crafted and presented. The latest iteration – Tangent, part 5 – is magnificent!
I’ve finally gotten around to implementing this with Dubin’s curves. Using them simplifies things as the bending is taken care of automagically.
What tripped me up initially though was how Processing’s y-axis extends downwards — usually this doesn’t matter, but it does when working with angles and orientation.
Some observations:
To determine if the band should wrap the outside or inside of the peg, compute the exterior angle it makes with previous and next pegs; if θ > PI, wrap outside.
The Dubin’s pin shouldn’t necessarily lie on N, S, E, W; it’s even better if it lies on the bisector (midpoint) of a peg’s exterior angle.
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. 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, any technique that finds a non-intersecting Hamiltonian cycle is appropriate (yours included!). A few other examples could include:
shortest path approximation (TSP) (*a shortest path never crosses itself)
Although these approaches have distinct objectives, they all share the common goal of addressing a route optimization problem, which specifically involves finding a cycle that visits each point exactly once without any intersection.
I have a personal preference for the last suggestion. Focusing on reducing the total distance traveled allows for the generation of solutions that are visually more homogeneous, likely aligning with Armin Hofmann’s intentions. This also seems more appropriate for applications in graphic design.
side note: I can’t help but think of Bruno Munari’s work, particularly his book ‘Flight of Fancy’ (1982), where he takes a single point cloud and transforms it into multiple different shapes by varying the connections, demonstrating how one can interpret the same raw information in numerous ways.
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 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 solver (world record: 85 900 cities / pegs in .06 seconds).
side note: Regarding this, I can only recommend reading ‘In Pursuit of the Traveling Salesman’ by William J. Cook (the brain behind the Concorde algorithm). I found his way of simplifying some basic computer science concepts very effective, and the book is filled with anecdotes about the historical context of the TSP and the algorithmic challenges associated with it. At least, if you can, try watching this recording of one of his public talks, which is very engaging (informative, full of visuals and funny).
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.
Great response as always. I realise I wasn’t clear in my original explanation, so let me clarify:
I’m using a concave hull implementation from JTS where one can specify the level of concavity. At maximum concavity, it finds the minimum inner hull, which forms a Hamiltonian cycle through the vertices. You’re absolutely right that concave hulls, in the general case, are not guaranteed to be Hamiltonian – in fact, they rarely are.
When I mentioned “finding a Hamiltonian cycle,” I was referring to the conventional approach (in my mind): first creating a graph from the geometry, then passing it to a Hamiltonian cycle algorithm in a graph library. In JGraphT, for instance, these algorithms are all TSP-based and require a complete graph. I’ve found these methods, with all their overhead, are significantly slower than the concave hull approach (though not at all an issue for generating static images – I had real-time manipulation in mind).
I never saw your website but keen to see what you had on there now that you’ve mentioned it.
Hey @micycle did you get around to polishing your solution and releasing the code yet? I’m trying to figure out something based on this problem myself and would love to see it
I still haven’t really figured it out, haha. And last time I checked the python version didn’t work in processing anymore.
