Quickhull (Javascript)

From LiteratePrograms

Other implementations: Javascript | Python, arrays

Contents - Quickhull (Javascript) 1 Quickhull demonstration using javascript and canvas tag 1.1 Distant function 1.2 The recursive quickhull algorithm implementation 1.3 Get it started 1.4 Utilities for showing animation in a HTML canvas tag 1.5 The minimum HTML to run the code 1.6 Example

Quickhull demonstration using javascript and canvas tag Distant function

This code demonstrate the procedure to construct a convex hull using quickhull algorithm. When the main javascript code is triggered by a button, the intermediate base edges will be plotted. At the end, the convex hull is highlighted in red.

First of all, we need a function to calculate the distant from a point to a base edge and use it to find the point that are furtherest away from the base edge.

<<utility functions>>=
function getDistant(cpt, bl) {
    var Vy = bl[1][0] - bl[0][0];
    var Vx = bl[0][1] - bl[1][1];
    return (Vx * (cpt[0] - bl[0][0]) + Vy * (cpt[1] -bl[0][1]))
}
function findMostDistantPointFromBaseLine(baseLine, points) {
    var maxD = 0;
    var maxPt = new Array();
    var newPoints = new Array();
    for (var idx in points) {
        var pt = points[idx];
        var d = getDistant(pt, baseLine);
        if ( d > 0) {
            newPoints.push(pt);
        } else {
            continue;
        }
        if ( d > maxD ) {
            maxD = d;
            maxPt = pt;
        }
    } 
    return {'maxPoint':maxPt, 'newPoints':newPoints}
}

The recursive quickhull algorithm implementation

This code block recursively builds the base edge and return the convex hull edges. The global variable allBaseLines is only used for replaying the convex hull construction.

<<quickhull>>=
var allBaseLines = new Array();
function buildConvexHull(baseLine, points) {
    allBaseLines.push(baseLine)
    var convexHullBaseLines = new Array();
    var t = findMostDistantPointFromBaseLine(baseLine, points);
    if (t.maxPoint.length) { // if there is still a point "outside" the base line
        convexHullBaseLines = 
            convexHullBaseLines.concat( 
                buildConvexHull( [baseLine[0],t.maxPoint], t.newPoints) 
            );
        convexHullBaseLines = 
            convexHullBaseLines.concat( 
                buildConvexHull( [t.maxPoint,baseLine[1]], t.newPoints) 
            );
        return convexHullBaseLines;
    } else {  // if there is no more point "outside" the base line, the current base line is part of the convex hull
        return [baseLine];
    }    
}

Get it started

Find the extremes, and use them to construct the initial base edge and the conver hull. The buildConvexHull are called twice to build upper half and lower half convex hull.

<<start quickhull>>=
function getConvexHull(points) {
    //find first baseline
    var maxX, minX;
    var maxPt, minPt;
    for (var idx in points) {
        var pt = points[idx];
        if (pt[0] > maxX || !maxX) {
            maxPt = pt;
            maxX = pt[0];
        }
        if (pt[0] < minX || !minX) {
            minPt = pt;
            minX = pt[0];
        }
    }
    var ch = [].concat(buildConvexHull([minPt, maxPt], points),
                       buildConvexHull([maxPt, minPt], points))
    return ch;
}

Utilities for showing animation in a HTML canvas tag

This block contains some simple functions for constructing the animation.

<<utility functions for animation>>=
function getRandomPoints(numPoint, xMax, yMax) {
    var points = new Array();
    var phase = Math.random() * Math.PI * 2;
    for (var i = 0; i < numPoint/2; i++) {
        var r =  Math.random()*xMax/4;
        var theta = Math.random() * 1.5 * Math.PI + phase;
        points.push( [ xMax /4 + r * Math.cos(theta), yMax/2 + 2 * r * Math.sin(theta) ] )
    }
    var phase = Math.random() * Math.PI * 2;
    for (var i = 0; i < numPoint/2; i++) {
        var r =  Math.random()*xMax/4;
        var theta = Math.random() * 1.5 * Math.PI + phase;
        points.push( [ xMax /4 * 3 +  r * Math.cos(theta), yMax/2 +  r * Math.sin(theta) ] )
    }
    return points
}
function plotBaseLine(baseLine,color) {
    var ctx = document.getElementById('qh_demo').getContext('2d');
    var pt1 = baseLine[0]
    var pt2 = baseLine[1];
    ctx.save()
    ctx.strokeStyle = color;
    ctx.beginPath();
    ctx.moveTo(pt1[0],pt1[1]);
    ctx.lineTo(pt2[0],pt2[1]);
    ctx.stroke();
    ctx.restore();
}   
var pts;
function qhPlotPoints() {
    ctx = document.getElementById('qh_demo').getContext('2d');
    ctx.clearRect(0,0,200,200);
    ctx.fillStyle = 'rgb(0,0,0)';
    pts = getRandomPoints(250,200,200);
    for (var idx in pts) {
        var pt = pts[idx];
        ctx.fillRect(pt[0],pt[1],2,2);
    }
}
function qhPlotConvexHull() {
    var ch = getConvexHull(pts);
    var eBL = allBaseLines[0];
    function plotIntermediateBL() {
        var l = allBaseLines.shift();
        if (l) {
            plotBaseLine(l, 'rgb(180,180,180)');
            setTimeout(plotIntermediateBL, 250);
        } else {
            for (var idx in ch) {    
                var baseLine = ch[idx];
                plotBaseLine(baseLine, 'rgb(255,0,0)');
            }
            plotBaseLine(eBL,'rgb(0,255,0)');
        }
    }
    plotIntermediateBL();
}

<<qh.js>>=
utility functions
quickhull
start quickhull
utility functions for animation

The minimum HTML to run the code

To run the javascript code, we need this HTML file. It should work at least in Firefox 2.0 and Safari 2.0.

<<qh.html>>=
<html>
<head>
<script language="javascript" src="./qh.js"></script>
</head>
<body>
<button onclick='qhPlotPoints()'>Get Random Points</button> 
<button onclick='qhPlotConvexHull()'>Get convex hull</button><br>
<canvas id="qh_demo" width=200 height=200 style='margin:20pt;border:solid 1px #888;'></canvas>
</body>
</html>

Example

Online example

Download code