25:["$","title",null,{"children":"Convex Polygon Inspection Problem | sklueber | Observable"}] 4b:T4d4,For this route type, the far side of the polygon cannot hide an edge from us. Otherwise we would have to walk around. That means, that the edge we discover last and the edge we potentially make a reflecting contact on before that, are adjacent. Let's just choose an arbitrary edge as the last edge ${tex`e_i`} to discover and the edge to the right of it as ${tex`e_{i-1}`}. That means that we will approach ${tex`e_i`} orthogonally from a point on ${tex`e_{i-1}`} since that will be the shortest way to get there. The point on ${tex`e_{i-1}`} can be determined with the **Heron Operation**. It calculates the point by projecting our start point ${tex`s`} onto ${tex`e_{i-1}`} and then moving it by ${tex`d \tan{\theta_i}`} with ${tex`d`} being the distance from ${tex`s`} to ${tex`e_i`} and ${tex`\theta_i`} being the angle between the adjacent edges. We just try out every combination and classify them: - incomplete: yellow, if it does not see every edge of the polygon - intersecting: red, if the route intersects the polygon - feasible: green, if the route is valid As a nice side-effect, this also catches the routes the route of just walking in a straight line, as then will just cross ${tex`e_{i-1}`} instead of reflecting.4c:T701,// calculate two possible routes with one reflecting contact and no contact to the polygon // params: // s: starting position of the route // e: side of the polygon that is the last to be seen // return: // list of two route objects, one for both possible second-to-last discovered edge function getRouteReflect(s, e) { const route = [new Route("reflect"), new Route("reflect")]; // an edge that is seen from the starting point can't be the last one to be discovered if (currentlySeenEdges.includes(e)) { route[0].f = route[1].f = "n/a"; return route; } const n = polygon.length; const ep1 = (e + 1) % n; const ep2 = (e + 2) % n; const em1 = e === 0 ? n - 1 : e - 1; const a = PVector(ep1.x - e.x, ep1.y - e.y); // possible second to last discovered edges are e_i+1 and e_i-1 const hm1 = [ PVector(e.x - em1.x, e.y - em1.y), PVector(ep2.x - ep1.x, ep2.y - ep2.y) ]; // for the two possible second-to-last discovered edges for (let i = 0; i < 2; i++) { const b = hm1[i]; const theta = PVector.angleBetween(a, b); // reflecting path is not possible if the angle is greater than pi / 2 if (theta >= Math.PI / 2) { route[i].f = "angle"; continue; } const [p, t, valid] = heronOperation(e, i === 1); route[i].addPoints(s, p, t); route[i].f = "feasible"; const seen_s = seenEdgesFromPoint(s); const seen_p = seenEdgesFromPoint(p); const seen_t = seenEdgesFromPoint(t); const seen = new Set([...seen_s, ...seen_p, ...seen_t]); // not every side seen if (seen.size != n) route[i].f = "unseen"; // debugger; if ( lineIntersectsPolygon(polygon, s, p) || lineIntersectsPolygon(polygon, p, t) ) { route[i].f = "intersects"; } } return route; }4d:T470,// e is last side to be discovered, hm1 the side of the reflection point function heronOperation(e, mirrored) { const n = polygon.length; const i = e; let a = polygon[modN(i - 1)]; // necessary because in JS -1 % n = -1 let b = polygon[i]; let c = polygon[(i + 1) % n]; const swap = a.copy(); if (mirrored) { a = c; c = swap; } // project s onto h_{i-1} let projPoint = projectOntoLine(b, a, s); // move point by amount in direction of e_i-1 let theta = PVector.angleBetween(a.copy().sub(b), c.copy().sub(b)); let dist = s.copy().dist(projPoint) * Math.tan(theta); let p_i = projPoint.copy().add(a.copy().sub(projPoint).norm().mult(dist)); // determine t_i by projecting onto h_i let t_i = projectOntoLine(b, c, p_i); // check if t_i is between projections of w^i_ccw and w^i_cw let projCCW = projectOntoLine(b, c, polygon[jump_off_ccw[i].jumpIndex]); let projCW = projectOntoLine(b, c, polygon[jump_off_cw[i].jumpIndex]); // the route is valid if t_i is between the projections of the jump off-points let valid = isBetween(projCCW, projCW, t_i); return [p_i, t_i, valid]; }4e:T6b3,function determine_jump_off(ccw) { let w = []; let p = polygon.map((vec) => vec.copy()); const n = p.length; if (!ccw) p.reverse(); let i = 0; // index of edge extension we want to reach // we start with j = 2 so we have to do a full loop for i=0 because otherwise we will always pick the vertex on the edge itself let j = 2; // index of jump off-vertex we are considering right now while (i < n) { let posJump = p[j % n]; // possible jump-off vector let v1 = p[i % n].copy(); let v2 = p[(i + 1) % n].copy(); // next edge extension let projPoint = projectOntoLine(v1, v2, posJump); // we check if the proposed projection would cross through the polygon // by checking if it is on the right of the current jump-off-candidate's edge let test = halfPlaneTest( posJump.copy(), p[(j + 1) % n].copy(), projPoint.copy() ); let projectionIntersected = ccw ? test < 0 : test > 0; // special case: the polygon is small and i reaches j - 1 ; then we have to keep looking if ((i + 1) % n === j) projectionIntersected = true; // special case: a vector that points backwards should not be detected if ( p[(j + 1) % n].copy().sub(posJump).dot(projPoint.copy().sub(posJump)) < 0 ) projectionIntersected = true; // keep checking next extension if not intersected if (projectionIntersected) { j = (j + 1) % n; // projection was not valid, so we try the next vertex } else { w[ccw ? i : (((n - i - 2) % n) + n) % n] = new JumpOffVector( ccw ? j : (((n - j - 1) % n) + n) % n, projPoint ); i++; // projection was valid, so we look at next extension } } return w; }4f:T503,// params: // e: last edge to be discovered function getRouteDoubleContact(s, e) { let route = [new Route("double_contact"), new Route("double_contact")]; let n = polygon.length; if (currentlySeenEdges.length === 0) { route[0].t = route[1].t = "n/a"; return route; } const [u_cw_index, u_ccw_index] = currentConvexTangentIndices; // both cw and ccw for (let j = 0; j < 2; ++j) { route[j].addPoints(s, polygon[j === 0 ? u_ccw_index : u_cw_index]); let i = j === 0 ? u_ccw_index : u_cw_index; while ( i !== (j === 0 ? jump_off_ccw[mod(e - 1, n)].jumpIndex : jump_off_cw[mod(e + 1, n)].jumpIndex) ) { route[j].addPoint(polygon[i]); i = mod(i + (j === 0 ? 1 : -1), n); } const jump = j === 0 ? jump_off_ccw[mod(e - 1, n)] : jump_off_cw[mod(e + 1, n)]; route[j].addPoints(polygon[jump.jumpIndex], jump.targetPoint); i = jump.jumpIndex; const secondJump = j === 0 ? jump_off_cw[mod(e, n)] : jump_off_ccw[mod(e, n)]; while (i !== secondJump.jumpIndex) { route[j].addPoint(polygon[i]); i = mod(i + (j === 0 ? -1 : 1), n); } route[j].addPoints(polygon[secondJump.jumpIndex], secondJump.targetPoint); route[j].f = "feasible"; } return route; }50:T63b,// k is the edge we bounce on function getRouteReflectFirst(s, cw) { let routes = []; const n = polygon.length; const mi = cw ? 1 : -1; // factor for mirroring the whole thing let q_index = cw ? jump_off_ccw[modN(n - 1)].jumpIndex : jump_off_cw[modN(n - 1)].jumpIndex; for (let j = n - 1; j >= 0; j--) { const k = cw ? j : n - j - 1; let route = new Route("reflect_first"); let p = bounce( s, polygon[q_index], polygon[k], polygon[mod(k + 1 * mi, n)] ); let killswitch = 0; while (killswitch++ < n) { // debugger; let pot_p = bounce( s, polygon[mod(q_index - 1 * mi, n)], polygon[k], polygon[mod(k + 1 * mi, n)] ); if ( mi * halfPlaneTest( polygon[mod(q_index, n)], polygon[mod(q_index - 1 * mi, n)], pot_p.copy() ) > 0 ) break; p = pot_p; q_index = mod(q_index - 1 * mi, n); } if (killswitch === n - 1) { route.f = "intersects"; routes.push(route); continue; } route.addPoints(s, p); let i = q_index; const offJump = cw ? jump_off_cw[mod(k + 1, n)] : jump_off_ccw[modN(k - 2)]; while (i != offJump.jumpIndex) { route.addPoint(polygon[i]); i = mod(i - 1 * mi, n); } route.addPoints(polygon[offJump.jumpIndex], offJump.targetPoint); route.f = "feasible"; if (lineIntersectsPolygon(polygon, route.r[0], route.r[1])) route.f = "intersects"; routes.push(route); } return routes; }51:T418,canvas = { const context = setUpContext(false); // show vertex numbers if (show_vertex_numbers) { for (let i = 0; i < polygon.length; i++) { context.font = "18px Computer Modern"; context.fillStyle = "black"; context.fillText("e_" + i, polygon[i].x, polygon[i].y); } } // determine route let routes = []; if (showRoutes.includes("Reflect")) routes.push(...currentReflectRoutes); if (showRoutes.includes("Double Contact")) routes.push(...currentDoubleContactRoutes); if (showRoutes.includes("Reflect First")) routes.push(...currentReflectFirstRoutes); let feasible = routes.filter( (obj) => obj.f === "feasible" || obj.f === "best" ); feasible.sort((a, b) => a.l - b.l); if (feasible[0] != null) feasible[0].f = "best"; if (showFeasibleOnly) routes = feasible; if (showShortestOnly) routes = [feasible_routes[0]]; for (const r of routes.reverse()) { drawRoute(context, r); } // Show jumps if (show_jumps) { drawJumpOff(context); } yield context.canvas; }52:T518,CornerRadiusCanvas = { const ctx = setUpContext(false, false); let furthestSeen = currentConvexTangentIndices[1]; // changes for clockwise if (polygon[furthestSeen] === undefined) return ctx.canvas; let fovStart = s.copy(); let fovEnd = polygon[furthestSeen].copy(); let distance = 0; for (let i = 0; i < 1 /* polygon.length - 1*/; i++) { const circleCenter = fovStart.copy().lerp(fovEnd, 0.5); const radius = fovStart.dist(fovEnd) / 2; const startAngle = mod(fovStart.copy().sub(fovEnd).angle2D(), 2 * Math.PI); const edge1 = fovStart.copy().sub(fovEnd); const edge2 = fovEnd.copy().sub(polygon[modN(furthestSeen + 1)]); const innerPolygonAngle = PVector.angleBetween(edge1, edge2); ctx.strokeStyle = "blue"; ctx.beginPath(); ctx.arc( fovEnd.x, fovEnd.y, radius * 2, startAngle, startAngle - innerPolygonAngle, true ); ctx.stroke(); // set up next iteration const radiusVertex = fovStart.copy().sub(circleCenter); radiusVertex.rotateBy(-innerPolygonAngle); const nextPos = circleCenter.copy().add(radiusVertex); fovStart = nextPos.copy(); furthestSeen = convexTangentIndicesAt(nextPos)[1]; // changes for clockwise fovEnd = polygon[furthestSeen]; } return ctx.canvas; }53:T889,angleHullCanvas = { const ctx = setUpContext(false, false); let furthestSeen = currentConvexTangentIndices[1]; // changes for clockwise let fovStart = s.copy(); if (polygon[furthestSeen] === undefined) return ctx.canvas; let fovEnd = polygon[furthestSeen].copy(); let distance = 0; for (let i = 0; i < polygon.length; i++) { const circleCenter = fovStart.copy().lerp(fovEnd, 0.5); const radius = fovStart.dist(fovEnd) / 2; const startAngle = mod(fovStart.copy().sub(fovEnd).angle2D(), 2 * Math.PI); const edge1 = fovStart.copy().sub(fovEnd); const edge2 = fovEnd.copy().sub(polygon[modN(furthestSeen + 1)]); const innerPolygonAngle = PVector.angleBetween(edge1, edge2); const phi = Math.max(-innerPolygonAngle + Math.PI * 0.5, 0); const triA = radius; const triBeta = Math.PI / 2 - phi; const triC = Math.sin(phi) * radius * 2; const triB = Math.sqrt( triA ** 2 + triC ** 2 - 2 * triA * triC * Math.cos(triBeta) ); const triGamma = Math.acos( (triA ** 2 + triB ** 2 - triC ** 2) / (2 * triA * triB) ); const visibleConnectingEdge = polygon[2].copy().sub(fovStart); const endAngle = startAngle + Math.PI + triGamma; //ctx.strokeText(PVector.radians2degrees(phi), 300, 300); //ctx.strokeText(triAlpha + triBeta + triGamma, 300, 340); ctx.beginPath(); ctx.strokeStyle = "black"; ctx.lineWidth = 1; ctx.arc(circleCenter.x, circleCenter.y, radius, startAngle, endAngle, true); ctx.stroke(); distance += (Math.PI - triGamma) * 2 * radius; // set up next iteration const forward = edge1.copy().mult(-1).norm(); forward.rotateBy(triGamma).mult(triB); const nextPos = circleCenter.copy().add(forward); fovStart = nextPos.copy(); furthestSeen = convexTangentIndicesAt(nextPos)[1]; // changes for clockwise fovEnd = polygon[furthestSeen]; } ctx.textAlign = "right"; ctx.fillText("path length: " + distance, 550, 20); const offline_distance = feasible_routes[0]?.l; ctx.fillText("optimal path length: " + offline_distance, 550, 30); ctx.fillText("ratio: " + distance / offline_distance, 550, 40); return ctx.canvas; }54:Tcc2,# Technical Aspects This project was implemented using an Observable notebook. Similar to Jupyter notebooks commonly used in Data Science, Observable notebooks offer the ability to seamlessly integrate text with code. However, there are some key differences. ## JavaScript For one, Observable uses JavaScript instead of Python or R. This means it runs directly in the browser and offers access to common tools of web development. In this case, drawing the routes and the polygon is done using HTML Canvas elements. This makes it easy to iterate and offers convenient functions like `arc()` for the online problem. Most notably, Observable offers easy access to [D3.js](https://d3js.org/) and [Observable Plot](https://observablehq.com/plot/). This makes up its primary purpose: quick interactive visualization of data. This is where Observable shines. The visualizations are highly flexible and accessible, giving anyone with internet access the ability to tinker with the data by changing parameters or even all the code behind them. Examples can be found [here](https://observablehq.com/community). ## Reactive cell execution The most important aspect for that is Observable's reactive model for cell execution. Code is split into individual cells just like in Jupyter notebooks. However, in contrast to Jupyter notebooks, cells are not run chronologically from the top. Instead Observable determines the dependencies between the cells and reruns a cell whenever a cell it references changes. That means that changing the way data is filtered in the beginning will immediatly affect the visualization. Also, cell order does not matter, allowing structuring by ease of use, not execution order. For this project, ultimately these features were not essential. The reactive cell execution is useful, especially while developing but does come with some headaches. For example, state is not trivially supported. Cells run once whenever their dependencies change and should be deterministic based on those. Marking a cell with the keyword `mutable` allows it to be permanently changed but can crop up in unexpected ways with other cells not reacting on a change or reacting constantly, meaning an infinite loop (which inconveniently lags the entire editor). This is only done for the coordinates of the polygon which are changed whenever a respective button is pressed. Cells are used for some computed values that are reused in multiple places. A good example are the jump-off points. They are determined whenever their dependency, the polygon, changes. Subsequently everything else that depends on them, like the routes, gets recalculated as well. ## Drawbacks In practice, this approach is very reminiscent of global variables. While it is nice to see the numbers change while moving the cursor, it does come at a steep cost of compromising clean code. For exploratory data analysis with a small number of cells this is a good trade-off. Larger projects with multiple entities could be better served with a more structured object-oriented approach. Nevertheless, the accessibility to JS frameworks as well as the format of combining Markdown prose with code is very appealing. The format of interactive explanatory articles is definitely worth pursuing. 55:T7da,class Watchman { constructor(pos) { this.pos = pos.clone(); this.rays = []; } update(x, y, walls) { this.pos.set(x, y); //mutable s = this.pos; } createRays(walls) { this.rays = []; const epsilon = 10e-7; for (const wall of walls) { const angleA = wall.a.clone().sub(this.pos).angle2D(); const angleB = wall.b.clone().sub(this.pos).angle2D(); this.rays.push(new Ray(this.pos.x, this.pos.y, angleA - epsilon)); this.rays.push(new Ray(this.pos.x, this.pos.y, angleA)); this.rays.push(new Ray(this.pos.x, this.pos.y, angleA + epsilon)); this.rays.push(new Ray(this.pos.x, this.pos.y, angleB - epsilon)); this.rays.push(new Ray(this.pos.x, this.pos.y, angleB)); this.rays.push(new Ray(this.pos.x, this.pos.y, angleB + epsilon)); } this.rays.sort((a, b) => a.angle < b.angle ? 1 : a.angle > b.angle ? -1 : 0 ); } look(walls, ctx) { const hits = []; for (let i = 0; i < this.rays.length; i++) { const ray = this.rays[i]; let closest = null; let record = Infinity; let closestIndex = null; for (const [index, wall] of walls.entries()) { const pt = ray.cast(wall); if (pt) { const d = this.pos.dist(pt); if (d < record) { record = d; closest = pt; closestIndex = index; } } } if (closest) { hits.push([closest, closestIndex]); } } ctx.fillStyle = "rgba(255,255,0, 0.5)"; ctx.beginPath(); hits.forEach((hit, i) => { let [hit_pt, wall_index] = hit; //walls[wall_index].seen = true; // draw visibility polygon if (i === 0) ctx.moveTo(hit_pt.x, hit_pt.y); else ctx.lineTo(hit_pt.x, hit_pt.y); }); ctx.closePath(); ctx.fill(); } show(ctx) { ctx.fillStyle = "black"; ctx.beginPath(this.pos.x, this.pos.y); ctx.arc(this.pos.x, this.pos.y, 4, 0, Math.PI * 2); ctx.fill(); } }56:T448,function lineIntersectsLine(a, b, c, d) { // calculate the cross products of the line segments const crossProductABCD = (d.y - c.y) * (b.x - a.x) - (d.x - c.x) * (b.y - a.y); const crossProductACAB = (a.y - c.y) * (b.x - a.x) - (a.x - c.x) * (b.y - a.y); const crossProductCDAB = (a.y - c.y) * (d.x - c.x) - (a.x - c.x) * (d.y - c.y); // check if the line segments intersect if ( crossProductABCD === 0 && crossProductACAB === 0 && crossProductCDAB === 0 ) { // the line segments are collinear, check if they overlap if ( (a.x <= c.x && c.x <= b.x) || (a.x >= c.x && c.x >= b.x) || (a.y <= c.y && c.y <= b.y) || (a.y >= c.y && c.y >= b.y) ) { return true; } } else if ( crossProductABCD !== 0 && crossProductACAB / crossProductABCD >= 0 && crossProductACAB / crossProductABCD <= 1 && crossProductCDAB / crossProductABCD >= 0 && crossProductCDAB / crossProductABCD <= 1 ) { // the line segments intersect return true; } // the line segments do not intersect return false; }57:T436,// "shader": color all pixels depending on the value of a function // very pretty, very very slow and does not work right now shader = null /*{ const context = DOM.context2d(width, height); var colorScale = d3 .scaleLinear() .domain([0, 1, 900]) .range(["#FFFFFF", d3.interpolatePlasma(0), d3.interpolatePlasma(1)]); const cwidth = context.canvas.width; const cheight = context.canvas.height; const imageData = context.createImageData(cwidth, cheight); // Loop through every pixel in the image and set its color based on the function for (let y = 0; y < cheight; y++) { for (let x = 0; x < cwidth; x++) { const index = (y * cwidth + x) * 4; const color = d3.color(colorScale(contact_b_a(PVector(x, y)))); imageData.data[index] = color.r; // red imageData.data[index + 1] = color.g; // green imageData.data[index + 2] = color.b; // blue imageData.data[index + 3] = 255; // alpha } } // Draw the image data to the canvas context.putImageData(imageData, 0, 0); debugger; //yield context.canvas; }*/58:[] 47:{"id":"d1ff0f22e021620c","slug":"polygon-inspection","title":"Convex Polygon Inspection Problem","thumbnail":"da6f7cc487cb8af4fab142f452bac024289282bd54566a4670cf1a1f82346f48","access_level":"public","create_time":"$D2022-10-13T15:05:07.824Z","update_time":"$D2023-05-25T11:22:47.237Z","view_time":null,"first_public_time":"$D2022-10-13T15:05:07.824Z","has_unpublished_edits":null,"fork":false,"stars":2,"starred":false,"owner":{"type":"team","id":"f6c849906ae3c8c2","login":"sklueber","name":"","avatar_url":"https://avatars-next.observableusercontent.com/ec017c3fc61aae299a05fd392f63ffb4d83205cef1839ee09f5108093fa9c9d5","tier":"starter_2024","bio":"","followed_by_you":false,"follows_you":false},"version":4674,"publish_version":null,"role":null,"authored":false,"authors":[{"type":"individual","id":"ac2023a1187a8f0d","login":"sklueber","name":"","avatar_url":"https://avatars-next.observableusercontent.com/ec017c3fc61aae299a05fd392f63ffb4d83205cef1839ee09f5108093fa9c9d5","tier":null,"bio":"","followed_by_you":false,"follows_you":false}],"members":[{"type":"individual","id":"ac2023a1187a8f0d","login":"sklueber","name":"","avatar_url":"https://avatars-next.observableusercontent.com/ec017c3fc61aae299a05fd392f63ffb4d83205cef1839ee09f5108093fa9c9d5","tier":null,"role":"editor"}],"comments":[],"custom_thumbnail":false,"trashed":false,"lapsed":null,"subscribed":null,"forks":0,"collection":null,"type":"notebook","body":{"titling":"auto","title":"Convex Polygon Inspection Problem","cells":[{"id":2570,"value":"# Convex Polygon Inspection Problem","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1393,"value":"## Offline Algorithm","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":3914,"value":"Imagine you are a watchman guarding a convex building. Your shift is almost over, just one more glance at each of the walls and you're done.\n\nOf course, you are a mathematical watchman. As long as you touch the hypothetical extension of a wall, you have seen it.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":3898,"value":"introCanvas = {\n const ctx = setUpContext(true);\n\n s; // to rerun, when s changes\n polygon;\n\n yield ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4660,"value":"Inputs.bind(Inputs.button(\"New polygon\"), viewof newBuildingButton)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3929,"value":"So, how do you go about optimizing your final walk of the day?\n\nIn other words:\n_How do you determine the shortest inspection path starting from position ${tex`s`} that sees all edges of a convex polygon?_\n\nWe are going to look at the different types of route the optimal path could be. You can take a look at the **code that generates each route type** by clicking the **arrow (`>`)** that appears when you hover the function name below the illustration. All the other cells can be inspected (or even tinkered with) like this too but they will likely be less interesting.\n\nLet's start simple. Just walk around the building counterclockwise until you have seen all edges.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":3966,"value":"naiveCanvas = {\n const ctx = setUpContext(false);\n\n s;\n polygon;\n drawRoute(ctx, naive_route_ccw(s));\n\n yield ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3937,"value":"function naive_route_ccw(s) {\n const route = new Route(\"naive\");\n route.addPoint(s);\n \n let seen = new Set(seenEdgesFromPoint(s));\n\n let vertexIndex = convexTangentIndicesAt(s)[1];\n if (isNaN(vertexIndex)) return null;\n\n while (seen.size !== polygon.length) {\n route.addPoint(polygon[vertexIndex]);\n for (let e of seenEdgesFromPoint(polygon[vertexIndex])) seen.add(e);\n vertexIndex = modN(vertexIndex + 1);\n }\n\n route.f = \"feasible\";\n return route;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4020,"value":"In some cases this might work fine. It might even be the optimal route. But what if you're not that lucky? What if someone pressed the button below and turned our building into a worse scenario?","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4023,"value":"viewof triangleBuilding = Inputs.toggle({\n label: \"Triangle Building\",\n value: false\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4075,"value":"$${triangleBuilding ? \"Now you can see that\" : \"After pressing the checkbox, you will see that\"} clearly there has to be a better option. Our route does not even have to make contact with the polygon.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4080,"value":"### Route Type 1: Reflecting, No Contact With The Polygon","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4088,"value":"$4b","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4090,"value":"reflectCanvas = {\n const ctx = setUpContext();\n\n const routes = currentReflectRoutes;\n\n for (const r of routes) {\n drawRoute(ctx, r);\n }\n\n const colors = d3.schemeCategory10;\n\n yield ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4450,"value":"Inputs.bind(Inputs.button(\"New polygon\"), viewof newBuildingButton)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4430,"value":"Now the triangle building cannot trick us anymore. But as you can quickly see by generating a new random polygon, this route type will not be possible in all cases. We will have to consider the two other possible ways a route a could look like.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":2617,"value":"$4c","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1858,"value":"$4d","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4108,"value":"### Route Type 2: Contact With The Polygon Before and After Reflecting\n\nIf the shortest route has to walk around the polygon, the shortest way to do so, is by hugging the wall. However to see the final route we want to discover, it might be shorter to leave the polygon boundary and \"jump off\" straight towards that final edge extension.\n\nFor this, we will need the _jump-off vertices_ of each edge.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1590,"value":"#### Jump-off vertices\n\nFor each vertex, we \n1. Project it onto the next edge extension\n2. Check, if that projection intersects the polygon. (It will never intersect towards the very next edge, but will with a later one.)\n3. If it does not, we mark the vertex as a jump-off vertex for the edge extension. Otherwise, we leave the algorithm and restart it with the next vertex.\n4. Repeat with checking the next edge extension.\n\nWe will do this for both clockwise and counterclockwise edges. In the illustration below, they are drawn blue and orange respectively.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4461,"value":"jumpOffCanvas = {\n const ctx = setUpContext();\n\n s; // to redraw when s is changed\n drawJumpOff(ctx);\n\n yield ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":362,"value":"viewof newBuildingButton = Inputs.button(\"New polygon\")","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1797,"value":"$4e","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4314,"value":"Constructing the route is relatively simple. We know which vertex is the (counter-) clockwise-most we can see. We will walk straight towards it and then keep hugging the polygon until we reach the jump off point of the final edge we will have to discover.\n\nAgain, we can change which edge will be the one to be discovered second-to-last (left or right of the last one). Iterating over each possible last-discovered edge this gives a lot of overlapping routes. You can uncheck `Show all routes` and scroll through them one by one with the slider.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4110,"value":"doubleContactCanvas = {\n const ctx = setUpContext();\n\n let routes = showAll\n ? currentDoubleContactRoutes\n : [currentDoubleContactRoutes[showIndex]];\n\n drawJumpOff(ctx);\n\n // show vertex numbers\n\n for (let i = 0; i < polygon.length; i++) {\n ctx.font = \"18px Computer Modern\";\n ctx.fillStyle = \"black\";\n ctx.fillText(\"e_\" + i, polygon[i].x, polygon[i].y);\n }\n\n for (const r of routes) {\n drawRoute(ctx, r);\n }\n\n let infoText = showAll\n ? \"all routes shown\"\n : \"final edge to be seen: \" + Math.floor(showIndex / 2);\n ctx.textAlign = \"right\";\n ctx.fillText(infoText, 550, 30);\n\n yield ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4123,"value":"viewof showAll = Inputs.toggle({ label: \"Show all routes\", value: false })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4168,"value":"viewof showIndex = Inputs.range([0, currentDoubleContactRoutes.length], {\n value: 0,\n step: 1,\n label: \"Route\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2847,"value":"$4f","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4136,"value":"### Route Type 3: Reflect, Then Contact\n\nThe final route type is contacting the second-to-last edge before contacting the polygon.\n\nThis type is less obvious. We could potentially reflect on an arbitrary edge before making contact with the polygon at an arbitrary vertex and then leaving it again to discover an arbitrary last edge. The key here is to cut down these options. \n\nFor example, when incrementing the edge we reflect on, the jump-on vector on the polygon will be the same or a later one than the one of the edge before. That means we can keep incrementing it while computing the different routes that end on the same last-discovered edge and don't have to recheck all the previous edges every time.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4138,"value":"ReflectFirstCanvas = {\n const ctx = setUpContext();\n\n let routes = showAll ? currentReflectFirstRoutes : [currentReflectFirstRoutes[showIndexReflectFirst]];\n\n for (const r of routes) {\n drawRoute(ctx, r);\n }\n\n yield ctx.canvas;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4498,"value":"Inputs.bind(Inputs.toggle({label :\"Show all routes\", value: false}), viewof showAll)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4495,"value":"viewof showIndexReflectFirst = Inputs.range([0, currentReflectFirstRoutes.length], {\n value: 0,\n step: 1,\n label: \"Route\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3129,"value":"$50","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4164,"value":"## Result\n\nFinally, we have generated all potential routes. A lot of them are not actually valid inspection routes. We can filter these out. Now we can just pick the shortest one!","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":759,"value":"$51","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4523,"value":"## Playground","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4196,"value":"Inputs.bind(Inputs.button(\"New polygon\"), viewof newBuildingButton)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":684,"value":"viewof number_of_sides = Inputs.range([3, 150], {\n label: \"Number of sides\",\n step: 1,\n value: 6\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4335,"value":"viewof showRoutes = Inputs.select([\"Reflect\", \"Double Contact\", \"Reflect First\"], {multiple: true, label: \"Select routes (ctrl + click for multiple)\", value: [\"Reflect\", \"Double Contact\", \"Reflect First\"] })","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4343,"value":"viewof showFeasibleOnly = Inputs.toggle({label: \"Show feasible only\", value : true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4359,"value":"viewof showShortestOnly = Inputs.toggle({label: \"Show shortest only\", value : true})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2101,"value":"viewof show_extensions = Inputs.toggle({\n label: \"Show Edge Extensions\",\n value: true\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2533,"value":"viewof show_jumps = Inputs.toggle({\n label: \"Show jump off points\",\n value: false\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4211,"value":"viewof show_vertex_numbers = Inputs.toggle({\n label: \"Show vertex numbers\",\n value: false\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3348,"value":"all_offline_routes = {\n let routes = [];\n routes.push(...currentReflectRoutes);\n routes.push(...currentDoubleContactRoutes);\n routes.push(...currentReflectFirstRoutes);\n\n return routes;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4606,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":3390,"value":"# Online Strategy","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4237,"value":"How should you move if you don't know the polygon beforehand? _What is a competetive online strategy to find the shortest inspection path?_\n","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4239,"value":"## Inspection of a convex chain\n\nFrom the perspective of the watchman, what he sees is essentially a convex chain of vertices. So for now, we will consider this problem.\n\n\n### The Corner-Radius Strategy","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4565,"value":"Again, one strategy we could use is to simply hug the polygon wall. But again, this could lead us to an arbitrarily long route. One strategy to approach at least a bounded multiple of the shortest length, is to walk around the corners of the chain in a circle. We call this the Corner-Radius Strategy.\n\nThe illustration shows how this step looks for the next corner. We just repeat this step from the next position.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4248,"value":"$52","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4600,"value":"Inputs.bind(Inputs.button(\"New polygon\"), viewof newBuildingButton)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4570,"value":"A significant improvement over this is centering the circle between your position and the last vertex you are able to see. This constructs the Angle Hull of the polygon.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":3395,"value":"$53","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3802,"value":"## Searching on two sides\n\nLet's remember the triangle building from the offline case again. It showed us that just blindly walking in one direction and hoping for the best can be arbitrarily bad, if the alternative of taking a short look on the other side would show us the whole polygon quickly.\n\nThe solution to this is to keep looking back and forth. This way can limit the worst case.\n\nIn order to determine how far the watchman should walk into one direction before turning back, we need to determine a lower bound ${tex`\\lambda`} of the shortest inspection route. If we turned around before walking that far, we couldn't have seen the entire polygon anyways.\n\nTo compute a lower bound, we need to create a parallel \"sight box\". When we reach two points that restrict the possible locations of the rest of polygon.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":3797,"value":"function getPathLowerBound(s) {\n const [a, b] = convexTangentIndicesAt(s).map((i) => polygon[i]);\n if (a === undefined || b === undefined) return 0;\n const s_a = a.copy().sub(s);\n const aLinePoint = s.copy().add(new PVector(-s_a.y, s_a.x));\n const B_a = projectOntoLine(s, aLinePoint, b);\n const dist1 = B_a.dist(s) / 2;\n\n const s_b = b.copy().sub(s);\n const bLinePont = s.copy().add(new PVector(-s_b.y, s_a.x));\n const A_b = projectOntoLine(s, bLinePont, a);\n const dist2 = A_b.dist(s) / 2;\n\n return Math.min(dist1, dist2);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3817,"value":"currentLowerBound = getPathLowerBound(s)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4580,"value":"## Final Online Strategy\n\nTaking this approach yields a worst-case ratio of ${tex`9c`} compared to the optimal inspection route. ${tex`c`} is the competetiveness of the convex chain inspection strategy.\n\nAs such, the watchman should walk around the corners following the Angle Hull Strategy. He should turn around after having walked a distance of ${tex`\\lambda`}, return to his last turnaround point and walk the distance again. If he keeps doing this until he has seen the entire polygon, his path will have been at most ${tex`9 \\frac{\\pi}{2}`} times longer than the ideal shortest path.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4604,"value":"---","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":1305,"value":"$54","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4228,"value":"# References\n\nSome of the best examples of interactive blog posts are certainly the ones written by [Bartosz Ciechanowski](https://ciechanow.ski/). Strong recommendation to take a look.\n\n\nThis article closely follows Kyle P. Clarkson's Master's Thesis at the University of British Columbia. It gives an overview of the problem and formulates both the offline and online algorithms described here. It also expands on the problem with variations like a specified termination point or a required minimum angle to count an edge as seen. The online algorithm was extracted into a separate paper as well.\n\n1. K. P. Clarkson, „On competitive strategies for external exploration of a convex polygon“, University of British Columbia, 2020. doi: 10.14288/1.0395351.\n2. K. Clarkson und W. Evans, „External Exploration of a Convex Polygon“, Aug. 2020.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4232,"value":"# Appendix","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":4408,"value":"These cells contain all the remaining code needed to run this project. You can view their content by clicking the arrow (`>`) that appears when hovering the mouse pointer next to them. Using the `Open minimap pane` button on the right of the screen (two circles connected by a line) will show which cells use them and are used by them.","pinned":false,"hidden":false,"mode":"md","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"","database":"$undefined"},{"id":2614,"value":"// type: which algorithm generated the route\n// r: route consisting of points that are visited in order\n// l: length of the calculated route\n// f: whether the route is feasible, i.e. does not cross the polygon and sees all sides\nclass Route {\n constructor(type, r = [], l = 0, f) {\n this.type = type;\n this.r = r;\n this.l = l;\n this.f = f;\n }\n\n addPoint(p) {\n if (this.r.length > 0) {\n this.l += this.r[this.r.length - 1].dist(p);\n }\n this.r.push(p);\n }\n\n addPoints(...points) {\n for (const p of points) {\n this.addPoint(p);\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2941,"value":"class JumpOffVector {\n constructor(jumpIndex, targetPoint) {\n this.jumpIndex = jumpIndex;\n this.targetPoint = targetPoint;\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":790,"value":"class Wall {\n #extension_start;\n #extension_end;\n\n constructor(x1, y1, x2, y2) {\n this.a = PVector(x1, y1);\n this.b = PVector(x2, y2);\n this.color = wallColor;\n this.seen = false;\n\n let slope = this.b.copy().sub(this.a).mult(500);\n this.#extension_start = this.a.copy().add(slope);\n this.#extension_end = this.b.copy().sub(slope);\n }\n\n show(ctx) {\n ctx.strokeStyle = this.seen ? \"green\" : this.color;\n ctx.beginPath();\n ctx.moveTo(this.a.x, this.a.y);\n ctx.lineTo(this.b.x, this.b.y);\n ctx.lineWidth = 3;\n ctx.stroke();\n\n // Draw extension\n ctx.beginPath();\n if (show_extensions) {\n ctx.moveTo(this.a.x, this.a.y);\n ctx.lineTo(this.#extension_end.x, this.#extension_end.y);\n\n ctx.moveTo(this.b.x, this.b.y);\n ctx.lineTo(this.#extension_start.x, this.#extension_start.y);\n }\n ctx.lineWidth = 0.5;\n ctx.setLineDash([5, 5]);\n ctx.strokeStyle = \"black\";\n ctx.stroke();\n\n ctx.setLineDash([]);\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":781,"value":"$55","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":872,"value":"watchman = new Watchman(startPos)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2640,"value":"currentReflectRoutes = {\n let routes = [];\n for (let i = 0; i < polygon.length; ++i) {\n routes.push(...getRouteReflect(s, i));\n }\n return routes;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2955,"value":"currentDoubleContactRoutes = {\n let routes = [];\n for (let i = 0; i < polygon.length; ++i) {\n routes.push(...getRouteDoubleContact(s, i));\n }\n\n return routes;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3214,"value":"currentReflectFirstRoutes = {\n let routes = [];\n routes.push(...getRouteReflectFirst(s, false));\n routes.push(...getRouteReflectFirst(s, true));\n\n return routes;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2620,"value":"currentlySeenEdges = seenEdgesFromPoint(s)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2800,"value":"feasible_routes = {\n let feasible_routes = all_offline_routes.filter(\n (obj) => obj.f === \"feasible\"\n );\n feasible_routes.sort((a, b) => a.l - b.l);\n if (feasible_routes[0] != null) feasible_routes[0].f = \"best\";\n return feasible_routes;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3274,"value":"function modN(a) {\n return mod(a, polygon.length);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3085,"value":"function mod(a, b) {\n return ((a % b) + b) % b;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1922,"value":"mutable s = startPos // current watchman position","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3131,"value":"// return point p, where the shortest path from s to q, that contacts h, contacts h\nfunction bounce(s, q, h1, h2) {\n // at point p, the angle from p to s is the same as to q\n // that is the case, when p is placed according to the ratio between the heights to the line of s and q\n\n let s_proj = projectOntoLine(h1, h2, s);\n let q_proj = projectOntoLine(h1, h2, q);\n let h_s = s.dist(s_proj);\n let h_q = q.dist(q_proj);\n let p = s_proj.add(q_proj.sub(s_proj).mult(h_s / (h_s + h_q)));\n\n return p;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":963,"value":"// check which side of the line defined by a and b point c is on\n// https://stackoverflow.com/a/3461533\nhalfPlaneTest = (a, b, c) => {\n return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2762,"value":"routeColor = ({\n best: \"darkblue\",\n feasible: \"limegreen\",\n unseen: \"yellow\",\n intersects: \"red\",\n angle: \"mediumorchid\"\n})","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1595,"value":"jump_off_cw = determine_jump_off(false)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1800,"value":"jump_off_ccw = determine_jump_off(true)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2119,"value":"// check if c is between a and b, assuming all of them are on one line\nfunction isBetween(a, b, c) {\n let dist_a_c = c.dist(a);\n let dist_b_c = c.dist(b);\n let dist_a_b = b.dist(a);\n let diff = dist_a_c + dist_b_c - dist_a_b;\n return diff < 1e-12;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2722,"value":"function lineIntersectsPolygon(polygon, p1, p2) {\n const n = polygon.length;\n let intersects = false;\n for (let i = 0, j = n - 1; i < n; j = i++) {\n if (lineIntersectsLine(p1, p2, polygon[i], polygon[j])) {\n // The line segment intersects an edge of the polygon\n return true;\n }\n }\n return intersects;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2705,"value":"$56","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2724,"value":"function pointInPolygon(polygon, point) {\n // Use ray casting algorithm to determine if point is inside polygon\n let inside = false;\n for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {\n const p1 = polygon[i];\n const p2 = polygon[j];\n if (\n p1.y > point.y !== p2.y > point.y &&\n point.x < ((p2.x - p1.x) * (point.y - p1.y)) / (p2.y - p1.y) + p1.x\n ) {\n inside = !inside;\n }\n }\n return inside;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2160,"value":"$57","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3734,"value":"function convexTangentIndicesAt(p) {\n const u = seenEdgesFromPoint(p);\n let u_cw = u[0]; // \"smallest\" value\n let u_ccw = u[0]; // \"largest\" value\n\n for (let i = 1; i < u.length; ++i) {\n if (u[i - 1] + 1 === u[i]) {\n u_ccw = u[i]; // if chain is not broken, keep growing u_ccw\n } else {\n u_cw = u[i];\n break;\n }\n }\n u_ccw = (u_ccw + 1) % polygon.length; // edges were numbered by their \"smaller\" vertex\n return [u_cw, u_ccw];\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2888,"value":"// return the indices of the outermost currently visible vertices\ncurrentConvexTangentIndices = {\n return convexTangentIndicesAt(s);\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3942,"value":"function drawRoute(context, route) {\n let points = route?.r;\n // draw route\n if (points != null && points.length > 0) {\n context.strokeStyle = routeColor[route.f];\n context.lineWidth = 3;\n context.fillStyle = \"black\";\n context.beginPath();\n context.moveTo(points[0].x, points[0].y);\n for (let i = 1; i < points.length; i++) {\n context.lineTo(points[i].x, points[i].y);\n }\n context.stroke();\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4151,"value":"function drawJumpOff(context, ccw) {\n context.fillStyle = \"orange\";\n for (let j = 0; j < 2; ++j) {\n let jumps = j === 0 ? jump_off_ccw : jump_off_cw;\n\n for (const [i, w] of jumps.entries()) {\n context.strokeStyle = j === 0 ? \"orange\" : \"turquoise\";\n context.beginPath();\n context.lineWidth = 2;\n context.moveTo(polygon[w.jumpIndex].x, polygon[w.jumpIndex].y);\n /*context.fillText(\n i,\n polygon[w.jumpIndex].x,\n polygon[w.jumpIndex].y + 12 * i\n );*/\n context.lineTo(w.targetPoint.x, w.targetPoint.y);\n\n context.stroke();\n }\n }\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":2438,"value":"seenEdgesFromPoint = (p) => {\n let seen = [];\n for (let i = 0; i < polygon.length; i++) {\n if (\n halfPlaneTest(polygon[i], polygon[(i + 1) % polygon.length], p) >=\n -0.0001\n ) {\n if (i === undefined || isNaN(i)) throw new \"huh\"();\n seen.push(i);\n }\n }\n return seen;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1952,"value":"function projectOntoLine(lineA, lineB, point) {\n let normDir = lineB.copy().sub(lineA).norm();\n let dotProduct = point.copy().sub(lineA).dot(normDir);\n let projVec = normDir.mult(dotProduct);\n let projPoint = lineA.copy().add(projVec);\n return projPoint;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":878,"value":"startPos = PVector(400, 200)","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3952,"value":"function setUpContext(fov = false, chain = false) {\n const context = DOM.context2d(width, height);\n context.fillStyle = \"white\";\n context.fillRect(0, 0, width, height);\n\n if (fov) watchman.createRays(walls);\n\n context.canvas.addEventListener(\"mousemove\", (e) => {\n watchman.update(e.offsetX, e.offsetY, walls);\n if (fov) watchman.createRays(walls);\n mutable s = watchman.pos;\n });\n\n for (let wall of chain ? walls.slice(0, walls.length - 1) : walls) {\n wall.show(context);\n }\n\n if (fov) watchman.look(walls, context);\n watchman.show(context);\n\n return context;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":356,"value":"mutable ABC = []","pinned":false,"hidden":true,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":975,"value":"// TODO redo ABC in all places\npolygon = {\n let poly = [];\n for (const p of ABC) {\n poly.push(PVector(p[0], p[1]));\n }\n return poly;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4027,"value":"triangleButton = {\n if (triangleBuilding)\n mutable ABC = [\n [200, 310],\n [300, 310],\n [250, 60]\n ];\n else generateBuilding();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":182,"value":"generateBuildingButton = {\n newBuildingButton;\n generateBuilding();\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":4065,"value":"function generateBuilding() {\n mutable ABC = makeConvexPolygon(number_of_sides).map((point) =>\n point.map((coord) => Math.round(50 + coord * 300)).reverse()\n );\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":909,"value":"walls = {\n let walls = [];\n\n // bounding walls\n walls.push(new Wall(-1, -1, width, -1));\n walls.push(new Wall(width, -1, width, height));\n walls.push(new Wall(width, height, -1, height));\n walls.push(new Wall(-1, height, -1, -1));\n\n // polygon walls\n let abc = ABC;\n for (let i = 0; i < abc.length - 1; i++) {\n walls.push(new Wall(...abc[i], ...abc[i + 1]));\n }\n walls.push(new Wall(...abc[abc.length - 1], ...abc[0]));\n return walls;\n}","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1287,"value":"wallColor = \"black\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1228,"value":"width = 600","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":1224,"value":"height = 400","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":3,"value":"import {makeConvexPolygon} from \"@stwind/random-convex-polygons\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":743,"value":"import { PVector } from \"@makio135/utilities\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"},{"id":754,"value":"import { Ray } from \"@makio135/hello-raycasting\"","pinned":false,"hidden":false,"mode":"ojs","author":"$undefined","summary":"$undefined","tool":"$undefined","providerMetadata":"$undefined","attachments":"$undefined","output":"$undefined","database":"$undefined"}],"files":"$W58","stdlib":"1"}} 24:null