2d:null 2e:["$","title",null,{"children":"Check if polygon is x-monotone | Racquel Fygenson | Observable"}] 33:T7a0,function polygon_cleaned(poli){ var x="abcdefghijklmnopqrstuvwxyz" var retval = {} var shift = 0 for(var i = 0; i < poli.length; i++){ retval[x[i]] = [{"x": poli[i][0], "y": 120-Math.round(poli[i][1])}][0] } if(retval[x[0]].y <= retval[x[poli.length-1]].y + 2 && retval[x[0]].y > retval[x[poli.length-1]].y - 2){ retval[x[0]] = {"x": retval[x[0]].x, "y": retval[x[0]].y, "h_edge": x[poli.length-1], "v_edge": x[1]} retval[x[poli.length-1]] = {"x": (retval[x[poli.length-1]].x)+1, "y": retval[x[0]].y, "h_edge": x[0], "v_edge": x[poli.length-2]} for(var k = 1; k < poli.length-2; k=k+2){ retval[x[k]] = {"x": retval[x[k]].x, "y": retval[x[k]].y, "h_edge": x[k+1], "v_edge": x[k-1]} retval[x[k+1]] = {"x": retval[x[k+1]].x, "y": retval[x[k]].y, "h_edge": x[k], "v_edge": x[k+2]} } } else{ retval[x[0]] = {"x": retval[x[0]].x, "y": retval[x[0]].y, "h_edge": x[1], "v_edge": x[poli.length-1]} retval[x[1]] = {"x": retval[x[1]].x, "y": retval[x[0]].y, "h_edge": x[0], "v_edge": x[2]} for(var k = 2; k < poli.length-1; k=k+2){ retval[x[k]] = {"x": retval[x[k]].x, "y": retval[x[k]].y, "h_edge": x[k+1], "v_edge": x[k-1]} retval[x[k+1]] = {"x": retval[x[k+1]].x, "y": retval[x[k]].y, "h_edge": x[k], "v_edge": x[k+2]} } retval[x[poli.length-1]] = {"x": retval[x[poli.length-1]].x, "y": retval[x[poli.length-1]].y, "h_edge":x[poli.length-2], "v_edge": x[0]} } // retval[x[0]] = {"x": (retval[x[poli.length-1]].x), "y": retval[x[0]].y, "h_edge": x[1], "v_edge": x[poli.length-1]} // for(var j = 1; j < poli.length-1; j = j+2){ // if(retval[x[j]].y < retval[x[j+1]].y){ // retval[x[j]] = {"x": (retval[x[j]].x) +shift, "y": retval[x[j]].y, "h_edge": x[j-1], "v_edge": x[j+1]} // } // else{ // retval[x[j]] = {"x": (retval[x[j]].x) -shift, "y": retval[x[j]].y, "h_edge": x[j-1], "v_edge": x[j+1]} // } // } return retval }34:T553,// p1_list = [{name: "a", x: 49, y: 44, h_edge: "b", v_edge: "t"}, // {name: "b", x: 114, y: 44, h_edge: "a", v_edge: "c"}, // {name: "c", x: 110, y: 81, h_edge: "d", v_edge: "b"}, // {name: "d", x: 169, y: 81, h_edge: "c", v_edge: "e"}, // {name: "e", x: 169, y: 37, h_edge: "f", v_edge: "d"}, // {name: "f", x: 250, y: 37, h_edge: "e", v_edge: "g"}, // {name: "g", x: 250, y: 87, h_edge: "h", v_edge: "f"}, // {name: "h", x: 290, y: 87, h_edge: "g", v_edge: "i"}, // {name: "i", x: 295, y: 131, h_edge: "j", v_edge: "h"}, // {name: "j", x: 247, y: 131, h_edge: "i", v_edge: "k"}, // {name: "k", x: 247, y: 187, h_edge: "l", v_edge: "j"}, // {name: "l", x: 187, y: 187, h_edge: "k", v_edge: "m"}, // {name: "m", x: 187, y: 133, h_edge: "n", v_edge: "l"}, // {name: "n", x: 129, y: 133, h_edge: "m", v_edge: "o"}, // {name: "o", x: 129, y: 196, h_edge: "p", v_edge: "n"}, // {name: "p", x: 70, y: 196, h_edge: "o", v_edge: "q"}, // {name: "q", x: 66, y: 120, h_edge: "r", v_edge: "p"}, // {name: "r", x: 25, y: 120, h_edge: "q", v_edge: "s"}, // {name: "s", x: 25, y: 93, h_edge: "t", v_edge: "r"}, // {name: "t", x: 45, y: 93, h_edge: "s", v_edge: "a"}]35:[] 31:{"id":"25405bdb85ec4cf6","slug":"check-if-a-polygon-is-x-monotone","title":"Check if polygon is x-monotone","thumbnail":"b178de54483bbfa8bb3c9ac97ba94fd19015e0de9a62f0ac788765fecfbb2d17","access_level":"public","create_time":"$D2021-04-28T00:38:10.702Z","update_time":"$D2021-05-10T07:12:25.374Z","view_time":null,"first_public_time":"$D2021-04-28T19:43:11.428Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"d91cf0a4c81da0e7","login":"racquellevia","name":"Racquel Fygenson","avatar_url":"https://avatars-next.observableusercontent.com/65fc88c7b5b3da59b62a2bb3b7f2f817300afb47c5108bf80b5b0d3ec5e0402f","tier":"starter_2024"},"version":356,"publish_version":356,"role":null,"authored":false,"authors":[{"type":"individual","id":"fc026d346efb6aba","login":"racquellevia","name":"Racquel Fygenson","avatar_url":"https://avatars-next.observableusercontent.com/65fc88c7b5b3da59b62a2bb3b7f2f817300afb47c5108bf80b5b0d3ec5e0402f","tier":null}],"members":[{"type":"individual","id":"fc026d346efb6aba","login":"racquellevia","name":"Racquel Fygenson","avatar_url":"https://avatars-next.observableusercontent.com/65fc88c7b5b3da59b62a2bb3b7f2f817300afb47c5108bf80b5b0d3ec5e0402f","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"title":"Check if polygon is x-monotone","cells":[{"id":82,"value":"md`# Check if polygon is x-monotone\n~~~js\nimport {isMontone} from \"@racquellevia/check-if-a-polygon-is-x-monotone\"\n~~~`","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":4,"value":"input_vertices = [[59, 44],\n [114, 44],\n [114, 81],\n [169, 81],\n [169, 37],\n [250, 37],\n [250, 87],\n [280, 87],\n [295, 131],\n [247, 131],\n [247, 187],\n [187, 187],\n [187, 133],\n [129, 100],\n [129, 196],\n [66, 196],\n [66, 120],\n [25, 120],\n [25, 93],\n [54, 93]]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":318,"value":"i_dict = polygon_cleaned(input_vertices)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":325,"value":"i_list = polygon_for_drawing(polygon_cleaned(input_vertices))","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":316,"value":"$33","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":322,"value":"function polygon_for_drawing(poli){\n var keys = Object.keys(poli)\n var retval = []\n for(var i = 0; i < keys.length; i++){\n retval.push({\"name\": keys[i], \"x\": poli[keys[i]].x, \"y\": poli[keys[i]].y, \"h_edge\": poli[keys[i]].h_edge, \"v_edge\": poli[keys[i]].v_edge})\n }\nreturn retval\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":104,"value":" p1 = [{\n a: {x: 49, y: 44, h_edge: \"b\", v_edge: \"t\"},\n b: {x: 114, y: 44, h_edge: \"a\", v_edge: \"c\"},\n c: {x: 110, y: 81, h_edge: \"d\", v_edge: \"b\"},\n d: {x: 169, y: 81, h_edge: \"c\", v_edge: \"e\"},\n e: {x: 169, y: 37, h_edge: \"f\", v_edge: \"d\"},\n f: {x: 250, y: 37, h_edge: \"e\", v_edge: \"g\"},\n g: {x: 250, y: 87, h_edge: \"h\", v_edge: \"f\"},\n h: {x: 290, y: 87, h_edge: \"g\", v_edge: \"i\"},\n i: {x: 295, y: 131, h_edge: \"j\", v_edge: \"h\"},\n j: {x: 247, y: 131, h_edge: \"i\", v_edge: \"k\"},\n k: {x: 247, y: 187, h_edge: \"l\", v_edge: \"j\"},\n l: {x: 187, y: 187, h_edge: \"k\", v_edge: \"m\"},\n m: {x: 187, y: 133, h_edge: \"n\", v_edge: \"l\"},\n n: {x: 129, y: 133, h_edge: \"m\", v_edge: \"o\"},\n o: {x: 129, y: 196, h_edge: \"p\", v_edge: \"n\"},\n p: {x: 70, y: 196, h_edge: \"o\", v_edge: \"q\"},\n q: {x: 66, y: 120, h_edge: \"r\", v_edge: \"p\"},\n r: {x: 25, y: 120, h_edge: \"q\", v_edge: \"s\"},\n s: {x: 25, y: 93, h_edge: \"t\", v_edge: \"r\"},\n t: {x: 45, y: 93, h_edge: \"s\", v_edge: \"a\"}\n}][0]","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":6,"value":"{\n const svg = d3.create('svg')\n .attr('width', 600)\n .attr('height',500);\n\n var poly = i_list\n \n var x = d3.scaleLinear().range([0, 600]);\n\tvar y = d3.scaleLinear().range([500,0]);\n \n x.domain([0, 300]);\n y.domain([-100, 100]);\n \n svg.selectAll(\"polygon\")\n .data([poly])\n .enter().append(\"polygon\")\n .attr(\"fill\", \"none\")\n .attr(\"stroke\", \"black\")\n .attr(\"points\",function(d) { \n return d.map(function(d) {\n return [x(d.x),y(d.y)].join(\",\");\n }).join(\" \");\n });\n\n svg.selectAll('circle')\n .data(poly)\n .join('circle')\n .attr('cy',d => y(d.y)) \n .attr('cx', d => x(d.x)) \n .attr('r', 4)\n .attr('fill', 'darkgrey')\n\n svg.selectAll(\"text\")\n .data(poly)\n .join(\"text\")\n .attr(\"dy\", \"1.2em\")\n .attr(\"dx\", \"0.3em\")\n .attr(\"x\", d => x(d.x))\n .attr(\"y\", d => y(d.y))\n .attr(\"font-size\", \"13\")\n .attr(\"fill\", \"black\")\n .text(d => d.name);\n \n \n return svg.node();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":116,"value":"isMonotone_dict(i_dict)\n","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":207,"value":"function isMonotone_dict(points){\n var keys = Object.keys(points)\n var minx = points[keys[0]]\n var maxx = points[keys[0]]\n\n var vCount = 0\n \n for(var i = 1; i < keys.length; i++){\n if(minx.x > points[keys[i]].x){\n minx = points[keys[i]]\n }\n if(maxx.x < points[keys[i]].x){\n maxx = points[keys[i]]\n }\n }\n \n var currx = minx.x\n var now = (points[minx.v_edge].x != minx.x) ? \"v\" : \"h\"\n var nextx = (now == \"v\") ? points[minx.v_edge] : points[minx.h_edge]\n while(currx != maxx.x){\n if(nextx.x < currx){\n // vCount.push(nextx)\n vCount++\n }\n currx = nextx.x\n now = (now == \"v\") ? \"h\" :\"v\"\n nextx = (now == \"v\") ? points[nextx.v_edge] : points[nextx.h_edge]\n }\n\n while(nextx.x != minx.x){\n if(nextx.x > currx){\n // vCount.push(nextx)\n vCount++\n }\n currx = nextx.x\n now = (now == \"v\") ? \"h\" :\"v\"\n nextx = (now == \"v\") ? points[nextx.v_edge] : points[nextx.h_edge]\n }\n\n return (vCount <= 0)\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":138,"value":"$34","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":15,"value":"d3 = require(\"d3@6\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"