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):

Expand|Select|Wrap|Line Numbers

 
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

Quote:

Originally Posted by RedSon

Is this implementation close to what you were thinking?

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.

Expand|Select|Wrap|Line Numbers

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

Expand|Select|Wrap|Line Numbers

 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.

Expand|Select|Wrap|Line Numbers

 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

Expand|Select|Wrap|Line Numbers

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

Quote:

Originally Posted by RedSon

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

Expand|Select|Wrap|Line Numbers

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

Quote:

Originally Posted by RedSon

Is there a way to modify this such that r(min) can be calculated for n > 1?

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

Quote:

Originally Posted by RedSon

Also, I would use this formula

Expand|Select|Wrap|Line Numbers

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?

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

Dormilich

Quote:

Originally Posted by RedSon

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

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

Quote:

Originally Posted by Dormilich

Expand|Select|Wrap|Line Numbers

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

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

Quote:

Originally Posted by Dormilich

Expand|Select|Wrap|Line Numbers

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

@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

Quote:

Originally Posted by 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)

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:

Expand|Select|Wrap|Line Numbers

(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

Quote:

Originally Posted by YarrOfDoom

I didn't see this solution anywhere, but wouldn't the perfect formula for for calculating the minimum radius be:

Expand|Select|Wrap|Line Numbers

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

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:

Expand|Select|Wrap|Line Numbers

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

YarrOfDoom

Quote:

Originally Posted by 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)?

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

Quote:

Originally Posted by Dormilich

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).

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

Quote:

Originally Posted by YarrOfDoom

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

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

Quote:

Originally Posted by RedSon

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?

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.

Expand|Select|Wrap|Line Numbers

 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:

Expand|Select|Wrap|Line Numbers

 >>> 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:

Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

re: Circular Layout

Similar Algorithms / Advanced Math bytes

/bytes/development

/bytes/it

/bytes/about