related.js

(Entry Nr. 494, by user 39 | edit)

/******************************************************************************
 * animated item relationship distance map
 *
 * Part of Gnod, the Global Network of Dreams. (c) Marek Gibney
 * 
 * Animates html elements with id's "s0", "s1",...
 *
 * Tries to keep the distances between them as given by an array gnodMap.aid[][],
 * where aid[4][7] is the proposed distance "s4" should have to "s7".
 * 
 * The element with id "s0" allways stays in the center.
 *
 * settings can be made by altering several values in gnodMap, e.g.
 *  gnodMap.scale=0.4; // makes the map smaller
 * 
 * DEPRECATED (see also end of this file):
 * settings can be set via a global object "gnodMapSettings":
 * * minX, maxX, minY, maxY: boundaries of drawing area
 * * offsetX, offsetY: move center out of the drawing area's center.
 * * nrItems: maximum number items to be displayed, even if Aid[][] is larger
 *
 *
 *****************************************************************************/

/** 
  * A moving HTML element
  */
function mg_2d_element(id)
{
 this.id=id;
 this.x=0;
 this.y=0;
 this.speedX=0;
 this.speedY=0;
 this.element=document.getElementById("s"+this.id);
 this.name=this.element.innerHTML;
 this.width =this.element.offsetWidth;
 this.height=this.element.offsetHeight;
 this.inertia=0.7;
 
 this.update=function(damper)
 {
  this.element.style.left=this.x-this.width /2;
  this.element.style.top =this.y-this.height/2;
  this.x+=this.speedX/damper;
  this.y+=this.speedY/damper;

this.speedX*=this.inertia;
  this.speedY*=this.inertia;
 }
}

