cyotek.com Tag Summary Feed - mathcyotek.com Tag Summary Feed - mathen-gbCopyright © 2009-2024 Cyotek Ltd. All Rights Reserved.richard.moss@cyotek.comThu, 25 Jul 2024 13:59:21 Zcyotek.com 4.8.4729.0https://www.cyotek.com/assets/images/logos/cyotek.pngcyotek.com Tag Summary Feed - mathblog/rss/math- https://www.cyotek.com/blog/arranging-items-radially-around-a-central-point-using-csharp?source=rsshttps://www.cyotek.com/blog/arranging-items-radially-around-a-central-point-using-csharp?source=rssrichard.moss@cyotek.comcsharpmathdiagramtrigonometryArranging items radially around a central point using C#<p>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.</p>
<p><a href="https://images.cyotek.com/image/devblog/radial-tree-1a.png" title="The demonstration program with a few child nodes"><img src="https://images.cyotek.com/image/thumbnail/devblog/radial-tree-1a.png" alt="The demonstration program with a few child nodes" title="The demonstration program with a few child nodes" /></a></p>
<p>This post discusses the sample project I created to explore the
first part of this concept.</p>
<blockquote>
<p>Caveat emptor. This post is out of my usual comfort zone as
its dealing with trigonometry. Errors and misunderstandings
may abound.</p>
</blockquote>
<h2 id="calculating-the-angle">Calculating the angle</h2>
<p>The first thing we need to do is calculate the angle between one
node and the next. The following formula will calculate the
number of <del>degrees</del> radians in the angle.</p>
<p><code>csharp
// count is the number of children we'll be placing around the center
double angle = 360.0 / count * Math.PI / 180.0;</code></p>
<h2 id="calculating-a-default-distance">Calculating a default distance</h2>
<p>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.</p>
<p><code>csharp
// technically as I'm using circles the Width and Height should always be the same, but this may change in future
distance = Math.Max(node.Width, node.Height);</code></p>
<h2 id="positioning-each-node">Positioning each node</h2>
<p>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.</p>
<p>```csharp
for (int i = 0; i < nodes.Count; i++)
{
DiagramNode child;
int x;
int y;</p>
<p>child = nodes[i];</p>
<p>// calculate the center of the child node offset from
// the central node
x = cx + Convert.ToInt32(Math.Cos(angle * i) * distance);
y = cy + Convert.ToInt32(Math.Sin(angle * i) * distance);</p>
<p>// adjust the final location to be the top left instead of the center
child.Location = new Point(x - (child.Width / 2), y - (child.Height / 2));
}
```</p>
<p><a href="https://images.cyotek.com/image/devblog/radial-tree-1b.png" title="Overlapping nodes make for pretty patterns but otherwise aren't much use"><img src="https://images.cyotek.com/image/thumbnail/devblog/radial-tree-1b.png" alt="Overlapping nodes make for pretty patterns but otherwise aren't much use" title="Overlapping nodes make for pretty patterns but otherwise aren't much use" /></a></p>
<p>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.</p>
<h2 id="testing-if-two-circles-overlap">Testing if two circles overlap</h2>
<p><a href="https://images.cyotek.com/image/devblog/radial-tree-1d.png" title="Without corners, nodes can overlap each other without having an impact"><img src="https://images.cyotek.com/image/thumbnail/devblog/radial-tree-1d.png" alt="Without corners, nodes can overlap each other without having an impact" title="Without corners, nodes can overlap each other without having an impact" /></a></p>
<p>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.</p>
<p>```csharp
private bool DoCirclesInsersect(int cx1, int cy1, int r1, int cx2, int cy2, int r2)
{
int dx;
int dy;
double distance;</p>
<p>// Find the distance between the centers
dx = cx1 - cx2;
dy = cy1 - cy2;
distance = Math.Sqrt(dx * dx + dy * dy);</p>
<p>return distance < r1 + r2;
}
```</p>
<blockquote>
<p>This is almost exactly the same method used in my previous
post of <a href="https://www.cyotek.com/blog/finding-nearest-colors-using-euclidean-distance">finding nearest colours</a>.</p>
</blockquote>
<p>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 <a href="http://csharphelper.com/blog/2014/09/determine-where-two-circles-intersect-in-c/">C# Helper post</a>. It also describes the math,
something I'm not even going to try and do.</p>
<h2 id="brute-forcing-the-intersection">Brute forcing the intersection</h2>
<p><a href="https://www.cyotek.com/files/articleimages/radial-tree-1c.png" title="Increasing the distance between the centre node and its children mean they can fit without overlapping"><img src="https://www.cyotek.com/files/articleimages/radial-tree-1c-thumbnail.png" alt="Increasing the distance between the centre node and its children mean they can fit without overlapping" title="Increasing the distance between the centre node and its children mean they can fit without overlapping" /></a></p>
<p>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.</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>```csharp
private bool TestNodes(List<DiagramNode> nodes)
{
bool result;
int count;</p>
<p>result = true;
count = nodes.Count;</p>
<p>for (int i = 0; i < count; i++)
{
int cx1;
int cy1;
int cx2;
int cy2;
int r1;
int r2;
int next;
Point c1;
Point c2;</p>
<pre><code>next = i < count - 1 ? i + 1 : 0;
c1 = nodes[i].Center;
c2 = nodes[next].Center;
cx1 = c1.X;
cy1 = c1.Y;
r1 = nodes[i].Width / 2;
cx2 = c2.X;
cy2 = c2.Y;
r2 = nodes[next].Width / 2;
if (this.DoCirclesInsersect(cx1, cy1, r1, cx2, cy2, r2))
{
result = false;
break;
}
</code></pre>
<p>}</p>
<p>return result;
}</p>
<p>private void PositionDiagram(DiagramNode node)
{
int count;
double angle;
int distance;
int cx;
int cy;
List<DiagramNode> childNodes;
Point center;</p>
<p>childNodes = node.ChildNodes;</p>
<p>count = childNodes.Count;</p>
<p>angle = 360.0 / count * Math.PI / 180.0;</p>
<p>// if we were using squares we'd need some extra padding
// but as I'm using ellipsis we can use use the largest axis
distance = Math.Max(node.Width, node.Height);</p>
<p>// need to use the centerpoint of our node
// to ensure all other nodes are an equal distance away
center = node.Center;
cx = center.X;
cy = center.Y;</p>
<p>// position the children
this.ArrangeNodes(childNodes, cx, cy, angle, distance);</p>
<p>// if there is more than one child node, check to see if any intersect with each
// other. if they do, and the distance is within a given maximum, increase the distance
// and try again. I've no doubt there's a much better way of doing this
// than brute forcing!
if (count > 1 && !this.TestNodes(childNodes))
{
this.BruteForceNodeLayout(childNodes, angle, cx, cy, distance);
}
}</p>
<p>private void BruteForceNodeLayout(List<DiagramNode> childNodes, double angle, int cx, int cy, int distance)
{
bool success;</p>
<p>do
{
// increment the distance
distance += childNodes[0].Width / 4;
if (distance > _maximumDistance)
{
distance = _maximumDistance;
}</p>
<pre><code>// first arrange all the nodes around the central node with a minimum distance
this.ArrangeNodes(childNodes, cx, cy, angle, distance);
success = distance >= _maximumDistance || this.TestNodes(childNodes);
</code></pre>
<p>} while (!success);
}
```</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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.</p>
<h2 id="initial-starting-position">Initial starting position</h2>
<p>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
code in <code>ArrangeNodes</code>.</p>
<h2 id="final-thoughts">Final thoughts</h2>
<p><a href="https://images.cyotek.com/image/devblog/radial-tree-1.gif" title="An animated example of the demonstration program"><img src="https://images.cyotek.com/image/thumbnail/devblog/radial-tree-1.gif" alt="An animated example of the demonstration program" title="An animated example of the demonstration program" /></a></p>
<p>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.</p>
<p>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 <a href="https://cyotek.com/contact">hear them</a>!</p>
<p>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.</p>
<h2 id="update-history">Update History</h2>
<ul>
<li>2017-11-05 - First published</li>
<li>2020-11-22 - Updated formatting</li>
</ul>
<h3 id="downloads">Downloads</h3>
<ul>
<li><a href="https://www.cyotek.com/downloads/view/RadialDiagramDemoPart1.zip/" title="Sample project for the Arranging items radially around a central point using C# blog post">RadialDiagramDemoPart1.zip</a> (11.38 KB)</li>
</ul>
<p><small>
All content <a href="https://www.cyotek.com/copyright-and-trademarks">Copyright (c) by Cyotek Ltd</a> or its respective writers. Permission to reproduce news and web log entries and other RSS feed content in unmodified form without notice is granted provided they are not used to endorse or promote any products or opinions (other than what was expressed by the author) and without taking them out of context. Written permission from the copyright owner must be obtained for everything else. <br />Original URL of this content is https://www.cyotek.com/blog/arranging-items-radially-around-a-central-point-using-csharp?source=rss.
</small></p>Sun, 05 Nov 2017 10:33:39 Z2020-04-06T17:00:09+01:00