# Auto-Arrange objects, shortest Distances, optimal

This topic is 4520 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hello. I want to auto-arrange a couple of graphically depicted entities which can be arbitrarily interconnected with each other, like this: 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]

*push*

##### 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 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 on other sites
Quote:
 Original post by TrapDepending 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 on other sites
Quote:
 Original post by SneftelI'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 on other sites
wikipedia on simulated annealing - it's a probabilistic algorithm that results in something good but not optimal in most cases

##### Share on other sites
ah that sounds interesting, I'll look more deeply into that tomorrow.
Thankyou both!

- unshaven

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

1. 1
2. 2
JoeJ
20
3. 3
4. 4
5. 5
frob
12

• 10
• 13
• 21
• 13
• 20

×