Convex hull: Difference between revisions

Content added Content deleted

Inline

@@ Line 681: / 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}}==