Circular Layout

[RedSon]

Hi all,

I have a problem where I have 1..n icons that I would like to layout in a circular pattern. Starting at an origin of (120, 160) I'm trying to figure out how to iterate over the collection of items and assign them a new position offset from the origin. Each of these items is a square of 48px and they cannot overlap.

How in the world do I do it? I know I'll be needing to use my trig on this, but it's been so long I forgot most of it :(

Thanks.

[Dormilich]

roughly speaking they need a distance of about 75px (48px · 2^0.5) from each other, the direction depends on the number n. so minimum radius of the circle should be n · 75px / 2 pi for n > 4 (to make it a sensible approximation).

..... if I've understood the problem right.

edit>>>
if you have a symmetry group of D[(2n)d] (i.e. an even number of pictures) you can reduce the calculation effort to one fourth (otherwise, one half)
<<<

[RedSon]

Here is what I have now (link):

Vector2 origin = new Vector2(viewport.Width / 2, viewport.Height / 2);
 
int radius = 48;
double factor = ((2 * Math.PI) / menuEntries.Count);
 
// Draw each menu entry in turn.
foreach (MenuEntry entry in menuEntries.Values)
{
    int i = menuEntries.IndexOfValue(entry);
    bool isSelected = IsActive && (i == selectedEntry);
 
    iconPos.X = (float)radius * (float)Math.Cos(factor * i + 1);
    iconPos.Y = (float)radius * (float)Math.Sin(factor * i + 1);
 
    entry.Draw(this, Vector2.Add(iconPos,origin), isSelected, gameTime);
}

Now there is no way I can tell if there are an even number of pictures or not, but I would be interested in optimizing the calculations.

The radius will likewise need to be calculated but it is currently hard coded.

Is this implementation close to what you were thinking?

[Dormilich]

@RedSon
yes, the only thing I wonder is why you use an initial rotation of 57° 17′ 44.8″.

you should check if the radius given is large enough, so that the icons do not overlap.

r(min) = n · icon.width / ( sqroot(2) · pi ) 

note that this approximation does not work for n < 5, thus a good default radius is necessary (48px should do)

for drawing optimization compute the circle with the origin at (0, 0) and add position on screen later. (seems like you already did that)

you can use a rotation matrix

cos(a)    –sin(a)
sin(a)     cos(a)

so you only need to compute the first point and then repeatedly (n–1 times) apply the matrix in a iterative way.

x(0) = r · sin(a_ini)
y(0) = r · cos(a_ini)
// a_ini is the initial angle you want, 0 is vertical, top
 
x(i+1) = x(i) · cos(a) – y(i) · sin(a);
y(i+1) = x(i) · sin(a) + y(i) · sin(a)
// where a = 2·pi / n

note: I don't know how to code in C#

[JosAH]

Are those icons shown in an upright position (i.e. no tilt)?

kind regards,

Jos

[RedSon]

@Jos: The icons in my application are not rotated in any way when they are drawn on the screen.

@Dormilich: Why do you say I use an initial rotation of 57° 17′ 44.8″?

Also, I would use this formula

r(min) = n · icon.width / ( sqroot(2) · pi )

but the screen size is so small having 5 or more icons creates a great amount of clutter. Is there a way to modify this such that r(min) can be calculated for n > 1?

[RedSon]

Also would either of you be willing to do some code review on the project I linked to in post 3?

You can use the web based svn viewer and double click on any line to make comments on that line. You don't have to know C# to be able to intuit what is going on with it.

[Dormilich]

@RedSon

Math.Cos(factor * i + 1)

57° 17′ 44.8″ = 1 (rad),
like usual in maths, if you add in y = f(x) a value to x, you shift the function by –x

@RedSon
sure,
n = 2: r(min) = 0.5 · icon.width;
n = 3: r(min) = sqroot(2/3) · icon.width;
n = 4: r(min) = icon.width;

@RedSon
the formula is an approximation of the circumference calculation, which will give large deviations for small n.

[Dormilich]

@RedSon
If I don't have to do it until next week, I'll try my best.

[RedSon]

You don't have to do it until whenever you want to do it. There is no project schedule for this, it is a hobby of mine.

[RedSon]

@Dormilich
Of course, that didn't even occur to me! I will have to make a fix for that, since I would like it to start at 0.

[Dormilich]

that's good.

if you would in turn have a look at my PHP code........ (though I need to find a place to post the code first)

[RedSon]

I would look at it, however I find PHP code to be much more cryptic than C#, so I am not sure how useful I will be. :(

[Dormilich]

it's more about programm design than actual coding (I know that my PHP knowledge is above forum average, but that doesn't mean I can't overlook some crucial points, especially since I'm new to OOP coding)

[RedSon]

Well, just got to find a place to put it ;-)

[JosAH]

For a fast upperbound you can do this; an icon at 45 degrees takes up most of the space, i.e. sqrt(2)*48 == W pixels (its diagonal). For n icons in a 'circular' layout you need a circumpherence of n*W pixels. That basically solves it; note that not all icons will 'touch' eachother because this estimation is a minimal upperbound.