function GnodMap()
{

this.aid=null;                // aid[i1][i2]: proposed similarity between the two items i1, i2.
 this.maxItems=0;              // max. number of items to draw. if set to 0, dimension of aid[] is used.

// adjustable constants ------------------------------------------------------

// window size and scaling
 this.left             =0;     // left border of drawing area
 this.top              =0;     // top border of drawing area
 this.bottom           =0;     // bottom border, automatically detected if not set.
 this.right            =0;     // right border, automatically detected if not set.
 this.offsetX          =0;     // x displace central item
 this.offsetY          =0;     // y displace central item
 this.scaleFactor      =1.4;   // scaling in respect to calculated window space
 this.scaleByCenterDist=-1;    // scaling in respect to mean target center distance (mean aid[i][0])

// timing
 this.frameDelayInitial=25;    // initial value of increasing delay at each timestep
 this.slowdownCycle    =300;   // number of timesteps after that delay is increased

// physics
 this.inertia          =0.7;   // part of velocity kept in one timestep 
 this.damperInitial    =1;     // initial value of increasing damper that cool down motion with time
 this.damperFactor     =1.002; // factor the damper is increased by in one timestep
 this.damperMax        =100;   // max. value of damper
 this.springForce0     =0.025; // force between each item and the central item s0 trying to keep them at aid[][]-distance
 this.springForce      =0.005; // force between each item pair except the central item s0
 this.centeringForce   =0.1;   // force that pulls the center of gravity towards the central item

// overlap avoiding
 this.repelDelay       =200;   // nr. of timesteps without repulsion
 this.repelIncrease    =0.001; // amount the repelling force that keeps items non overlapping increases each timestep
 this.repelMax         =0.15;  // max amount of repelling force. 
 this.paddingFactor    =1;     // factor by which an item is enlarged while avoiding overlap

// ----------------------------------------------------------------------------

var nrItems;                // number of items to layout
 var maxX, maxY, minX, minY; // bounds of drawing area
 var scaleX,scaleY;          // scale to make anything fit
 var cogX, cogY;             // center of gravity of all items
 var cycle=0;                // refresh cycle counter
 var frameDelay;             // delay between redraws
 var damper;                 // increasing damper to cool down motion
 var repel;                  // increasing force that repells items to not overlap each other

/**
  * update minX,minY,maxX,maxY to window size 
  * may be overridden by gnodMapSettings
  */
 this.updateBoundaries=function()
 {
  minX=this.left;
  minY=this.top;

var haveIE4orNewer = (document.all) ? 1 : 0;
  if (haveIE4orNewer)
  {
   maxX = document.body.clientWidth;
   maxY = document.body.clientHeight;
  }
  else
  {
   maxX = window.innerWidth;
   maxY = window.innerHeight;
  }

if (this.right ) maxX=this.right ;
  if (this.bottom) maxY=this.bottom;
 }

/**
  * returns the mean item dimensions (width, height)
  */
 this.getMeanItemSize=function()
 {
  var meanW=0, meanH=0;

for (i=1;i<nrItems;i++)
  {
   meanW+=items[i].width;
   meanH+=items[i].height;
  } 
  meanW/=nrItems;
  meanH/=nrItems;
  
  return {width: meanW, height: meanH};
 }

/**
  * sets scaleX, scaleY in relation to window size, proposed item distance, mean item size, parameters.
  */
 this.updateScale=function()
 {
  var scale            =this.scaleFactor*(1+this.scaleByCenterDist*this.meanTargetCenterDistance());
  var meanSize         =this.getMeanItemSize();

scaleX=(maxX-minX-meanSize.width )*scale;
  scaleY=(maxY-minY-meanSize.height)*scale;
 }

/**
  * update boundaries to window size and place items at initial positions
  */
 this.resetItemPositions=function()
 {
  this.updateBoundaries();

items=new Array();
  items[0]=new mg_2d_element(0);

// center item0
  items[0].x=minX+(maxX-minX)/2;
  items[0].y=minY+(maxY-minY)/2;

if (this.offsetX) items[0].x+=this.offsetX;
  if (this.offsetY) items[0].y+=this.offsetY;

for (i=1;i<nrItems;i++)
  {
   items[i]=new mg_2d_element(i);
   items[i].inertia=this.inertia;

//initially place elements on a small circle:
   items[i].x=items[0].x+Math.sin(i);
   items[i].y=items[0].y+Math.cos(i);
  }

this.updateScale();

cogX=items[0].x;
  cogY=items[0].y;
  cycle=0;
  frameDelay=this.frameDelayInitial;
  damper=this.damperInitial;
  repel=0;
 }

/**
  * recenter items by moving their center of gravity towards item[0].
  */
 this.recenterItems=function()
 {
  var forceX=(items[0].x-cogX)*this.centeringForce;
  var forceY=(items[0].y-cogY)*this.centeringForce;
  for (var i=1; i<nrItems; i++)
  {
   items[i].x+=forceX;
   items[i].y+=forceY;
  }
 }

/**
  * update item positions and cogX, cogY.
  *
  * first checks all items against boundaries and push them back if needed
  */
 this.updateItems=function()
 {
  cogX=0; cogY=0;

for (var i=0; i<nrItems; i++)
  {
   var w=items[i].width /2;
   var h=items[i].height/2;
   if (items[i].x+w>maxX) items[i].x=maxX-w;
   if (items[i].x-w<minX) items[i].x=minX+w;
   if (items[i].y+h>maxY) items[i].y=maxY-h;
   if (items[i].y-h<minY) items[i].y=minY+h;

cogX+=items[i].x;
   cogY+=items[i].y;

items[i].update(damper);
  }
  cogX/=nrItems; 
  cogY/=nrItems;
 }

/**
  * calculate min of all positive values of an array
  */
 function positiveMin(values)
 {
  var r=Number.MAX_VALUE;
  for (var i=0; i<values.length; i++)
   if (values[i]>=0 && values[i]<r) r=values[i];

return r;
 }

/**
  * update position of all items 
  * 
  * * pull items toward target distance stored in aim[][]
  * * push items to not overlap each other.
  */
 this.layoutItems=function()
 {
  for(i1=1; i1<nrItems; i1++)
  {
   for(i2=0; i2<nrItems; i2++) 
   {
    if (i2==i1) continue;

this.adjustItemDistance(items[i1], items[i2]);
    this.repelItems        (items[i1], items[i2]);
   }
  }
 }

/**
  * move two items towards their proposed distance in aim[][].
  */
 this.adjustItemDistance=function(item1, item2)
 {
  var targetDistance=this.aid[item1.id][item2.id];
  if(targetDistance<=0) return;

var dx=item1.x-item2.x;
  var dy=item1.y-item2.y;

var forceFactor;
  if   (item2.id==0) forceFactor=this.springForce0;
  else               forceFactor=this.springForce;

// measure distance in both axes independently in respect to window width and height
  var wdx=dx/scaleX;
  var wdy=dy/scaleY;
  var distanceInWindowSpace=Math.sqrt(wdx*wdx+wdy*wdy);
  var force=(targetDistance-distanceInWindowSpace)*forceFactor;

item1.speedX+=dx/distanceInWindowSpace*force;
  item1.speedY+=dy/distanceInWindowSpace*force;
 }

/** 
  * push items to not overlap each other
  */
 this.repelItems=function(item1, item2)
 {
  var dx=item1.x-item2.x;
  var dy=item1.y-item2.y;

//calculate extents of the items from their centers
  var extentsSumX=(item1.width +item2.width) *this.paddingFactor/2;
  var extentsSumY=(item1.height+item2.height)*this.paddingFactor/2;

// calculate overlapping on all four borders
  var oLeft  =-dx+extentsSumX;
  var oRight = dx+extentsSumX;
  var oTop   =-dy+extentsSumY;
  var oBottom= dy+extentsSumY;

var no_overlap = oLeft<0 || oRight<0 || oTop<0 || oBottom<0;

if (repel>0 && !no_overlap)
  {
   // calculate minimal overlapping
   var oMin=positiveMin(Array(oLeft, oRight, oTop, oBottom));

var distance=Math.sqrt(dx*dx+dy*dy);

// repel item in respect to current overlapping
   // we assume that dx,dy is a useful direction to decrease the overlapping
   var repelScaler=repel*oMin/distance;
   item1.x+=dx*repelScaler;
   item1.y+=dy*repelScaler;
  }
 }

/**
  * do one layout step. 
  */
 this.layoutStep=function ()
 {
  this.layoutItems();
  this.recenterItems();
  this.updateItems();

if (damper<this.damperMax)                        damper=damper*this.damperFactor;
  if (cycle>this.repelDelay && repel<this.repelMax) repel+=this.repelIncrease;
  if (cycle>this.slowdownCycle)                     frameDelay++;
  
  cycle++;
  
  // schedule next layout step
  var thisMap=this;
  setTimeout(function(){thisMap.layoutStep()},frameDelay); 
 }

this.sum_of_squared_errors=function()
 {
  var error0=0, error=0;
  for(i1=0; i1<nrItems; i1++)
  {
   for(i2=i1+1; i2<nrItems; i2++) 
   {
    var targetDistance=this.aid[i1][i2];
    if(targetDistance<=0) continue;

var dx=items[i1].x-items[i2].x;
    var dy=items[i1].y-items[i2].y;

// measure distance in both axes independently in respect to window width and height
    var wdx=dx/scaleX;
    var wdy=dy/scaleY;
    var distanceInWindowSpace=Math.sqrt(wdx*wdx+wdy*wdy);
    var tmp=targetDistance-distanceInWindowSpace;
    error+=tmp*tmp;
    if (i1==0) error0+=tmp*tmp;
   }
  } 
  return {error: error, error0: error0};
 }

this.meanTargetCenterDistance=function()
 {
  var r=0;

for(i1=1; i1<nrItems; i1++) r+=this.aid[i1][0];
  r/=(nrItems-1);
  
  return r;
 }

this.keyPress=function(event)
 {
  if (!event) event=window.event;
  if (!event.ctrlKey) return;
  if (event.which) key=event.which;
  else             key=event.keyCode;
  if (key!=105) return;

var errors=this.sum_of_squared_errors();

var info="Infos:\n";
  info+="Cycle: "+cycle+"\n";
  info+="Mean target center distance: "+this.meanTargetCenterDistance()+"\n";
  info+="Sum of Squared Errors of all items: "+errors.error+"\n";
  info+="Sum of Squared Errors of center item: "+errors.error0+"\n";
  alert (info);
  return false;
 }

/**
  * find needle in sorted array haystack
  */
 function search(needle, haystack) {
  var low=0;
  var high=haystack.length-1;

while (low<=high)
  {
   var mid   = parseInt((low+high)/2);
   var value = haystack[mid];

if      (value>needle) high=mid-1;
   else if (value<needle) low =mid+1;
   else    return mid;
  }

return -1;
 }

/**
  * replace values of aid[][] with equally dense values in the range 0.0-1.0
  * the smallest item becomes 1.0, the largest 0.0. 
  */
 this.equalizeAid=function()
 {
  var values=new Array();

//build array of all used values
  for (var i=0; i<nrItems; i++)
   for (var j=0; j<nrItems; j++)
    if (this.aid[i][j]>0) values.push(this.aid[i][j]);

values.sort();

//assign each aid[][] the rank of its value in values[] normalized to 0.0...1.0
  for (var i=0; i<nrItems; i++)
   for (var j=0; j<nrItems; j++)
    if (this.aid[i][j]>0) 
    {
     this.aid[i][j]=1-(search(this.aid[i][j], values)/values.length);
    }
 }

/**
  * initially place every item and start refresh timer.
  */
 this.init=function ()
 {
  // Even though init() gets called on window.onload, in IE it sometimes
  // gets started with a screen size of 0. If so, we try again later:
  this.updateBoundaries();
  if (maxX<1 || maxY<1)
  {
   setTimeout(function(){gnodMap.init()},500);
   return;
  }

nrItems=this.aid[0].length;
  if (this.maxItems && nrItems>this.maxItems) nrItems=this.maxItems;
  
  this.equalizeAid();
  this.resetItemPositions();

setTimeout(function(){gnodMap.layoutStep()},10); // let's go.
 }

// ----------------------------------------------------------------------------
 // install event handlers.
 //
 // instead of calling init directy, we attach it to the window.onload event
 // especially when the map is loaded, the screensize might not be set
 // before that event

var thisMap=this;

window.onload=function()
 {
  thisMap.init();
 }

document.onkeypress=function(event)
 {  
  return thisMap.keyPress(event);
 }

window.onresize=function()
 {
  thisMap.resetItemPositions();
 }
}

gnodMap=new GnodMap();

//assign deprecated global settings:
gnodMap.aid=Aid;
gnodMap.maxItems=gnodMapSettings.nrItems;
gnodMap.left    =gnodMapSettings.minX;
gnodMap.top     =gnodMapSettings.minY;
gnodMap.right   =gnodMapSettings.maxX;
gnodMap.bottom  =gnodMapSettings.maxY;
gnodMap.offsetX =gnodMapSettings.offsetX;
gnodMap.offsetY =gnodMapSettings.offsetY;

Create a new entry at this position