Convex Hull Using Mouse

by Matthew Vasallo

HTML

<canvas width="300px" height="300px" id="canvas" style="background-color:yellow"></canvas>

JavaScript

//USER DEMO CONFIG
var numberofpoints = 5; //change number of points to draw
var timealert = 0; //set to one to display alert with time taken
//EXAMPLE CODE

var ctx = $('#canvas')[0].getContext("2d");
var points = [];
ctx.canvas.onmousedown = function(evt){
    console.log("event is ", evt);
    ctx.clearRect(0,0,300,300);
    var point = {x:evt.offsetX, y:evt.offsetY};
    points.push(point);
    for (var i = 0; i < points.length; i++) {
        drawPoint(points[i], ctx);
    }
    var hull = convexhull(points);
    for (var h = 1; h < hull.length; h++) {
    drawLine(hull[h - 1], hull[h], ctx);
    }
drawLine(hull[0], hull[hull.length - 1], ctx);
};


var time = Date.now();

var newtime = Date.now();
if (timealert) alert(newtime - time + " ms");

function drawPoint(point, ctx) {
    ctx.fillRect(point.x, point.y, 3, 3);
}

function bigPoint(point, ctx) {
    ctx.fillStyle = "#FF0000";
    ctx.fillRect(point.x, point.y, 6, 6);
}

function drawLine(point1, point2, ctx) {
    ctx.beginPath();
    ctx.moveTo(point1.x, point1.y);
    ctx.lineTo(point2.x, point2.y);
    ctx.stroke();
}

function convexhull(pointset) {
    function sort(ps) {
        return ps.sort(function(a, b) {
            if (a.x == b.x) {           
                return a.y - b.y;                           
            } else {                                                    
                return a.x - b.x;                                                           
            }                                                                                           
        });                                     
    };                      

    function cross(o, a, b) {
        return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); 
    };                          

    pointset = sort(pointset);
    if (pointset.length <= 1) {
        return pointset;
    }   
    var lower = []; 
    for (var l = 0; l < pointset.length; l++) {
        while (lower.length >= 2 &&...