kind regards,

Jos

[Dormilich]

@Dormilich
@JosAH: like that one? (only put in a formula)

note: this solution does not work for n = 4, you'll see the overlap in some cases (the minimum radius is calculated 10% too small)

[JosAH]

@Dormilich
No not like that one; I reread my reply and noticed that my description was extremely sloppy. When you chop up a circle in equal angle wedges, those wedges are all isosecles triangles. The sides opposite to the centre of the circle should equal sqrt(2)*W, not that part of the circumpherence of the circle.

kind regards,

Jos

[Dormilich]

ok, you can exactly calculate the r(min) for every n by using the Law of Cosines, nevertheless, for n > 4 the approximation by circle segments is good enough and far easier to compute.

Alas, I see our discussion is interesting, but pointless, because RedSon said 5 or more icons would be too much for his application.

[YarrOfDoom]

This has caught my interest. I didn't see this solution anywhere, but wouldn't the perfect formula for for calculating the minimum radius be:

(sqrt(2) * 24) / sin(pi / n)

I've tried this on my graphical calculator and it seems to work for every n>1.
Here's how I got to it:

[RedSon]

I'm assuming 24 to be dependent on the dimension of the icon? How would your formula change if the icons could have an arbitrary height and width (but still be square)?

[Dormilich]

@YarrOfDoom
well, I was not aiming for the perfect formula (since this would involve sines or cosines), just one easy and fast to compute. and, put in another way, you have to round it anyways in the end (to get the pixels).

EDIT: using the Law of Cosines I get:

r = w / sqrt(1 – cos(2pi/n))

[YarrOfDoom]

@RedSon
It would become (sqrt(2) * x) / (2 * sin(pi / n))

@Dormilich
I guess it all depends on the situation, but it's always handy to have a more general solution standby, in case you come across a similar situation.

[RedSon]

@YarrOfDoom
Yes I know but my question was, what is x defined as? Is it half the width of the icon if the icon is square?

[YarrOfDoom]

@RedSon
Oops, lost a line there, x represents the width (and height, since it's a square) of the icon, and also note that the sine is multiplied by 2 now. (So the 24 is indeed meant as one half of 48).

[bvdet]

RedSon,

I found this thread by accident since I don't get over here often. For the exercise, I worked up a general solution in Python using code from one of my modules.

from math import pi, sin
 
from macrolib.PointPlane3D import *
 
def icon_layout(origin, size, n):
 
    # calculate radius
    minChord = size*2**0.5
    angleBetween = 2*pi/n
    minRadius = (minChord/2)/sin(angleBetween/2)
 
    startPoint = Point(origin.x+minRadius, origin.y, 0)
    '''
    Three counter-clockwise points define a plane with the plane normal
    vector pointing out of the screen. First point is the center of
    rotation. Second point defines the X axis and radius of circle.
    '''
    A = Plane3D(origin, startPoint, 
                Point(origin.x, origin.y+minRadius, 0))
 
    return [A.PointRotate3D(startPoint, angleBetween*i) \
            for i in range(numberIcons)]
 
origin = Point(120, 160, 0)
iconSize = 48
numberIcons = 12
pointList = icon_layout(origin, iconSize, numberIcons)
for pt in pointList:
    print repr(pt)

Output:

>>> Point(251.138439, 160.000000, 0.000000)
Point(233.569219, 225.569219, 0.000000)
Point(185.569219, 273.569219, 0.000000)
Point(120.000000, 291.138439, 0.000000)
Point(54.430781, 273.569219, 0.000000)
Point(6.430781, 225.569219, 0.000000)
Point(-11.138439, 160.000000, 0.000000)
Point(6.430781, 94.430781, 0.000000)
Point(54.430781, 46.430781, 0.000000)
Point(120.000000, 28.861561, 0.000000)
Point(185.569219, 46.430781, 0.000000)
Point(233.569219, 94.430781, 0.000000)
>>>

If you are interested in the source code for PointPlane3D: link

Here's a graphical solution:

[gtoal]

I don't think any of these solutions are taking into account a visually pleasing layout where the amount of white space between each icon is roughly similar. in 'circular_layout.jpg' above where the icons are regularly spaced, you can see where the icons at 45 degrees almost touch but the vertically or horizontally adjacent ones have a gap. A smarter algorithm that takes the shortest distance between the nearest points of adjacent icons into account may be needed.

[Dormilich]

a smarter algorithm would just add padding to the icon width.

[franknagy]

Let your icons be squares of sides a. Define a regular polygon of n sides with side d=a*sqrt(2). You can count from d and n the radius of the circle around the polygon:
r=(d/2)/sin(2*pi/n).
Place the center points of your icons on the vertices of this polygon.
x(k)= C(x)+r*cos(k/(2*pi),
y(k)= C(y)+r*sin(k/(2*pi), k=0,1,2,...,n-1.