Skip to content

Instantly share code, notes, and snippets.

@ITsvetkoFF

ITsvetkoFF/app

Created February 8, 2015 10:00
Show Gist options
  • Save ITsvetkoFF/ae2feef491e91a5602ef to your computer and use it in GitHub Desktop.
Save ITsvetkoFF/ae2feef491e91a5602ef to your computer and use it in GitHub Desktop.
Download ZIP
comparison of quadtree and plain search performance
Raw
app
var app = angular.module("AspiNodesApp", []);
app.controller('SimulationController', function ($scope) {
$scope.datum = {};
$scope.temp = {};
// Form defaults
$scope.datum.nodeQuantity = '1000'; //4000
$scope.datum.fieldWidth = '500'; //1800
$scope.datum.fieldHeight = '500'; //800
$scope.datum.fieldMaxRange = '30';//50
$scope.datum.fieldMinRange = '30'; //10
$scope.datum.pointData = [];
$scope.datum.populated = false;
$scope.datum.drawEverything = true;
$scope.datum.rangeStepNumber = 1;
$scope.datum.oneRangeStepExperiments = 2;
var euclidDistance = function(ax, ay, bx, by) {
return Math.sqrt(Math.pow(ax - bx, 2) + Math.pow(ay - by, 2));
};
var calculateLinks = function(svg) {
var linkGroup = svg.selectAll("#linkGroup");
return linkGroup.selectAll(".link")[0].length;
};
var calculateDegree = function(svg) {
var linkGroup = svg.selectAll("#linkGroup");
var sum = linkGroup.selectAll(".link")[0].length;
return sum/$scope.datum.nodeQuantity; //WE DO NOT NEED MULTIPLICATION BECAUSE OF DRAWING LINKS TWICE
};
var defineNumberOfDisconnectedNodes = function() {
var defined = false;
var MAIN_GROUP_CAPACITY = 0.8; // main group should contain at least...
var candidatesQuantity = $scope.datum.pointData.length;
var tryN = 0;
var message;
while (!defined) {
tryN++;
var tempMainGroup = [];
var searchStack = [];
var candidateIndex = Math.floor(Math.random() * candidatesQuantity);
var candidate = $scope.datum.pointData[candidateIndex];
searchStack.push(candidate.id);
while (searchStack.length > 0) {
var candidateId = searchStack.pop();
tempMainGroup.push(candidateId);
var arr = $scope.datum.pointData[candidateId].HopOneNeighbors;
if (arr.length>0) {
arr.forEach(function(element, index, array) {
if (tempMainGroup.indexOf(element) == -1 && searchStack.indexOf(element) == -1) {
searchStack.push(element);
}
});
}
};
if (tempMainGroup.length>MAIN_GROUP_CAPACITY*$scope.datum.nodeQuantity) {message = "Connected: "+tempMainGroup.length; defined = true;}
if (tryN == Math.ceil($scope.datum.nodeQuantity)) {message = "No group found!"; break;}
};
return message;
};
var clearNeighborsInfo = function() {
$scope.datum.pointData.forEach(function(element,index,array) {
element.HopOneNeighbors = [];
});
};
var universalDrawLinks = function(experimentElement, algorithm) {
//DEFINE SIMULATION PARAMETERS
var width = parseInt($scope.datum.fieldWidth),
height = parseInt($scope.datum.fieldHeight);
var minR = parseInt($scope.datum.fieldMinRange),
maxR = parseInt($scope.datum.fieldMaxRange);
var nQ = parseInt($scope.datum.nodeQuantity);
var svg = experimentElement.append("svg");
var linkGroup = svg.append('g').attr("id","linkGroup");
svg.attr("width", width)
.attr("height", height);
var point = svg.selectAll(".point")
.data($scope.datum.pointData)
.enter().append("circle")
.attr("class", "point")
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; })
.attr("r", function(d) { return d.r; });
clearNeighborsInfo();
//passing pointData for quadtree
var qData = $scope.datum.pointData.map(function(one) {
return [one.x,one.y,one.r,one.id];
});
// Create quadtree
var quadtree = d3.geom.quadtree()
.extent([[-1, -1], [$scope.datum.fieldWidth + 1, $scope.datum.fieldHeight + 1]])
(qData);
// Collapse the quadtree into an array of rectangles
function nodes(quadtree) {
var nodes = [];
quadtree.visit(function(node, x1, y1, x2, y2) {
nodes.push({x: x1, y: y1, width: x2 - x1, height: y2 - y1});
});
return nodes;
}
if ($scope.datum.drawEverything) {
var linkGroup = svg.selectAll("#linkGroup");
linkGroup.html('');
// Draw rectangles
//linkGroup.selectAll(".node")
// .data(nodes(quadtree))
// .enter().append("rect")
// .attr("class", "node")
// .attr("x", function (d) {
// return d.x;
// })
// .attr("y", function (d) {
// return d.y;
// })
// .attr("width", function (d) {
// return d.width;
// })
// .attr("height", function (d) {
// return d.height;
// });
}
//////////////////////////////////////////////////////////////////////////////
///////////////////////HERE IS THE ALGORITHM//////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
var search = algorithm(linkGroup);
var point = svg.selectAll(".point");
point.each(function(d,i) {
// helper
//console.log(d + " " + i + " this:" + this);
// 448.97178455721587,48.42824942898005 9 this:[object SVGCircleElement]
$scope.temp.that = d;
search(quadtree, d.x-d.r, d.y-d.r, d.x+d.r, d.y+d.r);
});
var linksMessage = calculateLinks(svg);
var degreeMessage = calculateDegree(svg);
var connectionMessage = defineNumberOfDisconnectedNodes();
var resultThis = experimentElement.append("div");
resultThis.text("Links: " + linksMessage + " | Degree: " + degreeMessage + "| " + connectionMessage);
};
//start sim with parameters variation
$scope.startSim = function() {
var nOfExp = parseInt($scope.datum.oneRangeStepExperiments);
var simParameters = generateParameters();
simParameters.forEach(function(parameterSet,index,arr){
var i;
for(i = 0; i<nOfExp; i++){
$scope.populate(parameterSet.minR, parameterSet.maxR);
}
});
};
var generateParameters = function() {
var arrayOfParameters = [];
var minR = parseInt($scope.datum.fieldMinRange),
maxR = parseInt($scope.datum.fieldMaxRange),
steps = parseInt($scope.datum.rangeStepNumber);
if (steps == 1) {arrayOfParameters.push({minR: minR, maxR:maxR});}
else if (steps > 1) {
var averageR = (maxR+minR)/2;
var delta = (maxR-minR)/2;
var i;
for(i = 0; i<steps; i++){
arrayOfParameters.push({minR: averageR-(delta*i/steps), maxR:maxR+(delta*i/steps)});
}
}
return arrayOfParameters;
};
// Only generates pointData: x,y,r,id,1hop(empty object)
$scope.populate = function (minR, maxR) {
var start = new Date().getTime();
var oneExperiment = d3.select("body").append("div").attr("class", "oneExperiment");
var ex1 = oneExperiment.append("div").attr("class","noPlanarization Planarization");
var ex2 = oneExperiment.append("div").attr("class","RNGPlanarization Planarization");
var ex3 = oneExperiment.append("div").attr("class","GGPlanarization Planarization");
oneExperiment.append("div").attr("style","clear:both");
//DEFINE SIMULATION PARAMETERS TODO - define them here and pass to universalDrawer somehow
var width = parseInt($scope.datum.fieldWidth),
height = parseInt($scope.datum.fieldHeight);
var nQ = parseInt($scope.datum.nodeQuantity);
var pointData = d3.range(nQ).map(function (element,index) {
return {"x":Math.random() * width,
"y":Math.random() * height,
"r":Math.random() * (maxR - minR) + minR,
"id":index,
"HopOneNeighbors":[]};
});
// Share data
$scope.datum.pointData = pointData;
///DRAW THREE types here
[ex1,ex2,ex3].forEach(function(experimentElement, index) {
if (index==0) {performNothing(experimentElement);}
if (index==1) {performRNGPlanarization(experimentElement);}
if (index==2) {performGGPlanarization(experimentElement);}
}
);
var time = new Date().getTime() - start;
console.log("Population is finished in " + time + "ms");
};
$scope.hideNeighbors = function () {
linkGroup.html('');
};
// This is not a simulation - just display links!
var performNothing = function (svgHolder) {
var noPlanarizatioin = function(linkGroup) {
function search(quadtree, x0, y0, x3, y3) {
quadtree.visit(function (node, x1, y1, x2, y2) {
var p = node.point;
if (p) {
var xp = (x0+x3)/2;
var yp = (y0+y3)/2;
var rp = Math.abs(xp-x0);
var xn = p[0];
var yn = p[1];
var rn = p[2];
var distToDraw = euclidDistance(xp,yp,xn,yn);
if (Math.min(rn,rp)>distToDraw && distToDraw != 0) {
if ($scope.datum.drawEverything) {
linkGroup.append("line")
.attr("x1", p[0])
.attr("y1", p[1])
.attr("x2", xp)
.attr("y2", yp)
.attr("class","link");
}
$scope.temp.that.HopOneNeighbors.push(p[3]);
}
}
return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0
});
};
return search;
};
universalDrawLinks(svgHolder, noPlanarizatioin);
};
var performRNGPlanarization = function(svgHolder) {
var RNGPlanarization = function(linkGroup) {
function search(quadtree, x0, y0, x3, y3) {
quadtree.visit(function (node, x1, y1, x2, y2) {
var p = node.point;
if (p) {
var xp = (x0+x3)/2;
var yp = (y0+y3)/2;
var rp = Math.abs(xp-x0);
var xn = p[0];
var yn = p[1];
var rn = p[2];
var dis = euclidDistance(xp,yp,xn,yn);
// Draw links if both see each other
var flag = false;
if (Math.min(rn,rp)>dis && dis>0) {
flag = true;
// Center of possible search zone
var iXc = (xp + xn) / 2;
var iYc = (yp + yn) / 2;
quadtree.visit(function (midNode, x1, y1, x2, y2) {
var pInner = midNode.point;
if (pInner) {
var xInner = pInner[0];
var yInner = pInner[1];
var d1 = euclidDistance(xInner, yInner, xn, yn);
var d2 = euclidDistance(xInner, yInner, xp, yp);
if (d1 > 0 && d2 > 0) {
// If it is in zone
if (dis > Math.max(d1, d2)) {
flag = false;
}
}
}
// Condition to move only around possible figure
return x1 >= iXc + dis || y1 >= iYc + dis || x2 < iXc - dis || y2 < iYc - dis
});
}
if (flag === true) {
if ($scope.datum.drawEverything) {
linkGroup.append("line")
.attr("x1", xn)
.attr("y1", yn)
.attr("x2", xp)
.attr("y2", yp)
.attr("class", "link");
}
$scope.temp.that.HopOneNeighbors.push(p[3]);
}
}
return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0
});
};
return search;
};
universalDrawLinks(svgHolder,RNGPlanarization);
};
var performGGPlanarization = function(svgHolder) {
var GGPlanarization = function(linkGroup) {
function search(quadtree, x0, y0, x3, y3) {
quadtree.visit(function (node, x1, y1, x2, y2) {
var p = node.point;
if (p) {
var xp = (x0+x3)/2;
var yp = (y0+y3)/2;
var rp = Math.abs(xp-x0);
var xn = p[0];
var yn = p[1];
var rn = p[2];
var dis = euclidDistance(xp,yp,xn,yn);
// Draw links if both see each other
var flag = false;
if (Math.min(rn,rp)>dis && dis>0) {
flag = true;
// Center of possible search zone
var iXc = (xp + xn) / 2;
var iYc = (yp + yn) / 2;
quadtree.visit(function (midNode, x1, y1, x2, y2) {
var pInner = midNode.point;
if (pInner) {
var xInner = pInner[0];
var yInner = pInner[1];
var dm = euclidDistance(xInner, yInner, iXc, iYc);
if (dm > 0) {
// If it is in zone
if (dis/2 > dm) {
flag = false;
}
}
}
// Condition to move only around possible figure
return x1 >= iXc + dis || y1 >= iYc + dis || x2 < iXc - dis || y2 < iYc - dis
});
}
if (flag === true) {
if ($scope.datum.drawEverything) {
linkGroup.append("line")
.attr("x1", xn)
.attr("y1", yn)
.attr("x2", xp)
.attr("y2", yp)
.attr("class", "link");
}
$scope.temp.that.HopOneNeighbors.push(p[3]);
};
}
return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0
});
};
return search;
};
universalDrawLinks(svgHolder,GGPlanarization);
};
var oneStep = function () {
var point = svg.selectAll(".point");
// для каждого узла происходит переход состояний
//
point.each(function(d,i) {
// helper
// console.log(d + " " + i + " this:" + this);
// 448.97178455721587,48.42824942898005 9 this:[object SVGCircleElement]
//search(quadtree, d.x-d.r, d.y-d.r, d.x+d.r, d.y+d.r);
});
};
});
Raw
index
<html>
<head>
<title>App</title>
<style>
svg {margin-right: 10px;}
.left-col {
width: 150px;
float: left;
margin-right: 10px;
}
.right-col {
float: left;
}
input[type='checkbox'] {height: 1.5em; width: 1.5em; margin:0px;}
input[type='text'], button, .right-col, .left-col {height: 30px;}
input[type='text'] {padding-left: 6px; width: 80px;}
input.stepRangesChange {
height: 1.3em;
width:30px;
padding-left: 0px;
text-align: center;}
label.left-col {
text-align: right;
padding-top: 7px;
}
label.upperLabel input[type='checkbox'] {position: relative; top:4px;}
label.upperLabel input[type='checkbox']:hover {
cursor: pointer;}
label.upperLabel:hover {
cursor: pointer;}
.clear {
clear: both
}
.separator {
height: 0px;
position: relative;
}
button {margin-left: 0px;}
.point {
fill: rgba(0,0,0,0.01);
stroke: rgba(0,0,0,0.1);
}
.point.scanned {
fill: orange;
fill-opacity: 1;
stroke: brown;
}
.point.selected {
fill: red;
fill-opacity: 1;
}
.node {
fill: none;
stroke: #eee;
shape-rendering: crispEdges;
}
.link {
stroke: rgba(0,0,0,0.5);
stroke-width: 1px;
z-index: 5;
}
.link-elemenated {
stroke: rgba(228,0,0,0.1);
stroke-width: 3px;
z-index: 4;
}
.populator {
color: royalblue;
text-decoration: underline;
}
.populator:hover {
cursor: pointer;}
.resultBlock {background-color: #eee; padding:10px; box-sizing: border-box; margin-bottom: 10px;}
.stepRanges {
position: absolute;
left:250px; padding: 20px 10px; top:2px; border-left: solid 3px #eeeeee;}
.manual-controls {margin:15px 0px;}
.semi-transparent {opacity: 0.4;}
.Planarization {float:left;}
.oneExperiment {clear: both; margin-top: 20px;}
table, td,tr {border: 1px solid #000000;}
td {height:20px;}
</style>
</head>
<body ng-app="AspiNodesApp" ng-controller="SimulationController">
<h1>Please, choose simulation parameters and <span class = "populator" ng-click="startSim()">start</span>
<!--| draw <input type="checkbox" ng-model="datum.drawEverything"> // THIS IS INTENDED TO AVOID DRAWING - TODO -->
</h1>
<div>
<form name="form" novalidate>
<label class = "upperLabel semi-transparent" ><input type="checkbox" ng-model="showTheControls" ng-init="showTheControls = true"> Show controls </label>
<div class="clear separator"></div>
<div class = "control-group" ng-show="showTheControls">
<label class="left-col" for="inputNodeQuantity">Number of nodes:</label>
<input id="inputNodeQuantity" type="text" ng-model="datum.nodeQuantity" required />
<div class="clear separator">
<label class="left-col" for="inputFieldWidth">Field width (m):</label>
<input id="inputFieldWidth" type="text" ng-model="datum.fieldWidth" required />
</div>
<div class="clear separator">
<label class="left-col" for="inputFieldHeight">Field height (m):</label>
<input id="inputFieldHeight" type="text" ng-model="datum.fieldHeight" required />
</div>
<div class="clear separator">
<label class="left-col" for="inputFieldMaxRange">Maximum range (m):</label>
<input id="inputFieldMaxRange" type="text" ng-model="datum.fieldMaxRange" required/>
<div class="stepRanges">
Step ranges from average value to these two in
<input class="stepRangesChange" type="text" ng-model="datum.rangeStepNumber"/> steps,
performing <input class="stepRangesChange" type="text" ng-model="datum.oneRangeStepExperiments"/> simulations on each step
</div>
</div>
<div class="clear separator">
<label class="left-col" for="inputFieldMinRange">Minimum range (m):</label>
<input id="inputFieldMinRange" type="text" ng-model="datum.fieldMinRange" required/>
</div>
<div class="clear separator"></div>
</div>
</form>
<div class="manual-controls" ng-show="false"> <!--datum.populated-->
<label class="left-col" ><strong>Manual actions:</strong></label>
<button ng-click="performNothing()">No planarization</button>
<!--<button ng-click="hideNeighbors()" ng-show="datum.populated">Hide neighbors</button>-->
<button ng-click="performRNGPlanarization()">RNG planarization</button>
<button ng-click="performGGPlanarization()">GG planarization</button>
</div>
</div>
<script src="libs/http_underscorejs.org_underscore.js"></script>
<script src="libs/http_ajax.googleapis.com_ajax_libs_angularjs_1.2.23_angular.js"></script>
<script src="libs/http_d3js.org_d3.v3.js" charset="utf-8"></script>
<script src="app.js"></script>
<!--
<script src="services.js"></script>
-->
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment