Published
Edited
Jul 6, 2020
3 stars
md `# Viewing the Graham algorithm for convex hull in O(n*log(n)) with P5Js`
md `## Explanation of the algorithm
Given n random points in the canvas, we want to generate the convex hull. The convex hull is a hull with points that all the other points is a convex combination of these points. To obtain these set of points in the hull, we need to follow the Graham algorithm, that achieves complexity of O(n*lg(n)).`
md `## Generate new random points
Run the cell bellow to generate new random points.`
dots = [];
p5(sketch => {
var stack = [];
var edges = [];
var ini_dot = -1;
let max_y = 0;
let radius = 7;
let number_of_dots = 50;
let count = 3;
let stop = false;
sketch.setup = function() {
sketch.frameRate(5);
sketch.createCanvas(800, 600);
sketch.background(255,255,255);
sketch.rectMode(sketch.CENTER);
for(let i = 0;i < number_of_dots; i++){
var dot = new Dot(sketch);
if(dot.y > max_y){
max_y = dot.y;
ini_dot = i;
}
dots.push(dot);
}
//
var dot_aux = new Dot(sketch);
dot_aux = dots[ini_dot];
dots[ini_dot] = dots[0];
dots[0] = dot_aux;
dots[0].color = sketch.color(255,0,0);
dots.sort(compare);
stack.push(0);
stack.push(1);
stack.push(2);
edges.push([0,1]);
};
sketch.draw = function() {
sketch.background(210,210,210);
for(let i = 0;i < dots.length; i++){
sketch.fill(dots[i].color);
if(!stop){
if(i == count){
sketch.fill(sketch.color(0,255,0));
}else if(i == stack[stack.length-2]){
sketch.fill(sketch.color(0,0,255));
}
}
sketch.circle(dots[i].x,dots[i].y,dots[i].diameter);
}
if(!stop){
while(dots[stack[stack.length-2]].triangle_orientation(dots[stack[stack.length-1]],dots[count])!=2){
stack.pop();
}
stack.push(count);
for(let i = 1; i < stack.length; i++){
sketch.line(dots[stack[i-1]].x,dots[stack[i-1]].y,dots[stack[i]].x,dots[stack[i]].y);
}
count = (count+1)%number_of_dots;
if(count == 1){
stop = true;
}
}
for(let i = 1; i < stack.length; i++){
sketch.line(dots[stack[i-1]].x,dots[stack[i-1]].y,dots[stack[i]].x,dots[stack[i]].y);
}
};
})
class Dot{
constructor(sketch){
this.x = sketch.random(150,650);
this.y = sketch.random(150,450);
this.diameter = 7;
this.color = sketch.color(0,0,0);
}
triangle_orientation(b,c){
let cross_product = (b.y-this.y)*(c.x-b.x)-(b.x-this.x)*(c.y-b.y);
if(cross_product == 0){
return 0;
}
return (cross_product>0)?1:2;
}
}
function compare(d1,d2){
// function to use in sort comparing the angle
var o = dots[0].triangle_orientation(d1,d2)
if (o == 0){
return (distSquare(dots[0], d2) >= distSquare(dots[0], d1))? -1 : 1;
}
return (o == 2)? -1: 1;
}
function distSquare(d1,d2){
// get the distance square
return (d1.x - d2.x)*(d1.x - d2.x) + (d1.y - d2.y)*(d1.y - d2.y);
}
function addEdge(sketch,a,b){
print(sketch.edges);
}
P5 = require('https://github.com/processing/p5.js/releases/download/1.0.0/p5.js')
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
