algorithm to spread items around a circle near their start positions

Question

I'm working on a chart that has a number of items around a circle. For each item, I have a radian which allows me to place it in the correct position - but I have overlaps and I'd like to spread the items out, but have them remain near (as near as possible) to their original positions.

In order to avoid overlap, each item must be at least 7 degrees from any adjacent item. There will always be enough room for all items around the circle - with a maximum of 20 items, it's possible for each item to have 18 degrees of separation (not that it will ever happen that way), but it's quite probable that I'll have up to 6 or 8 items clustered in an area, and possibly multiple clusters.

Most often, I'll have 10 to 12 items, but to make things easy to illustrate - lets say I have 5 items 1 degree apart: [1,2,3,4,5]. Ideally, the result would be [349,356,3,10,17] - each item 7 degrees from any other item with item 3 remaining unchanged, but all items remain as near their original positions as possible.

Of course, when I have all 20 items present - I risk moving an item into another item. Take a similar example: [340,1,2,3,4,5]. The same as above - except moving 1 to 346 would cause another overlap.

Given a complete list of item radians, does anyone know of a method to accomplish what I'm trying to do?

I just can't seem to figure out how to accomplish it.

Evenly spaced is easy, and not representative of the data I'm displaying. The items are positioned relative to the data they represent. I need them to remain on or near their assigned positions, yet spread out so they aren't overlapping. — Michael
– Michael, Commented Jan 11, 2014 at 7:47

kuroi neko · Accepted Answer · 2014-01-12 14:31:57Z

I had a go at your problem with a different approach.

The idea is to add objects to the circle one at a time.
Each object defines a collision area around it.

When a new object is added, it is checked for collision with the existing ones.
If a collision occurs, the new objects is added to a "collision group" containing all objects that will require relative position adjustments to avoid overlaping each other.
If no overlap is detected, a new collision group containing only the new object is created.

After accepting a new object, a group will cover a portion of the circle centered around its objects center of gravity and just wide enough to hold all the objects with no overlap.

Each time a collision group grows, it is checked against all the other groups for overlap, and merged with the first intersecting group detected.
The process is repeated with the resulting group until no more merges can be done.

Once all objects have been added, position adjustment are computed within each group to spread the objects evenly.

See a fiddle here

var CollisionResolver = function (radius) { this.radius = radius || 3.5; // degrees this.groups = []; this.collision = {}; this.objects = {}; this.num_obj = 0; } CollisionResolver.prototype = { // add an object to the circle add: function (obj) { function sort_group () { group.elem.sort(function(a,b) {return a.pos>b.pos; }); var middle = 0; for (var i = 0; i != group.elem.length ; i++) middle += group.elem[i].pos; middle /= group.elem.length; var range = this.radius * group.elem.length; group.min = middle-range; group.max = middle+range; // see if the expanded group now overlaps another for (var g = 0 ; g != this.groups.length ; g++) { var group2 = this.groups[g]; if (group2 == group) continue; for (var offset = 0 ; offset <720 ; offset += 360) { if ( (group2.max+offset > group.min) && (group2.min+offset < group.max)) { // merge groups for (var i = 0 ; i != group2.elem.length ; i++) group2.elem[i].pos += offset; group.elem = group.elem.concat(group2.elem); this.groups.splice (g, 1); // try again with the merged group sort_group.call (this,group); return; } } } } // store the object obj.id = this.num_obj; this.objects[this.num_obj++] = obj; // see if the object falls within a collision group for (var g in this.groups) { var group = this.groups[g]; for (var offset = 0 ; offset <720 ; offset += 360) { if ( (obj.pos+offset+this.radius > group.min) && (obj.pos+offset-this.radius < group.max)) { // insert the object into the collision group obj.pos += offset; group.elem.push (obj); sort_group.call (this, group); return; } } } // create a new singleton collision group var group = { elem: [obj], min :obj.pos-this.radius, max :obj.pos+this.radius }; this.groups.push (group); }, resolve: function () { // spread the objects inside each group var groups = this.groups; for (var i = 0 ; i != groups.length ; i++) { var group = groups[i]; for (var o = 0 ; o != group.elem.length ; o++) { group.elem[o].pos = (group.min + (2*o+1) * this.radius + 360) % 360; } } // return the positions var res = []; for (var i = 0 ; i != this.num_obj ; i++) res.push (this.objects[i].pos); return res; } } function spread (positions, radius) { var collider = new CollisionResolver (radius); // initialize object positions for (var i = 0; i != positions.length ; i++) { collider.add ({ pos:positions[i]} ); } // resolve collisions return collider.resolve(); }

It is still a bit rough around the edges (I'm not quite sure the 360°->0 transitions handling is really foolproof), but it seems to do the job in most cases. I'd say that's good enough for a proof of concept.

This algorithm does not enforce your requirement of a maximal (angular) distance between the original and adjusted positions. On the other hand, it guarantees no overlap as long as there is enough room to fit all the objects into the circle.

That's very nice. When I have time in the next few weeks I'll retool my code to try this. If it works as well as it does in your fiddle, I'll change my accepted answer.
Accepted answer changed - this is a perfect result. Thank you!

GameAlchemist · Accepted Answer · 2014-01-11 08:21:42Z

Build an array of { item, itemAngle, itemDisplayAngle } out of your items.
Have itemDisplayAngle set at itemAngle initially.
Sort the array by itemAngle.
Then loop through the array, and if the distance between two successive items is less than 7, shift the items 7 to the right if the room is not taken. watch out, the distance must be %360, and you must watch for the first items of the array if angle + 7 > 360.
repeat step above until no operation was performed.

Edit : to have the minimum spread, the solution is quite similar, just a little bit more difficult to explain : if the spread is <7, then you have to move each item by (7 - current spread) / 2.
But of course you have to check that you can, now both on your left and on your right, move items. I think that if you can't use the half-spread you should test if you can move right item to the right, or left item to the left. This way you have optimal placement.

That only moves items in one direction though. It doesn't keep them as close as possible to their original start positions. Your solution leaves item1 in place with item 5 being moved 28 degrees away. The solution I'm looking for would have item 5 only 14 degrees away. See my first example.
your edit is the method I've been working on all night. I finally got it. This can't be the best way...

Collectives™ on Stack Overflow

algorithm to spread items around a circle near their start positions

2 Answers 2

2 Comments

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Related