I have an array of 10+ numbers. They represent coordinates on a circle - in degrees, i.e. each number is in between 0 and 359.999999...
The problem I am trying to solve is that when I draw my items on the circle (via html5 canvas api), sometimes they are clustered together and that results in items being drawn onto each other.
So I would like to create an algorithm which disperses items evenly around their initial cluster position. Let's say (and I'd like this to be a configurable option) the minimal distance between two items is 5 degrees.
So if the initial array is [5, 41, 97, 101, 103, 158, 201, 214, 216, 217, 320] then I would like the algorithm come up with something like [5, 41, 95, 100, 105, 158, 201, 211, 216, 221, 320]
(with bolded items being dispersed around their initial "gravity center" regardless whether those are 2 or more items).
Also what would be neccessary is that the algorithm recognizes 0 and 359 being just 1 unit (degree) apart and also spread such items evenly around.
Has anyone ever created such algorithm or have a good idea how it could be achieved? Even some general thoughts are welcome.
I'm sure I could achieve that with plenty of trial and error, but I'd like to hear some educated guesses, if you will, first.
var val = [5, 41, 96, 101, 103, 158, 201, 214, 216, 217, 320, 1201, 1213, 1214, 1216, 1217, 1320],
delta = Array.apply(null, { length: val.length }).map(function () { return 0 }),
result,
threshold = 5,
converged = false;
document.write('val: ' + val + '<br>');
while (!converged) {
converged = true;
delta = delta.map(function (d, i) {
if (i < delta.length - 1 && delta.length > 1) {
if (val[i + 1] + delta[i + 1] - val[i] - d < threshold) {
converged = false;
delta[i + 1] += 1;
return d - 1;
}
}
return d;
});
document.write('delta: ' + delta + '<br>');
}
result = val.map(function (v, i) {
return v + delta[i];
});
document.write('result: ' + result + '<br>');
// try to minimise difference
converged = false;
while (!converged) {
converged = true;
delta = delta.map(function (d, i) {
if (i < delta.length - 2) {
var space = val[i + 1] + delta[i + 1] - val[i] - d;
if (d < 0 && space > threshold) {
converged = false;
return d + space - threshold;
}
}
return d;
});
document.write('delta min: ' + delta + '<br>');
}
result = val.map(function (v, i) {
return v + delta[i];
});
document.write('result: ' + result + '<br>');
the code pushes two too close couples appart with one on each side. this is symetrically and results in sometimes to far pushed values, which can be corrected.
[not implemented!]
if the space of your values is not sufficient, [0..360[ or by more then 72 elements with a difference of 5 the the while loop may not come to an end.
edit: the minimise block should iterate until all values are correted.
To get that "evenly random" distribution, say you have N numbers - split the circle into N segments, then randomly place each number into its segment.
That way you won't even need to care about 0 and 359 being only 1 unit apart.
Here's an idea:
var numbers = 5;
var segment = 360/numbers;
var result = [];
for(var i = 0; i < numbers; i++) {
result.push(Math.round((Math.random() + i) * segment));
}
alert(result.join(','));
Here's a more graphical idea (imagine folding the rectangle into a cylinder):
var numbers = 5;
var segment = 360 / numbers;
var minimum = 15;
var div = document.getElementById('r');
function build() {
var result = [];
div.innerHTML = '';
for (var i = 0; i < numbers; i++) {
var current = 0;
while(current < minimum + (result[result.length - 1] || 0)) {
current = Math.round((Math.random() + i) * segment);
}
result.push(current);
var d = document.createElement('div');
d.className = 'segment';
d.style.left = (result[result.length - 2] || 0) + 'px';
d.style.width = (current - (result[result.length - 2] || 0) - 1) + 'px';
d.textContent = current;
div.appendChild(d);
}
console.log(result.join(','));
}
build();
.segment {
height: 100%;
position: absolute;
font-size: 12px;
text-align: right;
border-right: 1px solid black;
}
#r {
height: 100%;
width: 360px;
background: #eee;
}
html, body {
height: 100%;
margin: 0;
padding: 0;
}
button {
position: absolute;
right: 4px;
margin: 0;
}
<button onclick="build()">Rebuild</button>
<div id="r"></div>
Algorithms that pretty-print graphs use a system of springs to move vertices away from each other when they overlap. Here, you are dealing with just one dimension and may get away with iteratively adjusting nearby angles until all nodes are at least 5 degrees apart.
You can deal with the cyclic values by creating an auxiliary working array, such that the elements are reordered after the largest gap. This allows you to treat the array as linear values without having to care about wrapping:
[2, 7, 320, 359] -> [-40, -1, 2, 7]
The code below does this. The nodes are moved in a rather crude fashion, though: The code only looks at pairs of nodes that are too close. The code can probably be improved by loking at clusters of two or more nodes that are too close to each other:
function adjust(arr, dist)
{
var offset = 0;
var max = 360.0 + arr[0] - arr[arr.length - 1];
var min = max;
var mix = 0; // index of first elment after largest gap
// exit early if array can't be adjusted
if (dist * arr.length > 240.0) return arr;
// find largest gap
for (var i = 1; i < arr.length; i++) {
var d = arr[i] - arr[i - 1];
if (d > max) {
max = d;
mix = i;
}
if (d < min) min = d;
}
var x = []; // working array
var adj = []; // final, adjusted array
// create working array on greatest gap
for (var i = 0; i < arr.length; i++) {
if (i + mix < arr.length) {
x.push(arr[i + mix] - 360);
} else {
x.push(arr[i + mix - arr.length]);
}
}
// iteratively adjust angles
while (min < dist) {
min = dist;
for (var i = 1; i < x.length; i++) {
var d = x[i] - x[i - 1];
if (d < dist) {
if (d < min) min = d;
x[i - 1] -= (dist - d) / 2;
x[i] += (dist - d) / 2;
}
}
}
// create final array
for (var i = 0; i < x.length; i++) {
if (i - mix < 0) {
adj.push(x[i - mix + x.length]);
} else {
adj.push(x[i - mix] + 360);
}
}
return adj;
}
