Sign in to follow this  
UnshavenBastard

Auto-Arrange objects, shortest Distances, optimal

Recommended Posts

Hello. I want to auto-arrange a couple of graphically depicted entities which can be arbitrarily interconnected with each other, like this: Image Hosted by ImageShack.us The entities should be arranged optimally, ie. all entities that are connected with each other should have the shortest distances from each other possible (ie. distance from center to center). I want to align them all in a rectangular manner, matching the aspect ratio of the window containing the depiction - but if this puts an undue constraint on this, I may neglect to care about the overall alignment. The first thing that came to my mind was creating all permutations from the list holding all objects, arranging them all for each permutation and calculating all distances, summing them all up and at the end of it all, choose the permutation with the best result, ie. smallest distance sum. (Having a given rectangular frame around and an equal neighbor's distance for all of the entities, you know all possible arrangements by knowing the permutations of a list containing all entities) Pretty brute-force. It works so far, but what I forgot was that there are n! permutations [grin], in other words, this approach is only useful for a handful of objects, if you dont want to completely take up the system's memory for a little app. But I need to process more. Added: btw., at the moment I don't care about crossing lines, or lines crossing entities... I think a good point to start is to get the entities which are connected to each other, arranged as close as possible before calculating any actual paths. (I will make my paths neatly axis-aligned later) So, is there a known algorithm for such a problem, or has anyone here solved a similar problem already and can give some hints? Thanks, unshaven [Edited by - UnshavenBastard on March 7, 2006 12:35:49 PM]

Share this post


Link to post
Share on other sites
I've done things like this in the past using Simulated Annealing. In your case, the annealing step might be to swap n random pairs of boxes; the score for a configuration, of course, would be the sum of all edge lengths.

Share this post


Link to post
Share on other sites
Depending on the exact definition of shortest distances and legal connections it might be anything between solving a system of linear equations and NP-hard.

Most probably it is NP-hard which means you can only solve it by trying all possible permutations.

Share this post


Link to post
Share on other sites
Quote:
Original post by Trap
Depending on the exact definition of shortest distances and legal connections it might be anything between solving a system of linear equations and NP-hard.

Most probably it is NP-hard which means you can only solve it by trying all possible permutations.



"shortest distances" means ie. the distance from one object's center to the center of another. (while there is a minimum distance defined so that they don't collide)

"legal connections", well this is not a maze or something,
the connections are abstract, there can be arbitrary connections between two entities - but the connections itself are completely meaningless for solving this problem. the only important thing is to know if two entities are connected to each other or not.
the rectangular overall alignmnent mentioned is only for nice looks.

Share this post


Link to post
Share on other sites
Quote:
Original post by Sneftel
I've done things like this in the past using Simulated Annealing. In your case, the annealing step might be to swap n random pairs of boxes; the score for a configuration, of course, would be the sum of all edge lengths.


I just looked-up the word "annealing" in a dictionary (non-native english speaker), I can only guess what you mean, would you elaborate a little? :-)

Share this post


Link to post
Share on other sites
You also may want to look at kd trees. The wikipedia entry on those are pretty good, and I believe that they are very good for closest point type algorithms.

EDIT: I apologize... the wikipedia entry actually isn't so good.

http://www.cs.sunysb.edu/~algorith/files/kd-trees.shtml

That link also has a nearest neighbor implementation.

Share this post


Link to post
Share on other sites
The Wikipedia page on simulated annealing is a bit opaque, IMHO. The Numerical Recipes books have much better info. clicky (and the rest)

Share this post


Link to post
Share on other sites
Thanks, interesting book! I downloaded it completely, oh my poor finger.


Smitty:

I see how kd-trees help in finding the nearest neighbor etc., but at the moment I don't see a use for them to solve the problem explained in my first post. I have to align objects to be neighbors, not test if/who they are. Or did you look already further than I?

Share this post


Link to post
Share on other sites
lol what is this,

I printed those 12 pages of the one pdf,
and seemingly all words which have it lack of the character combination "fi",
ie. "defined" is printed as "de ned", "configuration" as "con guration"


is my printer/driver dumb, or is this a kind of nasty "copy protection", so that I can't just print-out the book instead of buying it ?
It's good that I didn't print more chapters . . . argh.

Share this post


Link to post
Share on other sites
In the Numerical Recipes book, it says the strategy also involves to occasionally acceppt "uphill steps", ie. steps that make the current solution worse instead of better.
I see the need for that, but what I'm not sure about:

What are good strategies to decide when to accept an "uphill" step ?

My implementation is working so far, and until now pretty good, but I'm afraid after adding a couple more restrictions(penalties) it won't do that good without having an uphill step here and there, which isn't there at all currently.

[Edited by - UnshavenBastard on April 6, 2006 2:50:19 AM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this