Convex Hull with Dot Product Gift Wrap

This JavaScript program demonstrates how to generate a convext hull of a set of points using a gift wrapping algorithm with a dot product on a canvas element. The time complexity is O(mn), where n is the number points and m is the number of points in the hull.

ConvexHullDotProductGiftWrap.html

<!DOCTYPE html>
<html>
  <head>
    <title>XoaX.net's Javascript</title>
    <script type="text/javascript" src="ConvexHullDotProductGiftWrap.js"></script>
  </head>
  <body onload="Draw()">
     <canvas id="idCanvas" width="640" height ="480" style="background-color: #F0F0F0;"></canvas>
  </body>
</html>

ConvexHullDotProductGiftWrap.js

var gqCanvas = null;
var gqContext = null;
var gqPoints = null;

class CPoint2D {
	constructor(dX, dY) {
		this.mdX = dX;
		this.mdY = dY;
	}
	
	DrawPoint(qContext2D) {
		qContext2D.fillStyle = "gray";
		qContext2D.beginPath();
		qContext2D.arc(this.mdX, this.mdY, 3, 0, 2.0*Math.PI, true);
		qContext2D.fill();
	}
	
	static Swap(qP1, qP2) {
		var dSwap = qP1.mdX;
		qP1.mdX = qP2.mdX;
		qP2.mdX = dSwap;
		dSwap = qP1.mdY;
		qP1.mdY = qP2.mdY;
		qP2.mdY = dSwap;
	}
}

class CUnitVector {
	constructor(qP1, qP2) {
		this.mdX = qP2.mdX - qP1.mdX;
		this.mdY = qP2.mdY - qP1.mdY;
		var dMag = Math.sqrt(this.mdX*this.mdX + this.mdY*this.mdY);
		this.mdX /= dMag;
		this.mdY /= dMag;
	}
	
	Dot(qV) {
		return (this.mdX*qV.mdX + this.mdY*qV.mdY);
	}
}

function ConvexHull(qaPoints) {
	// Find a point on the hull. Find the index of the lowest left most point.
	var iLL = 0;
	for (var i = 1; i < qaPoints.length; ++i) {
		// If the comparison point is lower or as low and to the left
		if ((qaPoints[i].mdY > qaPoints[iLL].mdY) || 
			  ((qaPoints[i].mdY == qaPoints[iLL].mdY) && (qaPoints[i].mdX < qaPoints[iLL].mdX))) {
			iLL = i;
		}
	}
	// Put the first hull point in the last place
	CPoint2D.Swap(qaPoints[qaPoints.length-1], qaPoints[iLL]);
	var qInitDir = new CUnitVector(new CPoint2D(0.0, 0.0), new CPoint2D(1.0, 0.0));
	// Get a second point using the dot product to get the nearest point
	var qDir = new CUnitVector(qaPoints[qaPoints.length-1], qaPoints[0]);
	var dMaxDot = qInitDir.Dot(qDir);
	var iMaxIndex = 0;
	for (var i = 1; i < qaPoints.length; ++i) {
		// Make unit direction vector
		qDir = new CUnitVector(qaPoints[qaPoints.length-1], qaPoints[i]);
		var dCurrDot = qInitDir.Dot(qDir);
		if (dMaxDot < dCurrDot) {
			dMaxDot = dCurrDot;
			iMaxIndex = i;
		}
	}
	// Put the second point at the zero index
	CPoint2D.Swap(qaPoints[0], qaPoints[iMaxIndex]);
	var bDone = false;
	var iNextHullIndex = 1;
	qInitDir = new CUnitVector(qaPoints[qaPoints.length-1], qaPoints[0]);
	qDir = new CUnitVector(qaPoints[qaPoints.length-1], qaPoints[0]);
	while (!bDone) {
		iMaxIndex = -1;
		dMaxDot = -2;
		// Find the next point in the hull
		for (var i = iNextHullIndex; i < qaPoints.length; ++i) {
			qDir = new CUnitVector(qaPoints[iNextHullIndex-1], qaPoints[i]);
			var dCurrDot = qInitDir.Dot(qDir);
			if (dCurrDot > dMaxDot) {
				dMaxDot = dCurrDot;
				iMaxIndex = i;
			}
		}
		// Swap the point into the next index
		CPoint2D.Swap(qaPoints[iNextHullIndex], qaPoints[iMaxIndex]);
		if (iMaxIndex == qaPoints.length-1) {
			bDone = true;
		} else {
			// Reset the initial direction
			qInitDir = new CUnitVector(qaPoints[iNextHullIndex-1], qaPoints[iNextHullIndex]);
			++iNextHullIndex;
		}
	}
	// Return the hull size
	return iNextHullIndex + 1;
}


function Initialize() {
	gqCanvas = document.getElementById("idCanvas");
	gqContext = gqCanvas.getContext("2d");
	gqPoints = [];
	// Get the size of the canvas
	const kiWidth = gqCanvas.width;
	const kiHeight = gqCanvas.height;
	// Generate the set of points
	for (var i = 0; i < 100; ++i) {
		gqPoints.push(new CPoint2D(20 + (kiWidth - 40)*Math.random(),20 + (kiHeight - 40)*Math.random()));
	}
}

function Draw() {
	Initialize();
	
	// Draw the full set of points in gray
	for(var qPoint of gqPoints) {
		qPoint.DrawPoint(gqContext);
	}
	
	const kiHullSize = ConvexHull(gqPoints);
	// Draw the hull polygon path
	gqContext.beginPath();
	gqContext.moveTo(gqPoints[0].mdX, gqPoints[0].mdY);
	for (var i = 1; i < kiHullSize; ++i) {
		gqContext.lineTo(gqPoints[i].mdX, gqPoints[i].mdY);
	}
	gqContext.closePath();
	gqContext.strokeStyle = "red";
	gqContext.lineWidth = 1;
	gqContext.stroke();
	// Draw the vertices of the hull in red
	for (var i = 0; i < kiHullSize; ++i) {
		gqContext.fillStyle = "red";
		gqContext.beginPath();
		gqContext.arc(gqPoints[i].mdX, gqPoints[i].mdY, 3, 0, 2.0*Math.PI, true);
		gqContext.fill();
	}
}

Canvas JavaScript

Convex Hull with Dot Product Gift Wrap

ConvexHullDotProductGiftWrap.html

ConvexHullDotProductGiftWrap.js

Output