2d:null 2e:["$","title",null,{"children":"Line Clipping | John C | Observable"}] 33:T4b8,With this region code, it is easy to deal with the cases when both endpoints are inside the window and both endpoints are in the same region ```js if (regionCode0 === 0 && regionCode1 ===0){ // entire line inside the window return line; } else if ((regionCode0 & regionCode1) !== 0){ //entire line outside the window return null; } else { // need further testing } ``` Now for the complex cases, we pick one of the endpoint outside the window to test ```js let code = regionCode0 !== 0 ? regionCode0 : regionCode1; ``` we want to calculate a new X and Y coordinate to replace the endpoint, so we can test the endpoint against the four sides of the window ```js if ((code & (1 << 0)) !== 0) { newX = xmin; newY = (y1 - y0) * (xmin - x0) / (x1- x0) + y0; //endpoint on the left region } else if ((code & (1 << 1)) !== 0) { newX = xmax; newY = (y1 - y0) * (xmax - x0) / (x1- x0) + y0; //endpoint on the right region } else if ((code & (1 << 2)) !== 0) { newY = ymin; newX = (x1 - x0) * (ymin - y0) / (y1 - y0) + x0; //endpoint below the window } else if ((code & (1 << 3)) !== 0) { newY = ymax; newX = (x1 - x0) * (ymax - y0) / (y1 - y0) + x0; //endpoint above the window } ```34:T6d8,/** @param {Vector} p0 {x,y} first endpoint of the line @param {Vector} p1 {x,y} second endpoint of the line @param {Vector} p {x,y} upperleft corner of the clip window @param {number} w width of the clip window @param {number} h height of the clip window @returns [p0,p1] the line to draw inside the clip window **/ function clipLine(p0, p1, p, w, h) { let code0, code1; let p0c = {x:p0.x, y:p0.y}; let p1c = {x:p1.x, y:p1.y}; let xmin = p.x, xmax = p.x + w, ymin = p.y, ymax = p.y + h; while (true) { code0 = endpointRegionCode(p0c, p, w, h); code1 = endpointRegionCode(p1c, p, w, h); if (code0 === 0 && code1 ===0){ // entire line inside the window return [p0c, p1c]; } else if ((code0 & code1) !== 0){ //entire line outside the window return null; } else { let code = code0 !== 0 ? code0 : code1; let newX=0, newY=0, x0 = p0c.x, y0 = p0c.y, x1 = p1c.x, y1 = p1c.y; if ((code & (1 << 0)) !== 0) { newX = xmin; newY = (y1 - y0) * (xmin - x0) / (x1- x0) + y0; //endpoint on the left region } else if ((code & (1 << 1)) !== 0) { newX = xmax; newY = (y1 - y0) * (xmax - x0) / (x1- x0) + y0; //endpoint on the right region } else if ((code & (1 << 2)) !== 0) { newY = ymin; newX = (x1 - x0) * (ymin - y0) / (y1 - y0) + x0; //endpoint below the window } else if ((code & (1 << 3)) !== 0) { newY = ymax; newX = (x1 - x0) * (ymax - y0) / (y1 - y0) + x0; //endpoint above the window } // update new endpoint if (code === code0) { p0c.x = newX; p0c.y = newY; } else { p1c.x = newX; p1c.y = newY; } } } }35:T484,p5(s => { let gridSize = 100; s.setup = function () { s.createCanvas(400,400); s.background(255); s.stroke(0); s.strokeWeight(2); for (let x = 0; x < s.width; x += gridSize) { for (let y = 0; y < s.height; y += gridSize) { drawCell(x, y, gridSize, gridSize, s.random(5,15), s.random(Math.PI * 2)); } } } function drawCell(x, y, w, h, gap, a) { let xStart = x + s.random(w), yStart = y + s.random(h); let slope = Math.tan(a); let c = yStart - slope * xStart; let l1, l2; let i = 0; while( l1 !== null || l2 !== null){ let x0 = x - w/2, x1 = x + w + w/2; let y0 = slope * x0 + c + i * gap / Math.cos(a), y1 = slope * x1 + c + i * gap / Math.cos(a); l1 = clipLine({x:x0,y:y0},{x:x1,y:y1}, {x:x, y:y}, w, h); if (l1 !== null) s.line(l1[0].x, l1[0].y, l1[1].x, l1[1].y); x0 = x - w/2, x1 = x + w + w/2; y0 = slope * x0 + c - i * gap / Math.cos(a), y1 = slope * x1 + c - i * gap / Math.cos(a); l2 = clipLine({x:x0,y:y0},{x:x1,y:y1}, {x:x, y:y}, w, h); if (l2 !== null) s.line(l2[0].x, l2[0].y, l2[1].x, l2[1].y); i++; } } })36:T48c,p5(s => { let gridSize = 10; s.setup = function () { s.createCanvas(800,800); s.background(255); s.stroke(0); s.strokeWeight(2); for (let x = 0; x < s.width; x += gridSize) { for (let y = 0; y < s.height; y += gridSize) { drawCell(x, y, gridSize, gridSize, s.map(x,0,width, 2, 20), s.random(Math.PI * 2)); } } } function drawCell(x, y, w, h, gap, a) { let xStart = x + s.random(w), yStart = y + s.random(h); let slope = Math.tan(a); let c = yStart - slope * xStart; let l1, l2; let i = 0; while( l1 !== null || l2 !== null){ let x0 = x - w/2, x1 = x + w + w/2; let y0 = slope * x0 + c + i * gap / Math.cos(a), y1 = slope * x1 + c + i * gap / Math.cos(a); l1 = clipLine({x:x0,y:y0},{x:x1,y:y1}, {x:x, y:y}, w, h); if (l1 !== null) s.line(l1[0].x, l1[0].y, l1[1].x, l1[1].y); x0 = x - w/2, x1 = x + w + w/2; y0 = slope * x0 + c - i * gap / Math.cos(a), y1 = slope * x1 + c - i * gap / Math.cos(a); l2 = clipLine({x:x0,y:y0},{x:x1,y:y1}, {x:x, y:y}, w, h); if (l2 !== null) s.line(l2[0].x, l2[0].y, l2[1].x, l2[1].y); i++; } } })37:T499,p5(s => { let gridSize = 10; s.setup = function () { s.createCanvas(800,800); s.background(255); s.stroke(0); s.strokeWeight(2); for (let x = 0; x < s.width; x += gridSize) { for (let y = 0; y < s.height; y += gridSize) { drawCell(x, y, gridSize, gridSize, s.map(y,0,width, 2, 10), s.noise(x*0.01,y*0.01) * Math.PI*2); } } } function drawCell(x, y, w, h, gap, a) { let xStart = x + s.random(w), yStart = y + s.random(h); let slope = Math.tan(a); let c = yStart - slope * xStart; let l1, l2; let i = 0; while( l1 !== null || l2 !== null){ let x0 = x - w/2, x1 = x + w + w/2; let y0 = slope * x0 + c + i * gap / Math.cos(a), y1 = slope * x1 + c + i * gap / Math.cos(a); l1 = clipLine({x:x0,y:y0},{x:x1,y:y1}, {x:x, y:y}, w, h); if (l1 !== null) s.line(l1[0].x, l1[0].y, l1[1].x, l1[1].y); x0 = x - w/2, x1 = x + w + w/2; y0 = slope * x0 + c - i * gap / Math.cos(a), y1 = slope * x1 + c - i * gap / Math.cos(a); l2 = clipLine({x:x0,y:y0},{x:x1,y:y1}, {x:x, y:y}, w, h); if (l2 !== null) s.line(l2[0].x, l2[0].y, l2[1].x, l2[1].y); i++; } } })38:T533,p5(s => { let gridSize = 10; let img; s.preload = function () { img = s.loadImage(image) } s.setup = function () { s.createCanvas(800,800); s.background(255); //s.image(img,0,0, 400,400); s.stroke(0); s.strokeWeight(1); for (let x = 0; x < s.width; x += gridSize) { for (let y = 0; y < s.height; y += gridSize) { let b = s.brightness(img.get(x,y)); drawCell(x, y, gridSize, gridSize, s.map(b,0,width, 1, 10), s.noise(x*0.01,y*0.01) * Math.PI*2); } } } function drawCell(x, y, w, h, gap, a) { let xStart = x + s.random(w), yStart = y + s.random(h); let slope = Math.tan(a); let c = yStart - slope * xStart; let l1, l2; let i = 0; while( l1 !== null || l2 !== null){ let x0 = x - w/2, x1 = x + w + w/2; let y0 = slope * x0 + c + i * gap / Math.cos(a), y1 = slope * x1 + c + i * gap / Math.cos(a); l1 = clipLine({x:x0,y:y0},{x:x1,y:y1}, {x:x, y:y}, w, h); if (l1 !== null) s.line(l1[0].x, l1[0].y, l1[1].x, l1[1].y); x0 = x - w/2, x1 = x + w + w/2; y0 = slope * x0 + c - i * gap / Math.cos(a), y1 = slope * x1 + c - i * gap / Math.cos(a); l2 = clipLine({x:x0,y:y0},{x:x1,y:y1}, {x:x, y:y}, w, h); if (l2 !== null) s.line(l2[0].x, l2[0].y, l2[1].x, l2[1].y); i++; } } })39:[{"id":"e20f58b493578114b2a6e71f1debd8931af7ae1d7435a14d5cfa89d37422845330abbb33566716a251e23ad56d21170b32e810a839086057e073d4251e41c941","href":"https://static.observableusercontent.com/files/e20f58b493578114b2a6e71f1debd8931af7ae1d7435a14d5cfa89d37422845330abbb33566716a251e23ad56d21170b32e810a839086057e073d4251e41c941","name":"case2.svg","type":"image/svg+xml","lastModified":1709553873883.774,"size":4212},{"id":"900bb5aa625924d1ea088291ed5b8d3a13916fcf22771015d673aea34daa540ad15f0e1f519ebd5f4fd0492f3beeb9d615e90aa54131d6e5843f41117d37da2d","href":"https://static.observableusercontent.com/files/900bb5aa625924d1ea088291ed5b8d3a13916fcf22771015d673aea34daa540ad15f0e1f519ebd5f4fd0492f3beeb9d615e90aa54131d6e5843f41117d37da2d","name":"case3.svg","type":"image/svg+xml","lastModified":1709554196962.033,"size":4263},{"id":"66cf97f63f6bb9bd8df2211d7a3c865c7678330894dc83fbd1a954102d44a6543fc9ac51d93af7563e3c5c7dca592b10f12dc0169a3792fc26963e917fe90cad","href":"https://static.observableusercontent.com/files/66cf97f63f6bb9bd8df2211d7a3c865c7678330894dc83fbd1a954102d44a6543fc9ac51d93af7563e3c5c7dca592b10f12dc0169a3792fc26963e917fe90cad","name":"bits.svg","type":"image/svg+xml","lastModified":1709554560883.102,"size":6489},{"id":"2d7cfc3f65742d956d6806f31695b235a38053666904a65123aeaac95d4785d942172d7e228351338ca0a0018fcc54fbac7266ad0cb68f8244dbbcdbfdcc70d4","href":"https://static.observableusercontent.com/files/2d7cfc3f65742d956d6806f31695b235a38053666904a65123aeaac95d4785d942172d7e228351338ca0a0018fcc54fbac7266ad0cb68f8244dbbcdbfdcc70d4","name":"bits2.svg","type":"image/svg+xml","lastModified":1709554562971.724,"size":4025},{"id":"0850392a5b4ca55ad72bbf300cdad76072d81e78bc1f9ee7df991b3c1cba81620faff6cac09d12206dd16ea2ecd25f154e484effab90db61daed75c5a6e1de00","href":"https://static.observableusercontent.com/files/0850392a5b4ca55ad72bbf300cdad76072d81e78bc1f9ee7df991b3c1cba81620faff6cac09d12206dd16ea2ecd25f154e484effab90db61daed75c5a6e1de00","name":"Screenshot 2024-03-05 at 9.31.09 AM.png","type":"image/png","lastModified":1709631083105.809,"size":480674}] 31:{"id":"9bf15f76a89551cd","slug":"line-clipping","title":"Line Clipping","thumbnail":"b9da4dd1aa1a9bfe0517f6a76314c6b600acddf00db7c1fec2ff09e66abe7b9c","access_level":"public","create_time":"$D2024-03-04T11:55:09.811Z","update_time":"$D2024-04-09T11:03:24.094Z","view_time":null,"first_public_time":"$D2024-03-04T14:59:56.211Z","has_unpublished_edits":null,"fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":"starter_2024"},"version":188,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null}],"members":[{"type":"individual","id":"e8e99acdbe3aebfb","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":null,"role":"editor"},{"type":"team","id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C","avatar_url":"https://avatars-next.observableusercontent.com/1d9ef6121a0bbd1a75fab479f9891fe1d78cc65f76c394585ae1a7dad0d3abf6","tier":"starter_2024","role":"viewer"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"8a91769c6d3b75ab","slug":"algorithms","title":"Algorithms","owner":{"id":"b2e9840be7b1b607","login":"real-john-cheung","name":"John C"}},"type":"notebook","body":{"title":"Line Clipping","cells":[{"id":0,"value":"# Line Clipping\n\nfrom [sighack](sighack.com), grid based line drawing with Cohen-Sutherland Line Clipping.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"Cohen-Sutherland Line Clipping:\n1. If the line being Clip is entirely inside the window, draw it.\n2. If the line is entirely outside, skip it.\n3. Find new coordinates for endpoints of the line that lie within the clipping window, and repeat the process for the new line\n\nTo perform the steps, consider the endpoints of the line:\n\n* If both endpoints are inside the clip window, then the entire line is inside the window;\n* If both endpoints lie with in the same side out side the window, the entire line is outside the window;\n ![case2.svg](${await FileAttachment(\"case2.svg\").url()})\n\n* If both endpoints lie on different sides of the clip window (inside is consider as another side too), then we have the following cases:\n ![case3.svg](${await FileAttachment(\"case3.svg\").url()})\n\nTo help us figuring out the endpoint conditions, we can encode each side of the window in a simple way:![bits.svg](${await FileAttachment(\"bits.svg\").url()})![bits2.svg](${await FileAttachment(\"bits2.svg\").url()}) ","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":17,"value":"/**\nreturn the region code where the endpoint lies in\n@param {Vector} endpoint {x,y}\n@param {Vector} upperleftPoint {x,y} upperleft corner of the clip window\n@param {number} w width of the clip window\n@param {number} h height of the clip window \n@returns the region code for the endpoint\n**/\nfunction endpointRegionCode(endpoint, upperleftPoint, w, h){\n let code = 0;\n let xmin = upperleftPoint.x, xmax = upperleftPoint.x + w, ymin = upperleftPoint.y, ymax = upperleftPoint.y + h;\n\n if (endpoint.x < xmin) code |= (1 << 0); // endpoint falls on left region of the window\n else if (endpoint.x > xmax) code |= (1 << 1); // endpoint falls on right region of the window\n if (endpoint.y < ymin) code |= (1 << 2); // endpoint falls bellow the window\n else if (endpoint.y > ymax) code |= (1 << 3); // endpoint falls above the window\n \n return code;\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"$33","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":25,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":31,"value":"Now let's test the function out a bit. In the below sketch, I will create a grid with random number of parallel lines at a random angle inside each cell.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":33,"value":"import {p5, p5c} from \"@real-john-cheung/p5js\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":37,"value":"$35","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":127,"value":"Changing the grid size, gap, and angle of the lines will give lots of possibilities for creative coding, below are some examples","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":131,"value":"$36","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":141,"value":"$37","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":148,"value":"$38","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":160,"value":"image = await FileAttachment(\"Screenshot 2024-03-05 at 9.31.09 AM.png\").url()","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W39","stdlib":"1","titling":"auto"}} 32:"$31:body"