Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Revised @ElemarJR's Convex Hull (using Monotone Chain)
<!doctype html>
<html>
<head>
<title>ConvexHull 01</title>
<style type="text/css">
* {
margin: 0;
padding: 0;
}
html, body {
height: 100%;
width: 100%;
}
canvas { display: block;}
</style>
</head>
<body>
<canvas id="target"></canvas>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/1.6.4/jquery.min.js" type="text/javascript"></script>
<script>
var canvas = $('#target');
var context = canvas.get(0).getContext("2d");
var width = 0;
var height = 0;
function resize()
{
canvas.attr('width', $(window).get(0).innerWidth);
canvas.attr('height', $(window).get(0).innerHeight);
width = canvas.width();
height = canvas.height();
}
resize();
var edges = new Array();
function findConvexHull()
{
edges.splice(0, edges.length);
if (points.length == 0) return;
var isLeft = function(a, b, c) {
return ((b.x - a.x)*(c.y - a.y) - (b.y - a.y)*(c.x - a.x)) >= 0;
}
points.sort(function(a, b) { return a.x!=b.x ? a.x-b.x : a.y-b.y; });
var hull = [];
var m = function(i) { return hull[hull.length-i]; }
for(var i=0; i<points.length; i++) {
while(hull.length >= 2 && isLeft(m(1), m(2), points[i])) hull.pop()
hull.push(points[i]);
}
hull.pop();
for(var i=points.length-1, k=hull.length; i>=0; i--) {
while(hull.length >= k+2 && isLeft(m(1), m(2), points[i])) hull.pop()
hull.push(points[i]);
}
for(var i=0; i<hull.length; i++)
edges.push({a:hull[i], b:hull[(i+1)%hull.length]});
}
var points = new Array();
canvas.click(function(e) {
points.push({x: e.clientX, y: e.clientY});
findConvexHull();
draw();
});
function draw()
{
context.clearRect(0, 0, width, height);
for (var i = 0; i < points.length; i++ )
{
context.beginPath();
context.moveTo(points[i].x - 3, points[i].y);
context.lineTo(points[i].x + 3, points[i].y);
context.moveTo(points[i].x, points[i].y - 3);
context.lineTo(points[i].x, points[i].y + 3);
context.stroke();
}
for (i = 0; i < edges.length; i++)
{
context.beginPath();
context.moveTo(edges[i].a.x, edges[i].a.y);
context.lineTo(edges[i].b.x, edges[i].b.y);
context.stroke();
}
}
</script>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment