Anonymous user
Convex hull: Difference between revisions
Javascript implementation added
(Javascript implementation added) |
|||
Line 681:
{{out}}
<pre>Convex Hull: [(-9, -3), (-3, -9), (19, -8), (17, 5), (12, 17), (5, 19), (-3, 15)]</pre>
=={{header|Javascript}}==
<lang Javascript>
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);
}
</lang>
'''For usage''':
<nowiki>convexhull.js</nowiki>
<lang 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);
}
</lang>
<nowiki>convexhull.html</nowiki>
<lang html>
<html>
<head>
<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/0.7.2/p5.js"></script>
<script src="convexhull.js"></script>
</head>
<body>
<table>
<tr>
<th><h1>Convex Hull</h4></th>
<th><h4>Left mouse: Add points</h6></th>
</tr>
</table>
</body>
</html>
</lang>
=={{header|Julia}}==
| |||