Published
Edited
Nov 20, 2021
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
points = {
var positions = [];
for(var i = 0; i < num_points; i++){
var x_pos = Math.random() * (width-20) + 10;
var y_pos = Math.random() * (height-20) + 10;
positions.push([x_pos, y_pos]);
}
return positions;
}
Insert cell
Insert cell
Insert cell
lowest_idx = {
var y_vals = points.map(function(v) {return v[1];});
return y_vals.indexOf(Math.max.apply(null, y_vals));
}
Insert cell
Insert cell
Insert cell
![aa.drawio.png](${await FileAttachment("aa.drawio.png").url()})
Insert cell
Insert cell
function clockwiseness(p0, p1, p2){
// returns 1 if clockwise, 0 if colinear, -1 if counterclockwise
var signed_area = (p1[0] - p0[0])*(p2[1]-p0[1]) - (p2[0] - p0[0])*(p1[1]-p0[1])
if(signed_area == 0) return 0;
return (signed_area) > 0? 1 : -1
}
Insert cell
Insert cell
Insert cell
Insert cell
{
restart_gift;
var hull = [];
var current_idx = lowest_idx
draw_gift(current_idx, -1, -1, hull);
do {
hull.push(points[current_idx]);
// Melhor candidato é inicializado com um ponto qualquer (o de índice seguinte)
var candidate_idx = (current_idx + 1) % num_points;

// Percorre todos os pontos a procura de algum mais anti-horário que o melhor candidato
for (let i = 0; i < num_points; i++) {
if (i == candidate_idx || i == current_idx) continue;
yield Promises.delay(delay_gift, draw_gift(current_idx, candidate_idx, i, hull));
// Se o ponto testado for mais anti-horário que o atual candidato, substitui
if (clockwiseness(points[current_idx], points[i], points[candidate_idx]) == -1){
candidate_idx = i;
}
}
current_idx = candidate_idx;
if(current_idx == lowest_idx) hull.push(points[current_idx]);
} while (current_idx !== lowest_idx);
yield draw_gift(-1, -1, -1, hull);
}
Insert cell
function draw_gift(current_idx, candidate_idx, test_idx, hull){
var ctx = DOM.context2d(width, height);
for(var i = 0; i < num_points; i++){
var color = 'Black'

// Último ponto confirmado do fecho em vermelho
if(i == current_idx) color = 'Red';

// Melhor candidato para continuar o fecho em verde
if(i == candidate_idx){
color = 'Green'
draw_segment(ctx, points[current_idx][0], points[current_idx][1],
points[i][0], points[i][1], color);
}
// Ponto atualmente testado em azul
if(i == test_idx){
color = 'Blue'
draw_segment(ctx, points[current_idx][0], points[current_idx][1],
points[i][0], points[i][1], color);
}

draw_point(ctx, points[i][0], points[i][1], 5, color);
}
// Desenha o envoltório
if(hull.length > 0) draw_hull(ctx, hull, 'Red');
return ctx.canvas;
}
Insert cell
Insert cell
Insert cell
Insert cell
{
restart_graham;
let hull = [sorted_points[0], sorted_points[1], sorted_points[2]];
for(var i=3; i<=num_points; i++){
while(clockwiseness(hull[hull.length-2], hull[hull.length-1], sorted_points[i%num_points]) == 1){
hull.pop();
yield Promises.delay(delay_graham, draw_graham(hull, i+1));
}
hull.push(sorted_points[i%num_points]);
yield Promises.delay(delay_graham, draw_graham(hull, i+1));
}
return hull;
}
Insert cell
Insert cell
Insert cell
Insert cell
## Utilitários
Insert cell
sorted_points = [...points].sort((a, b) => get_slope(a, lowest_point) - get_slope(b, lowest_point))
Insert cell
lowest_point = points[lowest_idx]
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell
Insert cell

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.
Learn more