2f:T5c4,function orientationTest(tail, head){ // TODO: remove duplicates. if (tail[0][0] == tail[1][0]){ if (tail[1][1] > tail[0][1]){ if (head[1][0] < head[0][0]){ return -1; } else{ return 1; } }else if (tail[1][1] < tail[0][1]){ if (head[1][0] < head[0][0]){ return 1; } else{ return -1; } }else{ throw new Error('Duplicate points detected'); } } if (head[0][0] == head[1][0]){ if (tail[0][0] == tail[1][0]){ return 0; }else{ if (head[1][1] > head[0][1]){ if (tail[1][0] > tail[0][0]){ return -1; } else { return 1; } }else{ if (tail[1][0] > tail[0][0]){ return 1; } else { return -1; } } } } let slopeTail = (tail[0][1]-tail[1][1])/(tail[0][0]-tail[1][0]) let slopeHead = (head[0][1]-head[1][1])/(head[0][0]-head[1][0]) let flipped = 1; // direction reversed // left->right if ((tail[0][0] > tail[1][0]) && (head[0][0] < head[1][0])){ flipped = -1 } // right->left if ((tail[0][0] < tail[1][0]) && (head[0][0] > head[1][0])){ flipped = -1 } if (slopeHead > slopeTail){ // Left Turn return -1 * flipped }else if (slopeHead < slopeTail){ // Right Turn return 1 * flipped }else{ // Straight line return 0 } }30:Tfa0,function convexHull(P, log){ let n = P.length if(n <= 2){ let updatePointsSeen; if ((typeof log["pointsSeen"].at(-1) === "undefined") || (log["pointsSeen"].at(-1).length === 0)){ updatePointsSeen = P; }else{ updatePointsSeen = log["pointsSeen"].at(-1).concat(P); } log = updateLog(log ,[], log["mid"].at(-1), [], [], P, updatePointsSeen); return [P, log]; }else if(n === 3){ let updatePointsSeen; if ((typeof log["pointsSeen"].at(-1) === "undefined") || (log["pointsSeen"].at(-1).length === 0)){ updatePointsSeen = P; }else{ updatePointsSeen = log["pointsSeen"].at(-1).concat(P); } log = updateLog(log ,[], log["mid"].at(-1), [], [], P, updatePointsSeen); if(P[1][0]-P[0][0] === 0){ if (P[0][1]>P[1][1]){ return [[P[0],P[2],P[1]], log]; }else{ return [P, log]; } } let slope1 = (P[1][1]-P[0][1])/(P[1][0]-P[0][0]); let slope2 = (P[2][1]-P[0][1])/(P[2][0]-P[0][0]); if(slope1>=slope2){ return [P, log]; }else{ return [[P[0],P[2],P[1]], log] } } let mid = Math.floor(n/2); let updateMid; if ((typeof log["mid"].at(-1) === "undefined") || (log["mid"].at(-1).length === 0)){ updateMid = [P[mid]]; }else{ updateMid = log['mid'].at(-1).concat([P[mid]]); } log = updateLog(log, [], updateMid, [], [],[], log["pointsSeen"].at(-1)) let CHl, CHr; [CHl,log] = convexHull(P.slice(0, mid), log); [CHr,log] = convexHull(P.slice(mid), log); log = updateLog(log, CHl, log["mid"].at(-1), CHr,[],[],log["pointsSeen"].at(-1)) let nl= CHl.length, nr=CHr.length; let lmax=-1,imax = -1; for (let i =0;i lmax){ lmax = CHl[i][0]; imax = i; } } let rmin = 101, imin = 101; for (let i =0;i mutable step = (step-1+ret[1][\"mid\"].length )%ret[1][\"mid\"].length }>prev\n","pinned":false,"hidden":false,"mode":"html"},{"id":129,"value":"mutable step = 0","pinned":false,"hidden":false,"mode":"ojs"},{"id":17,"value":"Plot.plot({\n x:{domain:[0,100],label:\"x\"},\n y:{domain:[0,100],label:\"y\"},\n marks:[\n Plot.ruleX([0]),\n Plot.ruleY([0]),\n Plot.dot(dots),\n Plot.dot(ret[1][\"left\"].at(step), {fill:\"red\"}),\n Plot.line(ret[1][\"left\"].at(step), {stroke:\"red\"}),\n Plot.line([ret[1][\"left\"].at(step)[0],ret[1][\"left\"].at(step).at(-1)], {stroke:\"red\"}),\n Plot.dot(ret[1][\"right\"].at(step), {fill:\"blue\"}),\n Plot.line(ret[1][\"right\"].at(step), {stroke:\"blue\"}),\n Plot.line([ret[1][\"right\"].at(step)[0],ret[1][\"right\"].at(step).at(-1)], {stroke:\"blue\"}),\n Plot.dot(ret[1][\"merge\"].at(step), {fill:\"orange\"}),\n Plot.line(ret[1][\"merge\"].at(step), {stroke:\"orange\"}),\n \n \n Plot.dot(ret[1][\"convexHull\"].at(step), {fill:\"purple\"}),\n Plot.line(ret[1][\"convexHull\"].at(step), {stroke:\"purple\"}),\n Plot.line([ret[1][\"convexHull\"].at(step)[0],ret[1][\"convexHull\"].at(step).at(-1)], {stroke:\"purple\"}),\n Plot.ruleX(ret[1][\"mid\"].at(step).map(function(x) {return x[0];}), {strokeDasharray: 3})\n ]\n})\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":9,"value":"dots = {\n let seen = new Set();\n let points = new Array();\n let x, y;\n for (let i=0;ia[0]-b[0]);\n return points;\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"function getRandomInt(max=1,min=0){\n var x = Math.random()\n return Math.floor(max * x + min * (1-x))\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"function getRandomCoord(max=1,min=0){\n var x = Math.random()\n return max * x + min * (1-x)\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":24,"value":"$2f","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"function updateLog(log, left, mid, right, merge, convexHull, pointsSeen){\n log[\"left\"].push(left);\n log[\"mid\"].push(mid);\n log[\"right\"].push(right);\n log[\"merge\"].push(merge);\n log[\"convexHull\"].push(convexHull);\n log[\"pointsSeen\"].push(pointsSeen);\n return log;\n}","pinned":true,"hidden":false,"mode":"ojs"},{"id":30,"value":"$30","pinned":false,"hidden":false,"mode":"ojs"},{"id":40,"value":"ret = convexHull(dots, {\"left\":[[]], \"mid\":[[]], \"right\":[[]], \"merge\":[[]], \"convexHull\":[[]], \"pointsSeen\":[[]]})","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W31","stdlib":"1","titling":"auto"}