Displaying circles equidistantly

[WDR]

Hi... This is a more of a theory question, so... I don't have any code to post and I 'm not asking for any. I'm supposed to display a directed graph and with circular nodes and straight line edges. I have to do it with the help of an adjacency matrix. An example of such,

        1 2 3

1       0 1 0
2       0 0 1
3       1 0 0

I have chosen SFML for the graphical display and I have no problem converting the above matrix into a displayable graph consisting of circles as nodes and lines as edges. I, however, have one small problem. My program has functions to add and remove nodes and their edges. Based on that, my graph has to be updated accordingly. When the user adds or removes nodes, the program will update the graph. When the graph is updated, I have to make it in such a way that, no matter how many nodes are there, they should be all equidistant to each other. For example, if the user adds three nodes, the three circles should be in the form of an equilateral triangle. If he adds one more node later or adds four nodes at the start, the circles should be in the form of a square. Similarly, pentagon, hexagon, etc. You get the picture. Now, my question is... How would I write the code such that the window draws them equidistant to each other? Is there a predefined function or should I work out some extra logic on it? Please clarify this for me. Thank you.


      

[eXpl0it3r]

This is more a math problem than implementation question, as such asking on a programming forum might not be the most effective way to get an answer.

How much did you think and research the problem in a mathematical sense?

[WDR]

I don't understand what you mean by mathematical sense. If you mean whether I can loop through the matrix and draw the nodes based on the number of rows and columns, and edges based on the matrix values, then yes, I definitely can. The matrix in memory is updated through user input (standard C++ input std::cin) and I have a function to redraw the graph in the window (refresh) every time the change is made. I just wanted to know how I would draw the circles in such a way that the program calculates it's distance with other circles and places them in a certain pattern (in this case, equidistant to each other). I can still draw the circles, albeit rather randomly on the screen. Forgive my lack of understanding, but I thought this was more of a graphical display related question. Please clarify it for me. Thanks.

[eXpl0it3r]

I don't understand what you mean by mathematical sense.
[…]
I just wanted to know how I would draw the circles in such a way that the program calculates it's distance with other circles and places them in a certain pattern (in this case, equidistant to each other).

How to loop through or draw something is programming related, but as you said it yourself, "calculating" the positions is first a math problem and once you figured out the "calculating" part, the implementation is trivial.

[WDR]

Hmm... Yeah, now I get what you mean. Well, I'll try to work that out and see what I can stumble upon. In the meantime, however, thank you very much for your help and a note to moderators, please keep this topic open in case I have any more doubts regarding the same problem. Thanks. 

[eXpl0it3r]

We don't close threads unless there's some flame war happening that needs stopping.

Thinking about this a bit more, I think after a certain number of nodes it might be impossible to have all the nodes equidistantly to all the other nodes or if there's a solution it most likely it will involve a huge graph.
Thus the question is, do you really want it to be equidistant? Isn't it enough if they all have the same distance between objects?

[WDR]

Now that you mention it, I do agree that it becomes difficult after a certain number of nodes. But in the context of my program, I don't think it will go past a certain maximum (say 50) number of nodes. And even though we have a certain maximum threshold, it still is difficult to set a unique condition for every number. But the real answer to your question is... It's not that I 'want' it to be equidistant, but it's more of a presentation thing. When viewed by the user, it should be good to look at and easy to understand. My worry is, it might get cluttered if many nodes are given as input.

[eXpl0it3r]

Now that I had a bit more time to think about it, it's clear that you didn't mean "no matter how many nodes are there, they should be all equidistant to each other" and you essentially already gave the counter example yourself. Because three nodes is the only amount of points which can be equidistant to each other. As soon as you add a forth the diagonal because sqrt(a^2 + a^2) which is still bigger than a itself.



So what you actually want is just a nice arrangement of the graph. Which I think doesn't just depend on the amount of nodes you have, but also on the in between connections. Like if your graph is more tree-like, you'd want to display it that way etc.
Because if it the graph doesn't matter, then the easiest alignment would be to just have every node in a grid, which obviously isn't the best configuration in most cases.

[Jesper Juhl]

For example, if the user adds three nodes, the three circles should be in the form of an equilateral triangle. If he adds one more node later or adds four nodes at the start, the circles should be in the form of a square. Similarly, pentagon, hexagon, etc.

