2d:null 2e:["$","title",null,{"children":"Segments clipping for pen plotting | Philippe Deschaseaux | Observable"}] 33:T14f7,function Polygons() { const polygonList = []; const vec = ([x1, y1], [x2, y2]) => [x2 - x1, y2 - y1]; const Polygon = class { constructor() { this.cp = []; // clip path: array of [x,y] pairs this.dp = []; // 2d lines [x0,y0],[x1,y1] to draw this.aabb = []; // AABB bounding box } addPoints(...points) { // add point to clip path and update bounding box let xmin = 1e5, xmax = -1e5, ymin = 1e5, ymax = -1e5; (this.cp = [...this.cp, ...points]).forEach((p) => { (xmin = Math.min(xmin, p[0])), (xmax = Math.max(xmax, p[0])); (ymin = Math.min(ymin, p[1])), (ymax = Math.max(ymax, p[1])); }); this.aabb = [ (xmin + xmax) / 2, (ymin + ymax) / 2, (xmax - xmin) / 2, (ymax - ymin) / 2 ]; } addSegments(...points) { // add segments (each a pair of points) points.forEach((p) => this.dp.push(p)); } addOutline() { for (let i = 0, l = this.cp.length; i < l; i++) { this.dp.push(this.cp[i], this.cp[(i + 1) % l]); } } draw(plot) { const start = [0, 0]; let pos = start; for (let i = 0, l = this.dp.length; i < l; i += 2) { plot.move(...vec(pos, (pos = this.dp[i]))); plot.draw(...vec(pos, (pos = this.dp[i + 1]))); } plot.move(...vec(pos, start)); } addHatching(a, d) { const tp = new Polygon(); tp.cp.push([-1e5, -1e5], [1e5, -1e5], [1e5, 1e5], [-1e5, 1e5]); const dx = Math.sin(a) * d, dy = Math.cos(a) * d; const cx = Math.sin(a) * 200, cy = Math.cos(a) * 200; for (let i = 0.5; i < 150 / d; i++) { tp.dp.push([dx * i + cy, dy * i - cx], [dx * i - cy, dy * i + cx]); tp.dp.push([-dx * i + cy, -dy * i - cx], [-dx * i - cy, -dy * i + cx]); } tp.boolean(this, false); this.dp = [...this.dp, ...tp.dp]; } inside(p) { let int = 0; // find number of i ntersection points from p to far away for (let i = 0, l = this.cp.length; i < l; i++) { if ( this.segment_intersect( p, [0.1, -1000], this.cp[i], this.cp[(i + 1) % l] ) ) { int++; } } return int & 1; // if even your outside } boolean(p, diff = true) { // bouding box optimization by ge1doot. if ( Math.abs(this.aabb[0] - p.aabb[0]) - (p.aabb[2] + this.aabb[2]) >= 0 && Math.abs(this.aabb[1] - p.aabb[1]) - (p.aabb[3] + this.aabb[3]) >= 0 ) return this.dp.length > 0; // polygon diff algorithm (narrow phase) const ndp = []; for (let i = 0, l = this.dp.length; i < l; i += 2) { const ls0 = this.dp[i]; const ls1 = this.dp[i + 1]; // find all intersections with clip path const int = []; for (let j = 0, cl = p.cp.length; j < cl; j++) { const pint = this.segment_intersect( ls0, ls1, p.cp[j], p.cp[(j + 1) % cl] ); if (pint !== false) { int.push(pint); } } if (int.length === 0) { // 0 intersections, inside or outside? if (diff === !p.inside(ls0)) { ndp.push(ls0, ls1); } } else { int.push(ls0, ls1); // order intersection points on line ls.p1 to ls.p2 const cmpx = ls1[0] - ls0[0]; const cmpy = ls1[1] - ls0[1]; int.sort( (a, b) => (a[0] - ls0[0]) * cmpx + (a[1] - ls0[1]) * cmpy - (b[0] - ls0[0]) * cmpx - (b[1] - ls0[1]) * cmpy ); for (let j = 0; j < int.length - 1; j++) { if ( (int[j][0] - int[j + 1][0]) ** 2 + (int[j][1] - int[j + 1][1]) ** 2 >= 0.001 ) { if ( diff === !p.inside([ (int[j][0] + int[j + 1][0]) / 2, (int[j][1] + int[j + 1][1]) / 2 ]) ) { ndp.push(int[j], int[j + 1]); } } } } } return (this.dp = ndp).length > 0; } //port of http://paulbourke.net/geometry/pointlineplane/Helpers.cs segment_intersect(l1p1, l1p2, l2p1, l2p2) { const d = (l2p2[1] - l2p1[1]) * (l1p2[0] - l1p1[0]) - (l2p2[0] - l2p1[0]) * (l1p2[1] - l1p1[1]); if (d === 0) return false; const n_a = (l2p2[0] - l2p1[0]) * (l1p1[1] - l2p1[1]) - (l2p2[1] - l2p1[1]) * (l1p1[0] - l2p1[0]); const n_b = (l1p2[0] - l1p1[0]) * (l1p1[1] - l2p1[1]) - (l1p2[1] - l1p1[1]) * (l1p1[0] - l2p1[0]); const ua = n_a / d; const ub = n_b / d; if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) { return [ l1p1[0] + ua * (l1p2[0] - l1p1[0]), l1p1[1] + ua * (l1p2[1] - l1p1[1]) ]; } return false; } }; return { list: () => polygonList, create: () => new Polygon(), draw: (plot, p, addToVisList = true) => { for (let j = 0; j < polygonList.length && p.boolean(polygonList[j]); j++); p.draw(plot); if (addToVisList) polygonList.push(p); } }; }34:T405,{ const plot = Plot(); const polygons = new Polygons(); const { random, cos, sin, PI } = Math; function drawStar(turtle) { const [x, y] = [200 * random() - 100, 200 * random() - 100]; const [a, s] = [random() * PI, 10 + 10 * random()]; const polar = (i) => [a + (i / 5) * PI, s * (i % 2 ? 1 : 0.45)]; const cart = ([a, dist]) => [x + cos(a) * dist, y + sin(a) * dist]; const cp = [...Array(10)].map((_, i) => polar(i)).map(cart); const p1 = polygons.create(); p1.addPoints(...cp); p1.addOutline(); // polygon 1, star with outline polygons.draw(plot, p1, true); // draw polygon with outline and add to polygon list const p2 = polygons.create(); p2.addPoints(...cp.map(([x, y]) => [x + 1, y + 3])); // shadow offset p2.addHatching(-PI / 4, 0.5); // polygon 2, star shadow polygons.draw(plot, p2, false); // draw shadow, don't add to polygon list } for (let i = 0; i < 1000; i++) drawStar(plot); return viewer([width, 400]).view(plot, { "stroke-width": 0.2 }); }35:[] 31:{"id":"3c04a775cb657aef","slug":"segments-clipping-for-pen-plotting","title":"Segments clipping for pen plotting","thumbnail":"49e3b8e7b5c25c76853ac31b4ed41e895e2facb91573182f4e68e995d0ccb899","access_level":"public","create_time":"$D2024-04-21T09:16:36.098Z","update_time":"$D2024-11-13T15:58:14.407Z","view_time":null,"first_public_time":"$D2024-10-27T19:14:56.312Z","fork":false,"stars":0,"starred":false,"owner":{"type":"team","id":"cf2a83be2759e071","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":"starter_2024"},"version":59,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"7c1eebd3c1c51af1","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":null}],"members":[{"type":"individual","id":"7c1eebd3c1c51af1","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":null,"role":"editor"},{"type":"team","id":"cf2a83be2759e071","login":"ehouais","name":"Philippe Deschaseaux","avatar_url":"https://avatars-next.observableusercontent.com/59e97a66cd990ae4d696ee6feb742004d97f024d9bc0db66fbc4b60357d0005f","tier":"starter_2024","role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":{"id":"43e6ecff4165448a","slug":"pen-plotter","title":"Pen plotter","owner":{"id":"cf2a83be2759e071","login":"ehouais","name":"Philippe Deschaseaux"}},"type":"notebook","body":{"title":"Segments clipping for pen plotting","cells":[{"id":0,"value":"# Segments clipping for pen plotting","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":7,"value":"Code grabbed from https://turtletoy.net/turtle/a5befa1f8d","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":10,"value":"$33","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":13,"value":"$34","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":52,"value":"{\n const plot = Plot();\n const polygons = new Polygons();\n const p1 = polygons.create();\n p1.addPoints([0, 0], [100, 0], [100, 100], [0, 100]);\n p1.addOutline();\n polygons.draw(plot, p1, true);\n const p2 = polygons.create();\n p2.addPoints([10, 10], [110, 10], [110, 60], [10, 60]);\n p2.addOutline();\n polygons.draw(plot, p2, true);\n return viewer([width, 400]).view(plot, { \"stroke-width\": 0.2 });\n}","pinned":true,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":17,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","output":"","database":"$undefined"},{"id":36,"value":"import { Plot, viewer } from \"@ehouais/pivot-format-for-plotter-experiments\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"},{"id":19,"value":"import { Turtle, finalize } from \"@ehouais/hello-turtletoy\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W35","stdlib":"1","titling":"auto"}} 32:"$31:body"