Finding 2D convex hull using Graham scan in Javascript
HTML
<script src="http://psychedelicdevelopment.com/grahamscan/grahamscan.js"></script>
<canvas id="canvas" width="300" height="300"></canvas>
<br />
<input id="numpoints" type="text" value="50" size="4" />
<button id="generate">Generate new set of points</button>
<button id="find">Find convex hull</button>
JavaScript
var points = new Array();
function dot(ctx, point, style) {
ctx.save();
ctx.fillStyle = style;
ctx.beginPath();
ctx.arc(point.x, point.y, 2, 0, Math.PI * 2, true);
ctx.closePath();
ctx.fill();
ctx.restore();
}
function draw() {
var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
ctx.save();
ctx.setTransform(1, 0, 0, 1, 0, 0);
ctx.clearRect(0, 0, canvas.width, canvas.height);
ctx.restore();
for (var i = 0; i < points.length; i++) {
dot(ctx, points[i], "rgba(0, 128, 0, 0.8)");
}
}
function doSetTimeout() {
setTimeout(function() {
var a = 1;
}, 100);
}
function findHull() {
var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
var hull = new ConvexHull();
hull.compute(points);
var indices = hull.getIndices();
if (indices && indices.length > 0) {
ctx.beginPath();
ctx.moveTo(points[indices[0]].x, points[indices[0]].y);
for (var i = 1; i < indices.length; i++) {
ctx.lineTo(points[indices[i]].x, points[indices[i]].y);
}
ctx.closePath();
ctx.fillStyle = "rgba(200, 0, 0, 0.2)";
ctx.strokeStyle = "rgba(0, 0, 0, 0.5)";
ctx.fill();
ctx.stroke();
for (var j = 0; j < indices.length; j++) {
dot(ctx, points[indices[i]], "rgba(200, 0, 0, 0.8)");
doSetTimeout();
}
}
}
function generate() {
points = new Array();
var numpoints = document.getElementById("numpoints").value;
for (var i = 0; i < numpoints; i++) {
var pt = {
x: 10 + Math.random() * 270,
y: 10 + Math.random() * 270
};
points.push(pt);
}
}
$(function(){
generate();
draw();
$("#generate").on('click', function(){
generate();
draw();
});
$("#find").on('click', function(){
draw();
findHull();
});
});