Recently I was looking for a way of display hierarchical information in a more compact form than the previous horizontal/vertical trees I was using. One of the concepts I looked into during this was the idea of arranging children radially around a central node.
This post discusses the sample project I created to explore the first part of this concept.
Caveat emptor. This post is out of my usual comfort zone as its dealing with trigonometry. Errors and misunderstandings may abound.
The first thing we need to do is calculate the angle between one
node and the next. The following formula will calculate the
degrees radians in the angle.
All the nodes in this diagram are going to be rendered as circles. This makes some of the layout work easier due to there being no corners, as the shapes can be closer to together without overlapping. To start with, I'll simply try and place the new nodes right next to the centre node.
Once we have the angle, we loop through each child node and using the angle and distance values we can calculate the centre point of the child using the sine and cosine mathematical functions. Once we've got the centre, we offset it by half the nodes width and height to get the upper left corner.
With this code in place, our diagram is taking shape - at least until we add enough nodes that they start to overlap with each other. If this happens, we need to detect if the nodes overlap using Euclidean geometry.
To test if circles overlap, we calculate the distance between the centre of the first circle and the second. If the distance is less than the radius of the two circles, then they intersect.
This is almost exactly the same method used in my previous post of finding nearest colours.
For a much more detailed version of this function which can also determine at which points on the edges of the circles intersect see this C# Helper post. It also describes the math, something I'm not even going to try and do.
I'm sure there's probably a much better way of doing this, but as I don't know of one I resorted to brute forcing - after positioning the children, I check them to see if there's any overlap. If there are intersections, I increment the distance, re-position the nodes and test again. To avoid nodes being placed excessively far from the centre node, once the distance is above a defined maximum I abort the testing and use the maximum value, regardless of overlap.
The below code only considers the intersection of one child node with an adjacent child node. However, if the central node is smaller than the children, then it is possible for the child nodes to overlap the parent. The full demonstration program tests for intersection with both the parent node and the next child node to avoid this.
Once the child nodes have moved sufficiently far enough away from the centre you could try staggering the nodes to make better use of the free space; this may allow for a closer grouping.
Although the demonstration program doesn't show this, this code works perfectly well if the child nodes are of varying sizes - it will try and position according to the largest child it finds.
If you consider a clock face, the painting of the first node in
this example always occurs at 3 o'clock. This is actually
perfect for my needs, but if you wanted it to start from
somewhere else (for example 12 o'clock), you'd need to adapt the
The technique in this article can be useful in other circumstances, for example I first used code similar to this to create a 12 node colour wheel as part of another concept program. But the general principle could be used for other things, such as dials, gauges and clock faces.
Due to the brute forcing for positioning, this code is nowhere near as optimal as I'd otherwise like it - if anyone has ideas for solving this I'd love to hear them!
I cut out a lot of the code from this article and just focused on the core functionality, a fully functional sample can be downloaded from the link below.
- 2017-11-05 - First published
- 2020-11-22 - Updated formatting