You could easily achieve this by placing them on the circumference of a circle. If there are n nodes to display, just place them 360/n degrees apart. So, for n=3 you'd place them 120 degrees apart, n=10 would place them 36 degrees apart etc..

[WDR]

@eXpl0it3r: Lol... Sorry, I should have used a more appropriate word than equidistant. But anyways, you got what I meant. You mentioned a grid which is two dimensional. I did try a one dimensional arrangement where all the nodes are in a straight line, but the connections were a mess. And you're right. The connecting arrows are also important. As Jesper pointed out, the circle formation where an equilateral triangle, square or pentagon could be formed is kind of the best arrangement because the arrows can be drawn from any node to any other node without them overlapping over other nodes. If it was in a straight line, I would have to write a condition for the line to go around a node if it was in its path. Sort of like this,

This:


is easier than this:


If I didn't write that condition, I would end up with this, which doesn't make sense:


Which is why I am stressing for a good arrangement. Thank you for your inputs, though, eXpl0it3r! It's getting me to brainstorm for some new and different solutions. 


@Jesper Juhl: I did think of this earlier, wherein if you have three nodes, it gives the vertices an equilateral triangle, four nodes the vertices of a square, five for a pentagon and so on... Infinite nodes (in theory) would give a circle. So, all the vertices, irrespective of the number of nodes would lie on the circumference of a circle. How to implement this, though, I am not sure. I would have to actually imagine a circular path, maybe (?) or draw an actual reference circle to place nodes and not call its draw method in the final display to keep it invisible.

[Jesper Juhl]

Calculating a point on a circle circumference given a center point, radius and angle is pretty simple - see for example
 http://en.m.wikipedia.org/wiki/Circle#Equations
 http://www.math.com/tables/geometry/circles.htm

[WDR]

Oh yeah... I forgot those equations (I learned them way back in high school  ). I could work it out with this. I'll try and see how it goes. Thanks, Jesper. 

P. S. : By the way, if anyone is wondering, this is the exact same project I am doing:

It's an admission requirement for a Game Development school I am applying to. Even the person in the video says that the circular representation is a good way of arranging the nodes. Also, he shows an arrangement with many nodes at around 5:35. It makes a perfect circle. 

He uses 3D graphics and DirectX 10 complete with a three dimensional camera to traverse through the graph. For me, however, SFML's 2D implementation will suffice.

[WDR]

UPDATE: Sorry for the double post, but here's an update. I took Jesper's suggestion and looked on how to create the circular path using the circle equations he linked above. For any point on the circumference,

x = a + r(cos t)

y = b + r(sin t)

where (x,y) is the point, (a,b) is the center, t is the angle with X-axis and r is the radius.

I used these equations and based on them, I wrote the code to draw the nodes on the circular path. And it worked like a charm. 

Here's the code if anyone else wants to do anything similar:

Window.clear(sf::Color(255, 255, 255));

std::vector<sf::CircleShape> Circles;

sf::CircleShape Circle(30);

int n = 10, k = 1;

float X, Y;

for(int i = 0; i < n; i++)
{
        Circles.push_back(Circle);
}

for(std::vector<sf::CircleShape>::iterator it = Circles.begin(); it != Circles.end(); it++)
{
        it->setFillColor(sf::Color(0, 0, 0));

        X = 200.0f + 100 * (float)cos(k * (2 * PI/n));

        Y = 200.0f + 100 * (float)sin(k * (2 * PI/n));

        it->setOrigin(it->getGlobalBounds().width/2, it->getGlobalBounds().height/2);

        it->setPosition(X, Y);

        Window.draw(*it);

        k++;
}

I know the code is very crude and very messy. But the logic behind it is the same. I only did that to test how the output came. It's better to use loops for many nodes. EDIT: I changed the code to make it more optimal with the help of for loops and STL containers such as vectors. The window size I took was 400x400 so the center is (200, 200). Here's what I got for three nodes and four nodes.



Pretty neat, right? At least it serves my purpose. Thanks, Jesper Juhl and eXpl0it3r! For now, I am satisfied with what I got, but please don't close the topic yet. If I hit any more roadblocks with this problem again, I shall ask again. Thank you. Have a nice day!