Comment by maxbond

Comment by maxbond 2 days ago

2 replies

The choice and design of algorithm can itself be an aesthetic decision. Eg, OP generated some layouts, and spotted something that wasn't to their taste; the edges frequently overlap. So, we might approach the problem like this:

1. Choose an arbitrary algorithm to lay out trees where the edges don't overlap. There's many ways to do this, it doesn't need to be legible at this step.

2. Insert additional nodes along each edge. How many nodes is a tuning parameter we'll need to play with.

3. Use a traditional force-based graph layout algorithm, one that assigns charge to the nodes so that they repel each other. Because we've given the edges some nodes, they will have charge and won't bunch up together.

4. (Optional?) Detect edge overlaps. If they exist, randomize the initial state and try again.

(Note that the algorithm I've described is O(n^2). Patience will be necessary. You can probably refine it further, I only thought about it for a few minutes. Optimizations applied to physics engines (collision detection, gravity simulation) will apply.)

I've dabbled in generative art like this, and if you're willing to do the math and programming and iterate on the design, you can definitely get something of the aesthetic you are after. Bonus, the skills are transferrable to some other kinds of programming, like property testing and graphics.

JohnKemeny 2 days ago

You won't get edge overlaps if you start with a non-crossing drawing. In addition, n² is not very much when you have <100 nodes, as in this case.

Force directed layout algorithms can also be made faster using quad-trees and approximate repulsion.

MattPalmer1086 2 days ago

That's very similar to an algorithm I played with many years ago.

I also used simulated annealing, where a temperature controls the amount of random movement each node gets on an iteration, and the temperature is gradually reduced. It was a DAG though, not a tree.