Algorithm

How to draw a circle – 2

dondonliuLeave a comment

Since we know what a circle looks like, why don’t we directly plot each point since we know x must span from [x-x0,x+x0]?

  y = y0 +/- sqrt(r*r-(x-x0)(x-x0))


<!DOCTYPE html>
<html>
<head>
<script>
function plotPoint(ctx,x,y) {
  ctx.fillRect(x,y,1,1);
}

function getRandomInt (min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function drawRandom() {
   var c=document.getElementById("myCanvas");
  var ctx=c.getContext("2d");
  drawCircle(getRandomInt(100,800),getRandomInt(100,400),getRandomInt(50,100),ctx);
}
function drawCircle(x0,y0,r,ctx) {
  var r2=r*r;
  var step=.1;
  var y;
  for(var x=x0-r;x<=x0+r;x+=step) {
    var dx2 = (x-x0)*(x-x0);
    y = y0 + Math.sqrt(r2-dx2);
    plotPoint(ctx,x,y);
    y = y0 - Math.sqrt(r2-dx2);
    plotPoint(ctx,x,y);
  }
}

function draw() {
  var c=document.getElementById("myCanvas");
  var ctx=c.getContext("2d");

try {
  var x0 = parseInt(document.getElementById('x0').value);
  var y0 = parseInt(document.getElementById('y0').value);
  var r = parseInt(document.getElementById('r').value);
  if ('NaN' == x0||'NaN'==y0||'NaN'==r) return;
  drawCircle(x0,y0,r,ctx);
  
} catch(err) {
  alert(err);
}

}
</script>
</head>
<body>

X0: <input type=text id=x0 value=300 size=3 />
Y0: <input type=text id=y0 value=300 size=3 />
R: <input type=text id=r value=100 size=3 />
<input type=button value="draw a circle" onclick="javascript:draw()"/>
<input type=button value="draw a random circle" onclick="javascript:drawRandom()"/>

<p>

<canvas id="myCanvas" width="800" height="600" style="border:1px solid #d3d3d3;">
Your browser does not support the HTML5 canvas tag.</canvas>

</p>


</body>
</html>

How to draw a circle

dondonliuLeave a comment

update: turns out this is really a dumb idea.

Here’s the code to draw a circle in relatively OK time (apparently not the optimal solution but I don’t have enough graphics background to come up with one).

We know the equation for circles are:

  (x-x0)(x-x0) + (y-y0)(y-yo) = r*r

(x0,y0) being the center and r being the radius.


<!DOCTYPE html>
<html>
<head>
<script>
function plotPoint(ctx,x,y) {
  ctx.fillRect(x,y,1,1);
}
function onCircle(x,y,x0,y0,r) {
  var dx=x-x0;
  var dy=y-y0;
  var eps=20;
  if( Math.abs(r*r-dx*dx-dy*dy)<=eps) return true;
  return false;
}

function getRandomInt (min, max) {
    return Math.floor(Math.random() * (max - min + 1)) + min;
}

function drawRandom() {
   var c=document.getElementById("myCanvas");
  var ctx=c.getContext("2d");
  drawCircle(getRandomInt(100,800),getRandomInt(100,400),getRandomInt(50,100),ctx);
}

function drawCircle(x0,y0,r,ctx) {
  var r2=r/Math.sqrt(2);
  var step=.2;
  for(var x=x0-r;x<=x0-r2;x+=step) {
     for(var y=y0-r;y<=y0+r;y+=step) {
       if(onCircle(x,y,x0,y0,r))
         plotPoint(ctx,x,y);
     }
  }
    for(var x=x0+r2;x<=x0+r;x+=step) {
     for(var y=y0-r;y<=y0+r;y+=step) {
       if(onCircle(x,y,x0,y0,r))
         plotPoint(ctx,x,y);
     }
  }
    for(var x=x0-r;x<=x0+r;x+=step) {
     for(var y=y0-r;y<=y0-r2;y+=step) {
       if(onCircle(x,y,x0,y0,r))
         plotPoint(ctx,x,y);
     }
  }
    for(var x=x0-r;x<=x0+r;x+=step) {
     for(var y=y0+r2;y<=y0+r;y+=step) {
       if(onCircle(x,y,x0,y0,r))
         plotPoint(ctx,x,y);
     }
  }
}

function draw() {
  var c=document.getElementById("myCanvas");
  var ctx=c.getContext("2d");

try {
  var x0 = parseInt(document.getElementById('x0').value);
  var y0 = parseInt(document.getElementById('y0').value);
  var r = parseInt(document.getElementById('r').value);
  if ('NaN' == x0||'NaN'==y0||'NaN'==r) return;
  drawCircle(x0,y0,r,ctx);
  
} catch(err) {
  alert(err);
}

}
</script>
</head>
<body>

X0: <input type=text id=x0 value=300 size=3 />
Y0: <input type=text id=y0 value=300 size=3 />
R: <input type=text id=r value=100 size=3 />
<input type=button value="draw a circle" onclick="javascript:draw()"/>
<input type=button value="draw a random circle" onclick="javascript:drawRandom()"/>

<p>

<canvas id="myCanvas" width="800" height="600" style="border:1px solid #d3d3d3;">
Your browser does not support the HTML5 canvas tag.</canvas>

<script>


</script> 
</p>

</body>
</html>

Pagerank in Hadoop

dondonliuLeave a comment

How Pagerank works:

for node(A), its pagerank score is computed as:


pr(A) = (1-d)/N + d (pr(A1)/L(A1)+pr(A2)/L(A2)+...)

A1,A2,… are node A’s neighbors (incoming nodes). L(A1) is number of A1’s neighbors. N is number of nodes.

Assume in input graph for each node you have its outgoing edges (this is the way I assume Linkedin data. I will try both and see the difference). What we have to know before the computation:

  1. N, the number of all nodes
  2. Pr(A), each node’s initial score
  3. each Node’s outgoing edges(nodes)

Input:

Node_A Pr(A) A1 A2 ...

Mapper:

output:

A1 p Pr(A)/L(A)
A2 p Pr(A)/L(A)
..
A d A1
A d A2
...

‘p’ means pagerank score that goes to node A2

‘d’ means there’s an edge from A to A1

Reducer:

since a node’s all incoming nodes are grouped in the same reducer, updates its pr score and graph structure:


if 'p': pr(A1) += score (A1)
if 'd': add A1 to A's outgoing edges

and output:

Node_A Pr(A) A1 A2 ...