# Quickhull experiment in html5 - part1

Implementing the Quickhull algorithm. This will find out a fast optimal bounding volume encapsulating all the points.

Steps:

- Find the bounding box
- Find the points lying on the box, they form a quad..
- Eliminate the points lying inside the formed boundary
- Find the farthest point away from each edges and form a triangle of that edge with the point.
- Eliminate the points lying inside the triangle and add the two new edges to the hull
- Repeat the steps 3-5 till no points are found outside the hull.

The interactive canvas below (requires google chrome):

/* This program demonstrates the working of Bezier curve and shows * the working of blending functions * Copyright (C) 2011 Rishikesh Parkhe * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see . */

var ctx;
var degree = 0;
var pts_x = new Array();
/*pts_x[0] = 10;
pts_x[1] = 50;
pts_x[2] = 90;
pts_x[3] = 180;
pts_x[4] = 280;
pts_x[4] = 350;*/

var pts_y = new Array();
/*pts_y[0] = 50;
pts_y[1] = 130;
pts_y[2] = 220;
pts_y[3] = 40;
pts_y[4] = 340;
pts_y[4] = 40;*/
var mouse_x=0;
var mouse_y=0;

var render_x = new Array(); var render_y = new Array();

var bound_x = new Array(); var bound_y = new Array();

var bernstein_coeffs = new Array();

var min_x; var max_x; var min_y; var max_y;

var indices = new Array();

function point_inside_tri() {

}

function get_render_lines() { indices = new Array(); indices[0] = 0; indices[1] = 0; indices[2] = 0; indices[3] = 0;

min_x = pts_x[0]; max_x = pts_x[0]; min_y = pts_y[0]; max_y = pts_y[0];

for(var i=0;i max_x) { indices[2] = i; max_x = pts_x[i]; }

if(pts_y[i] < min_y) { indices[1] = i; min_y = pts_y[i]; }

if(pts_y[i] > max_y) { indices[3] = i; max_y = pts_y[i]; } }

/*var num = 100; var du = 1.0 / (num-1); var u = 0.0; for(var i=0; i1.0) u = 1.0;

var pt = evaluate(u, i);

render_x[i] = pt[0]; render_y[i] = pt[1]; }*/ }

function init() { var canvas = document.getElementById(“canvas”); ctx = canvas.getContext(“2d”); get_render_lines(); canvas.addEventListener(‘mousemove’, mouseMove, false); canvas.addEventListener(‘mouseup’, mouseUp, false);

draw(); }

function draw() { ctx.fillStyle = “rgba(0, 10, 30, 1)”; ctx.fillRect(0, 0, 400, 400);

ctx.fillStyle = “rgba(200, 100, 10, 0.8)”; ctx.fillRect(mouse_x-10, mouse_y-10, 10, 10);

if(degree > 1) { ctx.moveTo(pts_x[0], pts_y[0]); ctx.fillStyle = ‘#00f’; ctx.strokeStyle = “rgba(230, 220, 250, 0.2)”; ctx.lineWidth = 1; ctx.beginPath(); for(var i=0; i