70 lines
1.5 KiB
JavaScript
70 lines
1.5 KiB
JavaScript
var points = [];
|
|
var hull = [];
|
|
|
|
function setup() {
|
|
createCanvas(1132, 700);
|
|
frameRate(10);
|
|
|
|
strokeWeight(4);
|
|
stroke(220);
|
|
}
|
|
|
|
function draw() {
|
|
background(40);
|
|
// draw points
|
|
for (i = 0; i < points.length; i++) {
|
|
point(points[i].x, points[i].y);
|
|
};
|
|
console.log(hull);
|
|
// draw hull
|
|
noFill();
|
|
beginShape();
|
|
for (i = 0; i < hull.length; i++) {
|
|
vertex(hull[i].x, hull[i].y);
|
|
};
|
|
endShape(CLOSE);
|
|
}
|
|
|
|
function mouseClicked() {
|
|
points.push(createVector(mouseX, mouseY));
|
|
hull = convexHull(points);
|
|
noFill();
|
|
//console.log(hull);
|
|
beginShape();
|
|
for (var i = 0; i < hull.length; i++) {
|
|
vertex(hull[i].x, hull[i].y);
|
|
}
|
|
endShape(CLOSE);
|
|
return false;
|
|
}
|
|
|
|
// https://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
|
|
function convexHull(points) {
|
|
points.sort(comparison);
|
|
var L = [];
|
|
for (var i = 0; i < points.length; i++) {
|
|
while (L.length >= 2 && cross(L[L.length - 2], L[L.length - 1], points[i]) <= 0) {
|
|
L.pop();
|
|
}
|
|
L.push(points[i]);
|
|
}
|
|
var U = [];
|
|
for (var i = points.length - 1; i >= 0; i--) {
|
|
while (U.length >= 2 && cross(U[U.length - 2], U[U.length - 1], points[i]) <= 0) {
|
|
U.pop();
|
|
}
|
|
U.push(points[i]);
|
|
}
|
|
L.pop();
|
|
U.pop();
|
|
return L.concat(U);
|
|
}
|
|
|
|
function comparison(a, b) {
|
|
return a.x == b.x ? a.y - b.y : a.x - b.x;
|
|
}
|
|
|
|
function cross(a, b, o) {
|
|
return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x);
|
|
}
|