juanplopes/convexhull01.html

## convexhull01.html
<!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>
	<!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>