So far i have only come up with the following code. We suppose we have a "list" array that is filled with objects that have ".x" and ".y" properties; a list of droids is a good example. The following code splits it into a 2d array called "clusters", so that each clusters[j] is grouped in the following sense: the distance of any of its elements from its mass center (xav[j],yav[j]) is less than MAX_DISTANCE. It seems to work at O(n^2), where n is the length of the list.
Can this be improved?
Code: Select all
clusters=[];
xav=[];
yav=[];
for (i=list.length-1; i>=0; --i) {
var x=list[i].x,y=list[i].y;
var found=false;
for (var j=0; j<clusters.length; ++j) {
if (distBetweenTwoPoints(xav[j],yav[j],x,y)<MAX_DISTANCE) {
var n=clusters[j].length;
clusters[j][n]=i;
xav[j]=(n*xav[j]+x)/(n+1);
yav[j]=(n*yav[j]+y)/(n+1);
found=true;
break;
}
}
if (!found) {
var n=clusters.length;
clusters[n]=[i];
xav[n]=x;
yav[n]=y;
}
}
