31:T443,slide`## Then we find the list of left edges.
We do this by: > *1.* walk around the polygon and check the coordinates of neighboring vertices to determine which are vertical/slanted neighbors and which are horizontal neighbors. We tie the vertical and horizontal neighbor info to each vertex so we can access it easily later. *O(n)* time.

> *2.* walk around the polygon, compare vertex coordinates and note every edge that is not horizontal. *O(n)* time.

> *3.* then, walk through our list of vertical edges and compare the coordinates of the starting and ending vertex of each edge to determine if it is a left edge. If so, we add it to a list. *O(n)* time.

`32:T5ed,slide`## The we find each vertex's right neighbor (ρ).
This the ρ that we saw earlier in our visual walkthrough.
The right neighbor of vertex *v*, is the closest vertex to the right of *v* that is also visible from *v*.

We find this by: >*1.* ordering the list of vertices by x-coordinate. We can use y-coordinate to break ties. *O(n log n)* time.

>*2.* starting at the fartest left vertex and add it to a holding list.

>>*2a* .Move to the next left vertex, if this vertex is not connected via a vertical/slanted edge to the first vertex (which is now in the holding list), then the first vertex's right neighbor is this vertex. Remove the first vertex from the holding list and add the new vertex to the holding list.

>> *2b*. If this vertex is connected to the first vertex via a vertical/slanted edge, check if that connecting edge is a left edge or a right edge.
>>> *2b_1*. If it's a left edge, don't assign any right neighbors, just add the new vertex to the holding list.

>>> *2b_2*.If it's a right edge, mark the vertex in holding list as having no right neighbor, add the new vertex to the holding list.

______________ Repeat with all vertices. *O(n log n)* time. `33:T95f,function polygon_cleaned(poli){ //for now we'll only handle 26 different vertices. We will tie each one to a letter in the string 'x' below. var x="abcdefghijklmnopqrstuvwxyz" //make the dictionary we will populate var retval = {} //for every vertex in the input list 'poli' for(var i = 0; i < poli.length; i++){ //set the key to be a the next letter in our string 'x', the x-coordinate to be the input x-coordinate, and the y-coordinate to be 500 minus the y-input rounded to the nearest whole number. retval[x[i]] = [{"x": poli[i][0], "y": 500-Math.round(poli[i][1])}][0] //We subtract the y-input from 500 because our plotting package, d3.js, assigns the top-left coordinate to the origin, and we want our origin to be at the bottom-left, as it typically is in geometry. } //if we think our input's first and second vertex are trying to form a horizontal edge. We can now walk around the polygon and alternate assigning horizontal and vertical edges 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]} } } //otherwise our input's first and second vertex are connected by a vertical edge.e can now walk around the polygon and alternate assigning horizontal and vertical edges 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]} } return retval }34:T63d,function graph_points(points_list, h, w){ const svg = d3.create('svg') // .attr('width', visWidth + margin_figure.left + margin_figure.right) // .attr('height', visHeight + margin_figure.top + margin_figure.bottom); .attr('width', w) .attr('height', h) svg.append('rect') .attr("width", w) .attr("height", h) .attr("fill", "white") var poly = points_list var xx =[] var yy =[] for(var i = 0; i < points_list.length; i++){ xx.push(points_list[i].x) yy.push(points_list[i].y) } var maxx = Math.max.apply(null, xx) var minx = Math.min.apply(null, xx) var maxy = Math.max.apply(null, yy) var miny = Math.min.apply(null, yy) var x = d3.scaleLinear().range([50, w-100]); var y = d3.scaleLinear().range([h-100, 50]); x.domain([minx, maxx]); y.domain([miny, maxy]); svg.selectAll("polygon") .data([poly]) .enter().append("polygon") .attr("fill", "none") .attr("stroke", "black") .attr("points",function(d) { return d.map(function(d) { return [x(d.x),y(d.y)].join(","); }).join(" "); }); svg.selectAll('circle') .data(poly) .join('circle') .attr('cy',d => y(d.y)) .attr('cx', d => x(d.x)) .attr('r', 4) .attr('fill', 'darkgrey') svg.selectAll("text") .data(poly) .join("text") .attr("dy", "1.2em") .attr("dx", "0.3em") .attr("x", d => x(d.x)) .attr("y", d => y(d.y)) .attr("font-size", "13") .attr("fill", "black") .text(d => d.name); return svg.node(); }35:T2da2,function graph_w_3(points_list, num_left, num_step, h, w){ if(isP_Rectilinear(input_dict) == "good"){ var answ = quad_part(make_left_edge_list(input_dict_wrn, find_v_edges(input_list)), input_dict_wrn) var lefts = [] var rights = [] for(var i = 0; i < answ.length; i++){ lefts.push(answ[i][0]+answ[i][1]) rights.push(answ[i][2]+answ[i][3]) // if((input_dict[answ[i][0]].x < input_dict[answ[i][1]].x && input_dict[answ[i][0]].y < input_dict[answ[i][1]].y) || check_if_left_edge(input_dict, answ[i][0]+answ[i][1])){ // lefts.push(answ[i][0]+answ[i][1]) // rights.push(answ[i][2]+answ[i][3]) // } // if((input_dict[answ[i][1]].x < input_dict[answ[i][2]].x && input_dict[answ[i][1]].y < input_dict[answ[i][2]].y)|| check_if_left_edge(input_dict, answ[i][1]+answ[i][2])){ // lefts.push(answ[i][1]+answ[i][2]) // rights.push(answ[i][3]+answ[i][0]) // } // if((input_dict[answ[i][2]].x < input_dict[answ[i][3]].x && input_dict[answ[i][2]].y < input_dict[answ[i][3]].y)|| check_if_left_edge(input_dict, answ[i][2]+answ[i][3])){ // lefts.push(answ[i][2]+answ[i][3]) // rights.push(answ[i][0]+answ[i][1]) // } // if((input_dict[answ[i][3]].x < input_dict[answ[i][0]].x && input_dict[answ[i][3]].y < input_dict[answ[i][0]].y)|| check_if_left_edge(input_dict, answ[i][3]+answ[i][0])){ // lefts.push(answ[i][3]+answ[i][0]) // rights.push(answ[i][1]+answ[i][2]) // } } // return [lefts, rights] var to_highlight_l = lefts[num_left] var to_highlight_r = rights[num_left] if(input_dict[to_highlight_l[0]].x == input_dict[to_highlight_l[1]].x){ var alpha = (input_dict[to_highlight_l[1]].y > input_dict[to_highlight_l[0]].y) ? [input_dict[to_highlight_l[0]].x, input_dict[to_highlight_l[0]].y, to_highlight_l[0]] : [input_dict[to_highlight_l[1]].x, input_dict[to_highlight_l[1]].y, to_highlight_l[1]] } else if(input_dict[to_highlight_l[0]].x > input_dict[to_highlight_l[1]].x){ var alpha = [input_dict[to_highlight_l[0]].x, input_dict[to_highlight_l[0]].y, to_highlight_l[0]] } else{ var alpha = [input_dict[to_highlight_l[1]].x, input_dict[to_highlight_l[1]].y, to_highlight_l[1]] } var rho = [input_dict[input_dict_wrn[alpha[2]].rn].x, input_dict[input_dict_wrn[alpha[2]].rn].y, input_dict_wrn[alpha[2]].rn] // var rho = (Math.abs(input_dict[to_highlight_r[0]].x - alpha[0]) < Math.abs(input_dict[to_highlight_r[1]].x - alpha[0])) ? [input_dict[to_highlight_r[0]].x, input_dict[to_highlight_r[0]].y, to_highlight_r[0]] : [input_dict[to_highlight_r[1]].x, input_dict[to_highlight_r[1]].y, to_highlight_r[1]] var alpha_v = (alpha[2] == to_highlight_l[0]) ? [input_dict[to_highlight_l[1]].x, input_dict[to_highlight_l[1]].y, to_highlight_l[1]] : [input_dict[to_highlight_l[0]].x, input_dict[to_highlight_l[0]].y, to_highlight_l[0]] var rho_v = (rho[2] == to_highlight_r[0]) ? [input_dict[to_highlight_r[1]].x, input_dict[to_highlight_r[1]].y, to_highlight_r[1]] : [input_dict[to_highlight_r[0]].x, input_dict[to_highlight_r[0]].y, to_highlight_r[0]] const svg = d3.create('svg') // .attr('width', visWidth + margin_figure.left + margin_figure.right) // .attr('height', visHeight + margin_figure.top + margin_figure.bottom); .attr('width', w) .attr('height', h) svg.append('rect') .attr("width", w) .attr("height", h) .attr("fill", "white") var poly = points_list var xx =[] var yy =[] for(var i = 0; i < points_list.length; i++){ xx.push(points_list[i].x) yy.push(points_list[i].y) } var maxx = Math.max.apply(null, xx) var minx = Math.min.apply(null, xx) var maxy = Math.max.apply(null, yy) var miny = Math.min.apply(null, yy) var x = d3.scaleLinear().range([50, w-100]); var y = d3.scaleLinear().range([h-100, 50]); x.domain([minx, maxx]); y.domain([miny, maxy]); svg.selectAll("polygon") .data([poly]) .enter().append("polygon") .attr("fill", "none") .attr("stroke", "black") .attr("points",function(d) { return d.map(function(d) { return [x(d.x),y(d.y)].join(","); }).join(" "); }); svg.selectAll('circle') .data(poly) .join('circle') .attr('cy',d => y(d.y)) .attr('cx', d => x(d.x)) .attr('r', 4) .attr('fill', 'darkgrey') svg.selectAll("text") .data(poly) .join("text") .attr("dy", "1.2em") .attr("dx", "0.3em") .attr("x", d => x(d.x)) .attr("y", d => y(d.y)) .attr("font-size", "13") .attr("fill", "black") .text(d => d.name); svg.append("line") .attr("x1", x(input_dict[to_highlight_l[0]].x)) .attr("y1", y(input_dict[to_highlight_l[0]].y)) .attr("x2", x(input_dict[to_highlight_l[1]].x)) .attr("y2", y(input_dict[to_highlight_l[1]].y)) .attr("stroke", "red") .attr("stroke-width", 3) if(num_step > 0 && num_step < 5){ svg.append("circle") .attr("cx", x(alpha[0])) .attr("cy", y(alpha[1])) .attr("r", 10) .attr("stroke", "red") .attr("fill", "none") .attr("stroke-width", 3) svg.append("text") .attr("x", x(alpha[0] -10)) .attr("y", y(alpha[1] - 12)) .attr("fill", "red") .attr("stroke-width", 2) .text("α") } if(num_step > 1 && num_step < 5){ svg.append("circle") .attr("cx", x(rho[0])) .attr("cy", y(rho[1])) .attr("r", 10) .attr("stroke", "#2eaaec") .attr("fill", "none") .attr("stroke-width", 3) svg.append("text") .attr("x", x(rho[0] -10)) .attr("y", y(rho[1] - 12)) .attr("fill", "#2eaaec") .attr("stroke-width", 2) .text("ρ") } if(num_step > 2 && num_step < 5){ svg.append("circle") .attr("cx", x(alpha_v[0])) .attr("cy", y(alpha_v[1])) .attr("r", 10) .attr("stroke", "red") .attr("fill", "none") .attr("stroke-width", 3) svg.append("text") .attr("x", x(alpha_v[0] -22)) .attr("y", y(alpha_v[1] - 12)) .attr("fill", "red") .attr("stroke-width", 2) .text("α_v") } if(num_step > 3 && num_step < 5){ svg.append("circle") .attr("cx", x(rho_v[0])) .attr("cy", y(rho_v[1])) .attr("r", 10) .attr("stroke", "#2eaaec") .attr("fill", "none") .attr("stroke-width", 3) svg.append("text") .attr("x", x(rho_v[0] -22)) .attr("y", y(rho_v[1] - 12)) .attr("fill", "#2eaaec") .attr("stroke-width", 2) .text("ρ_v") } if(num_step < 0){ svg.append("line") .attr("x1", x(input_dict[answ[num_left][0]].x)) .attr("y1", y(input_dict[answ[num_left][0]].y)) .attr("x2", x(input_dict[answ[num_left][1]].x)) .attr("y2", y(input_dict[answ[num_left][1]].y)) .attr("stroke", "#ff4088") .attr("stroke-width", 3) svg.append("line") .attr("x1", x(input_dict[answ[num_left][1]].x)) .attr("y1", y(input_dict[answ[num_left][1]].y)) .attr("x2", x(input_dict[answ[num_left][2]].x)) .attr("y2", y(input_dict[answ[num_left][2]].y)) .attr("stroke", "#ff4088") .attr("stroke-width", 3) svg.append("line") .attr("x1", x(input_dict[answ[num_left][2]].x)) .attr("y1", y(input_dict[answ[num_left][2]].y)) .attr("x2", x(input_dict[answ[num_left][3]].x)) .attr("y2", y(input_dict[answ[num_left][3]].y)) .attr("stroke", "#ff4088") .attr("stroke-width", 3) svg.append("line") .attr("x1", x(input_dict[answ[num_left][3]].x)) .attr("y1", y(input_dict[answ[num_left][3]].y)) .attr("x2", x(input_dict[answ[num_left][0]].x)) .attr("y2", y(input_dict[answ[num_left][0]].y)) .attr("stroke", "#ff4088") .attr("stroke-width", 3) } if(num_step < -1){ svg.append("line") .attr("x1", x(input_dict[answ[num_left][0]].x)) .attr("y1", y(input_dict[answ[num_left][0]].y)) .attr("x2", x(input_dict[answ[num_left][1]].x)) .attr("y2", y(input_dict[answ[num_left][1]].y)) .attr("stroke", "#ffbad4") .attr("stroke-width", 3) svg.append("line") .attr("x1", x(input_dict[answ[num_left][1]].x)) .attr("y1", y(input_dict[answ[num_left][1]].y)) .attr("x2", x(input_dict[answ[num_left][2]].x)) .attr("y2", y(input_dict[answ[num_left][2]].y)) .attr("stroke", (lefts.includes(answ[num_left][1]+answ[num_left][2]) || lefts.includes(answ[num_left][2]+answ[num_left][1]))? "#4ccf05" : "#ffbad4") .attr("stroke-width", 3) svg.append("line") .attr("x1", x(input_dict[answ[num_left][2]].x)) .attr("y1", y(input_dict[answ[num_left][2]].y)) .attr("x2", x(input_dict[answ[num_left][3]].x)) .attr("y2", y(input_dict[answ[num_left][3]].y)) .attr("stroke", "#ffbad4") .attr("stroke-width", 3) svg.append("line") .attr("x1", x(input_dict[answ[num_left][3]].x)) .attr("y1", y(input_dict[answ[num_left][3]].y)) .attr("x2", x(input_dict[answ[num_left][0]].x)) .attr("y2", y(input_dict[answ[num_left][0]].y)) .attr("stroke", (lefts.includes(answ[num_left][3]+answ[num_left][0]) || lefts.includes(answ[num_left][0]+answ[num_left][3]))? "#4ccf05" : "#ffbad4") .attr("stroke-width", 3) if(lefts.includes(answ[num_left][1]+answ[num_left][2]) || lefts.includes(answ[num_left][2]+answ[num_left][1])){ svg.append("text") .attr("x", x(input_dict[answ[num_left][1]].x +20)) .attr("y", y(input_dict[answ[num_left][1]].y +10)) .attr("fill", "#4ccf05") .text("New left edge!") } if(lefts.includes(answ[num_left][3]+answ[num_left][0]) || lefts.includes(answ[num_left][0]+answ[num_left][3])){ svg.append("text") .attr("x", x(input_dict[answ[num_left][3]].x +20)) .attr("y", y(input_dict[answ[num_left][3]].y +10)) .attr("fill", "#4ccf05") .text("New left edge!") } } if(num_step == 100){ for(var f = 0; f < answ.length; f++){ svg.append("line") .attr("x1", x(input_dict[answ[f][0]].x)) .attr("y1", y(input_dict[answ[f][0]].y)) .attr("x2", x(input_dict[answ[f][1]].x)) .attr("y2", y(input_dict[answ[f][1]].y)) .attr("stroke", "#ff9e00") .attr("stroke-width", 3) svg.append("line") .attr("x1", x(input_dict[answ[f][1]].x)) .attr("y1", y(input_dict[answ[f][1]].y)) .attr("x2", x(input_dict[answ[f][2]].x)) .attr("y2", y(input_dict[answ[f][2]].y)) .attr("stroke", "#ff9e00") .attr("stroke-width", 3) svg.append("line") .attr("x1", x(input_dict[answ[f][2]].x)) .attr("y1", y(input_dict[answ[f][2]].y)) .attr("x2", x(input_dict[answ[f][3]].x)) .attr("y2", y(input_dict[answ[f][3]].y)) .attr("stroke", "#ff9e00") .attr("stroke-width", 3) svg.append("line") .attr("x1", x(input_dict[answ[f][3]].x)) .attr("y1", y(input_dict[answ[f][3]].y)) .attr("x2", x(input_dict[answ[f][0]].x)) .attr("y2", y(input_dict[answ[f][0]].y)) .attr("stroke", "#ff9e00") .attr("stroke-width", 3) } } return svg.node(); } }36:T964,function graph_w_leftedges(points_list, h, w){ if(isP_Rectilinear(input_dict) == "good"){ var lefts = make_left_edge_list(input_dict_wrn, find_v_edges(input_list)) var to_highlight = [] for(var l =0; l < lefts.length; l++){ to_highlight.push([{x: input_dict[lefts[l][0][0]].x, y:input_dict[lefts[l][0][0]].y}, {x: input_dict[lefts[l][0][1]].x, y: input_dict[lefts[l][0][1]].y}]) } const svg = d3.create('svg') // .attr('width', visWidth + margin_figure.left + margin_figure.right) // .attr('height', visHeight + margin_figure.top + margin_figure.bottom); .attr('width', w) .attr('height', h) svg.append('rect') .attr("width", w) .attr("height", h) .attr("fill", "white") var poly = points_list var xx =[] var yy =[] for(var i = 0; i < points_list.length; i++){ xx.push(points_list[i].x) yy.push(points_list[i].y) } var maxx = Math.max.apply(null, xx) var minx = Math.min.apply(null, xx) var maxy = Math.max.apply(null, yy) var miny = Math.min.apply(null, yy) var x = d3.scaleLinear().range([50, w-100]); var y = d3.scaleLinear().range([h-100, 50]); x.domain([minx, maxx]); y.domain([miny, maxy]); svg.selectAll("polygon") .data([poly]) .enter().append("polygon") .attr("fill", "none") .attr("stroke", "black") .attr("points",function(d) { return d.map(function(d) { return [x(d.x),y(d.y)].join(","); }).join(" "); }); svg.selectAll('circle') .data(poly) .join('circle') .attr('cy',d => y(d.y)) .attr('cx', d => x(d.x)) .attr('r', 4) .attr('fill', 'darkgrey') svg.selectAll("text") .data(poly) .join("text") .attr("dy", "1.2em") .attr("dx", "0.3em") .attr("x", d => x(d.x)) .attr("y", d => y(d.y)) .attr("font-size", "13") .attr("fill", "black") .text(d => d.name); svg.selectAll("line") .data(to_highlight) .join("line") .attr("x1", d => x(d[0].x)) .attr("y1", d => y(d[0].y)) .attr("x2", d => x(d[1].x)) .attr("y2", d => y(d[1].y)) .attr("stroke", "red") .attr("stroke-width", 3) return svg.node(); } }37:T639,function find_r_neighbor(full_dict, olist) { var vertices = [] var holding = [olist[0]] var retval = {} var curr for(var i = 1; i < olist.length-1; i++){ curr = olist[i] var l = holding.length // retval["h"+i] = [Object.assign({}, holding), curr] for(var k = 0; k < l; k++){ if(full_dict[curr].v_edge != holding[k]){ if(full_dict[full_dict[holding[k]].v_edge].x == full_dict[holding[k]].x && full_dict[holding[k]].x > full_dict[full_dict[holding[k]].h_edge].x && !check_if_left_edge(full_dict, holding[k]+ full_dict[holding[k]].v_edge)){ retval[holding[k]] = "none" } else if(full_dict[curr].x == full_dict[olist[i+1]].x){ retval[holding[k]] = Math.abs(full_dict[curr].y - full_dict[holding[k]].y) < Math.abs(full_dict[olist[i+1]].y - full_dict[holding[k]].y) ? curr : olist[i+1] } else{ retval[holding[k]] = curr } } else{ //check if right or left edge if(check_if_left_edge(full_dict, curr+holding[k])){ } else if(full_dict[curr].x == full_dict[holding[k]].x && full_dict[holding[k]].x < full_dict[full_dict[holding[k]].h_edge].x){ } else{ retval[holding[k]]="none" } } } for(var k = 0; k < l; k++){ if(retval[holding[k]]){ holding[k] = "gone" } } holding = d3.filter(holding, d => d != "gone") holding.push(curr) } retval[olist[olist.length-1]] = "none" retval[olist[olist.length-2]] = "none" return retval } 38:T76b,function quad_part(lefts, full_list){ if(isP_Rectilinear(full_list) != "good"){ return "The input polygon is not pseudo-rectilinear" } var loc = [] var current_left var v var v_vedge var v_rn var v_rn_vedge var a var b var c var d var retval = [] //delete below block when ready to finalize for(var i = 0; i < lefts.length; i++){ loc.push(lefts[i]) } var loc_full = JSON.parse(JSON.stringify(full_list)); // // retval.push(JSON.parse(JSON.stringify(full_list))) while(loc.length > 0){ current_left = loc.pop()[0] v = (loc_full[current_left[0]].x >= loc_full[current_left[1]].x) ? current_left[0]: current_left[1] v_vedge = (v==current_left[0]) ? current_left[1]:current_left[0] v_rn = loc_full[v].rn v_rn_vedge = loc_full[v_rn].v_edge a = (loc_full[v].y < loc_full[v_vedge].y) ? v : v_vedge b = (a == v) ? v_vedge : v c = (loc_full[v_rn].y > loc_full[v_rn_vedge].y) ? v_rn : v_rn_vedge d = (c == v_rn) ? v_rn_vedge : v_rn if(loc_full[b].x != loc_full[c].x){ loc_full[b].v_edge = c loc_full[c].v_edge = b } if(loc_full[a].x != loc_full[d].x){ loc_full[a].v_edge = d loc_full[d].v_edge = a } retval.push([a,b,c,d]) if (loc_full[b].y > loc_full[c].y && loc_full[a].y < loc_full[d].y){ retval.push("bboo") retval.push([b, c]) retval.push([a, d]) if(loc_full[c].x < loc_full[d].x){ loc.push([b+c, -1]) loc.push([a+d, -1]) } else{ loc.push([a+d, -1]) loc.push([b+c, -1]) } } if(loc_full[b].y > loc_full[c].y){ // retval.push(["BIG B", b, c]) loc.push([b+c, -1]) } else if(loc_full[a].y < loc_full[d].y){ // retval.push(["BIG D", a, d]) loc.push([a+d, -1]) } else{ } } return retval }39:T658,keypresscontrol= { document.cells = document.getElementsByClassName("observablehq"); document.current=2; document.stopnumber = document.cells.length- 5 //keymap document.onkeyup = function(e) { console.log(e) ; if (e.which === 83){console.log('re -s- tart'); document.current=2 var elmnt = document.cells[document.current] elmnt.scrollIntoView(); } if (e.which === 32| e.which === 39| e.which === 40){console.log('space'); document.current+=1 if (document.current < (document.stopnumber)){ var elmnt=document.cells[document.current]; if (elmnt.innerHTML != '

'){ elmnt.scrollIntoView(); } else { document.stopnumber = document.current; } }else{document.current = document.stopnumber } } if (e.which === 38 | e.which === 37){console.log('back'); document.current-=1 if (document.current <2){document.current = 2} var elmnt = document.cells[document.current] elmnt.scrollIntoView(); } } }3a:T46a,slide_style = html``3b:T5e1,// html``3c:Te0b,p2 = { const scaleX = d3.scaleLinear().domain([0,310]).range([0,240]); const scaleY = d3.scaleLinear().domain([0,210]).range([30,300]); var poly = polygon_display_2 const svg = d3.create('svg') .attr('width', 600) .attr('height', 300) var r1 = svg.append("svg") .attr('y', 0) .attr('x', 0) .attr('width', 300) .attr('height', 300) r1.append("rect") .attr('y', 0) .attr('x', 10 ) .attr('width', '100%') .attr('height', '100%') .attr('fill', 'none') r1.append("text") .attr("x", "50%") .attr("y", "30") .text("Polygon") .attr("text-anchor", "middle") r1.selectAll("polygon") .data([poly]) .enter().append("polygon") .attr("points",function(d) { return d.map(function(d) { return [scaleX(d[0]),scaleY(d[1])].join(","); }).join(" "); }) .attr("fill", "none") .attr("stroke","black") .attr("stroke-width",2); var r2 = svg.append("svg") .attr('y', 0) .attr('x', 300) .attr('width', 300) .attr('height', 300) r2.append("rect") .attr('y', 0) .attr('x', 0) .attr('width', '100%') .attr('height', '100%') .attr('fill', 'none') r2.append("text") .attr("x", "60%") .attr("y", "30") .text("Quadrilateralized Polygon") .attr("text-anchor", "middle") r2.selectAll("polygon") .data([poly]) .enter().append("polygon") .attr("points",function(d) { return d.map(function(d) { return [scaleX(d[0]),scaleY(d[1])].join(","); }).join(" "); }) .attr("fill", "none") .attr("stroke","black") .attr("stroke-width",2); r2.append('line') .style("stroke", "red") .style("stroke-width", 2) .attr("x1", scaleX(35)) .attr("y1", scaleY(195)) .attr("x2", scaleX(40)) .attr("y2", scaleY(160)) r2.append('line') .style("stroke", "red") .style("stroke-width", 2) .attr("x1", scaleX(12)) .attr("y1", scaleY(121)) .attr("x2", scaleX(40)) .attr("y2", scaleY(160)); r2.append('line') .style("stroke", "red") .style("stroke-width", 2) .attr("x1", scaleX(112)) .attr("y1", scaleY(113)) .attr("x2", scaleX(36)) .attr("y2", scaleY(88)); r2.append('line') .style("stroke", "red") .style("stroke-width", 2) .attr("x1", scaleX(112)) .attr("y1", scaleY(113)) .attr("x2", scaleX(109)) .attr("y2", scaleY(33)); r2.append('line') .style("stroke", "red") .style("stroke-width", 2) .attr("x1", scaleX(112)) .attr("y1", scaleY(113)) .attr("x2", scaleX(168)) .attr("y2", scaleY(74)); r2.append('line') .style("stroke", "red") .style("stroke-width", 2) .attr("x1", scaleX(186)) .attr("y1", scaleY(138)) .attr("x2", scaleX(168)) .attr("y2", scaleY(74)); r2.append('line') .style("stroke", "red") .style("stroke-width", 2) .attr("x1", scaleX(186)) .attr("y1", scaleY(138)) .attr("x2", scaleX(275)) .attr("y2", scaleY(79)); r2.append('line') .style("stroke", "red") .style("stroke-width", 2) .attr("x1", scaleX(250)) .attr("y1", scaleY(150)) .attr("x2", scaleX(186)) .attr("y2", scaleY(204)); return svg.node() }3d:T86b,p1 ={ const scaleX = d3.scaleLinear().domain([0,310]).range([0,240]); const scaleY = d3.scaleLinear().domain([0,210]).range([30,300]); var poly = polygon_display_1 const svg = d3.create('svg') .attr('width', 600) .attr('height', 300) var r1 = svg.append("svg") .attr('y', 0) .attr('x', 0) .attr('width', 300) .attr('height', 300) r1.append("rect") .attr('y', 0) .attr('x', 10 ) .attr('width', '100%') .attr('height', '100%') .attr('fill', 'none') r1.append("text") .attr("x", "50%") .attr("y", "30") .text("Polygon") .attr("text-anchor", "middle") r1.selectAll("polygon") .data([poly]) .enter().append("polygon") .attr("points",function(d) { return d.map(function(d) { return [scaleX(d[0]),scaleY(d[1])].join(","); }).join(" "); }) .attr("fill", "none") .attr("stroke","black") .attr("stroke-width",2); var r2 = svg.append("svg") .attr('y', 0) .attr('x', 300) .attr('width', 300) .attr('height', 300) r2.append("rect") .attr('y', 0) .attr('x', 0) .attr('width', '100%') .attr('height', '100%') .attr('fill', 'none') r2.append("text") .attr("x", "60%") .attr("y", "30") .text("Quadrilateralized Polygon") .attr("text-anchor", "middle") r2.selectAll("polygon") .data([poly]) .enter().append("polygon") .attr("points",function(d) { return d.map(function(d) { return [scaleX(d[0]),scaleY(d[1])].join(","); }).join(" "); }) .attr("fill", "none") .attr("stroke","black") .attr("stroke-width",2); r2.append('line') .style("stroke", "red") .style("stroke-width", 2) .attr("x1", scaleX(211)) .attr("y1", scaleY(101)) .attr("x2", scaleX(281)) .attr("y2", scaleY(35)); return svg.node() }3e:[{"id":"981ce9693936ddc8d5ed95a02603cd25d0aa4099c9dafca50cd17ad7f551d7814560385f87af91e4cedd606dc9986af1e9a2d061fd6a8fcfc4b69bc45f27450b","href":"https://static.observableusercontent.com/files/981ce9693936ddc8d5ed95a02603cd25d0aa4099c9dafca50cd17ad7f551d7814560385f87af91e4cedd606dc9986af1e9a2d061fd6a8fcfc4b69bc45f27450b","name":"room-2.png","type":"image/png","lastModified":1620179217014.177,"size":85711},{"id":"a487cce393d2a7f974f7ccdf52ed1aa9f706c95637d400d7f089b2723691cc68c12f6b525533d99a252eecf39e1ff246e6b8bece1a7d57278217a04af832968b","href":"https://static.observableusercontent.com/files/a487cce393d2a7f974f7ccdf52ed1aa9f706c95637d400d7f089b2723691cc68c12f6b525533d99a252eecf39e1ff246e6b8bece1a7d57278217a04af832968b","name":"room-8.png","type":"image/png","lastModified":1620179853596.618,"size":101677},{"id":"763df2ddb4fbf6e544a2e87338272e058f0bcebe654bfa925ee3aea75b4a5d7b982b2fadd3a76deca22c3285ed2b4afdf3fd3c64d738c9e20f295b17378204d3","href":"https://static.observableusercontent.com/files/763df2ddb4fbf6e544a2e87338272e058f0bcebe654bfa925ee3aea75b4a5d7b982b2fadd3a76deca22c3285ed2b4afdf3fd3c64d738c9e20f295b17378204d3","name":"room-4.png","type":"image/png","lastModified":1620179458596.797,"size":92297},{"id":"b6de1bc8a4e61c458b352b4e9a13d9a77960f1de9b01bb4069907b9eb78983b9b31d35392ebb7b2d28780dd4de2cf3f784b5edbf053c85e3f93dfb26fe87703f","href":"https://static.observableusercontent.com/files/b6de1bc8a4e61c458b352b4e9a13d9a77960f1de9b01bb4069907b9eb78983b9b31d35392ebb7b2d28780dd4de2cf3f784b5edbf053c85e3f93dfb26fe87703f","name":"room-3.png","type":"image/png","lastModified":1620179365865.357,"size":67992},{"id":"91a391fb7b6935bb9b3b144457a1d80500cb912e5f1a28fb0ec2b5512b9557ec338433e1e208c19fc62cc13fccd9611ec0d81e00bbab5b7081cf33f2310d911c","href":"https://static.observableusercontent.com/files/91a391fb7b6935bb9b3b144457a1d80500cb912e5f1a28fb0ec2b5512b9557ec338433e1e208c19fc62cc13fccd9611ec0d81e00bbab5b7081cf33f2310d911c","name":"room-10.png","type":"image/png","lastModified":1620259508625.195,"size":40407},{"id":"6f3be3659be63212a0581e02eb151a1da43712713199a3f4fecdfea6b12cebf635c25e5db06ccf6693fd690de2951063e2cf120477f6ff2c0e014602f10a01b3","href":"https://static.observableusercontent.com/files/6f3be3659be63212a0581e02eb151a1da43712713199a3f4fecdfea6b12cebf635c25e5db06ccf6693fd690de2951063e2cf120477f6ff2c0e014602f10a01b3","name":"room-9.png","type":"image/png","lastModified":1620259143935.042,"size":42717},{"id":"6ec2b170d3121a348217a79c21a798514d369fb214b649171a10f23a806f73f0d105812a2278bf5831ab7bf6cf9576a4e20b74d9ffcead266a46c1a95b647c77","href":"https://static.observableusercontent.com/files/6ec2b170d3121a348217a79c21a798514d369fb214b649171a10f23a806f73f0d105812a2278bf5831ab7bf6cf9576a4e20b74d9ffcead266a46c1a95b647c77","name":"room-11.png","type":"image/png","lastModified":1620443437955.099,"size":117622},{"id":"981ce9693936ddc8d5ed95a02603cd25d0aa4099c9dafca50cd17ad7f551d7814560385f87af91e4cedd606dc9986af1e9a2d061fd6a8fcfc4b69bc45f27450b","href":"https://static.observableusercontent.com/files/981ce9693936ddc8d5ed95a02603cd25d0aa4099c9dafca50cd17ad7f551d7814560385f87af91e4cedd606dc9986af1e9a2d061fd6a8fcfc4b69bc45f27450b","name":"room-2@1.png","type":"image/png","lastModified":1620629672257.806,"size":85711},{"id":"e90d17b3be1ac24f3bd99f0f441b6c20a871c90a63b80711eac8938ba0ddbe2b9ce3bd4b12aa9d6e2d2555429cbe231718cca5294975c74286f5b501fbc673c3","href":"https://static.observableusercontent.com/files/e90d17b3be1ac24f3bd99f0f441b6c20a871c90a63b80711eac8938ba0ddbe2b9ce3bd4b12aa9d6e2d2555429cbe231718cca5294975c74286f5b501fbc673c3","name":"arrow.png","type":"image/png","lastModified":1620629616045.564,"size":17007},{"id":"d23e3d974d58ef601a5a96a821c06f18034c3c045e662bc1e9365373460b9176b1c0984d4a9502819a54b8c068a9f098e28fb6daf77f7cda5a185cb6d91d5aec","href":"https://static.observableusercontent.com/files/d23e3d974d58ef601a5a96a821c06f18034c3c045e662bc1e9365373460b9176b1c0984d4a9502819a54b8c068a9f098e28fb6daf77f7cda5a185cb6d91d5aec","name":"monotone@2.gif","type":"image/gif","lastModified":1620670936681.808,"size":192580},{"id":"dbe690726a97d7fbbcdf76941430c5a04b2a568c06f76712dd470f988dd68abb609fc79406edf860e6abe5faf420fff746e83d1b03b0153cd141a711cbbbe216","href":"https://static.observableusercontent.com/files/dbe690726a97d7fbbcdf76941430c5a04b2a568c06f76712dd470f988dd68abb609fc79406edf860e6abe5faf420fff746e83d1b03b0153cd141a711cbbbe216","name":"sorting.gif","type":"image/gif","lastModified":1620668384746.931,"size":143025},{"id":"a946d3a4e514753e1b60854c3a9192f777f5421505d5f27f6fc3a71023e3a7975c9c2c508ab12bb1c7a205f38663243c47bd102db7c62853cd513444d67556a3","href":"https://static.observableusercontent.com/files/a946d3a4e514753e1b60854c3a9192f777f5421505d5f27f6fc3a71023e3a7975c9c2c508ab12bb1c7a205f38663243c47bd102db7c62853cd513444d67556a3","name":"room-1@2.png","type":"image/png","lastModified":1620629448888.169,"size":60230},{"id":"a946d3a4e514753e1b60854c3a9192f777f5421505d5f27f6fc3a71023e3a7975c9c2c508ab12bb1c7a205f38663243c47bd102db7c62853cd513444d67556a3","href":"https://static.observableusercontent.com/files/a946d3a4e514753e1b60854c3a9192f777f5421505d5f27f6fc3a71023e3a7975c9c2c508ab12bb1c7a205f38663243c47bd102db7c62853cd513444d67556a3","name":"room-1.png","type":"image/png","lastModified":1620179034867.098,"size":60230},{"id":"36f44426a9845eadcffed4fed6c7ed79c6ab6ef9ce0c6cf59fc638b8a841fb5c220d907d9cfe33f6ddc819de857ee551dde53880051343bca7a78cefbee1accc","href":"https://static.observableusercontent.com/files/36f44426a9845eadcffed4fed6c7ed79c6ab6ef9ce0c6cf59fc638b8a841fb5c220d907d9cfe33f6ddc819de857ee551dde53880051343bca7a78cefbee1accc","name":"rn@1.gif","type":"image/gif","lastModified":1620671107402.01,"size":1230186},{"id":"8dca1c055861f56ba3f4864190d4acba629b447ee4055257b642d58d09d50e6c8a66a1fae6ba618e03cc58a78fb05de83bd6204bcd4a96309fb05f3f6a7bb3b5","href":"https://static.observableusercontent.com/files/8dca1c055861f56ba3f4864190d4acba629b447ee4055257b642d58d09d50e6c8a66a1fae6ba618e03cc58a78fb05de83bd6204bcd4a96309fb05f3f6a7bb3b5","name":"check-overlap.gif","type":"image/gif","lastModified":1620660991704.547,"size":66252},{"id":"2b0d5847eab5b0a1e69495e5b0fe8d8954f9558fa4663c1945b1f8b7e42baa72dd17741c3642f5c237b6224dbbf4a1752538671d72cc70fc78b24cfe68a0c40b","href":"https://static.observableusercontent.com/files/2b0d5847eab5b0a1e69495e5b0fe8d8954f9558fa4663c1945b1f8b7e42baa72dd17741c3642f5c237b6224dbbf4a1752538671d72cc70fc78b24cfe68a0c40b","name":"2.jpg","type":"image/jpeg","lastModified":1620663814614.827,"size":35623},{"id":"d01e806caf8df4f2a41820997b51c0a40808ffe9de479c5723cddb52c533876fc04425b769c6939614502b53936fb30f44eb7621f14ad014373f7c00908c2372","href":"https://static.observableusercontent.com/files/d01e806caf8df4f2a41820997b51c0a40808ffe9de479c5723cddb52c533876fc04425b769c6939614502b53936fb30f44eb7621f14ad014373f7c00908c2372","name":"left-edges@1.gif","type":"image/gif","lastModified":1620663920291.971,"size":232744}] 2f:{"title":"Dr. Lubiw's quadrilateralization algorithm","cells":[{"id":0,"value":"md`# Dr. Lubiw's quadrilateralization algorithm`","pinned":false,"hidden":false,"mode":"ojs"},{"id":27,"value":"md`Slide formatted adapted from: https://observablehq.com/@wolfiex/a-presentation-framework-built-on-a-observablehq-notebook`","pinned":false,"hidden":false,"mode":"ojs"},{"id":22,"value":"slide`# Quadrilateralizing pseudo-rectilinear polygons\n
\n## An algorithm by Dr. Anna Lubiw\nhttps://doi.org/10.1145/323233.323247 \n

\n*Implemented and Visualized by Racquel Fygenson*\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":169,"value":"slide`## What is quadrilateralization?\n
\nQuadrilateralization is the splitting of any polygon into 4-sided, straight-edged shapes (i.e. quadrilaterals).\n
\n${p1}`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":199,"value":"slide`## What is quadrilateralization?\n
\nQuadrilateralization is the splitting of any polygon into 4-sided, straight-edged shapes (i.e. quadrilaterals).\n
\n${p2}`","pinned":false,"hidden":false,"mode":"ojs"},{"id":205,"value":"slide`## What is a pseudo-rectilinear polygon? \nA psuedo-rectilinear polygon is any polygon that adheres to the following constraints:\n1. an even number of edges\n2. alternating horizontal and vertical or tilted edges\n3. no vertices that are in the shadow of a tilted edge\n4. all interior angles ≤ 270°\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":212,"value":"slide`## What is a pseudo-rectilinear polygon? \n

\n\nAn easy way to think about the constraints of a pseudo-rectilinear shape is to imagine a
🏠 room 🏠 that can only be buit with horizontal and vertical or slanted walls.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":223,"value":"slide`

\n

\nWe can have rooms that are simply one retangle (and therefore already quadrilateralized!)`","pinned":false,"hidden":false,"mode":"ojs"},{"id":236,"value":"slide`

\n

\nOr rooms that are L-shaped, or have alcoves or closets.`","pinned":false,"hidden":false,"mode":"ojs"},{"id":239,"value":"slide`These rooms are properly rectilinear, but we're not *that* strict.\n\nWe're here for a fun (pseudo-rectilinear) time. So we can also replace any of the vertical walls in our rectilinear rooms with slanted walls if we want 💅 \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":241,"value":"slide`These rooms are properly rectilinear, but we're not *that* strict.\n\nWe're here for a fun (pseudo-rectilinear) time. So we can also replace any of the vertical walls in our rectilinear rooms with slanted walls if we want 💅 \n

\n

💥 Bada-bing 💥\n

\n\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":250,"value":"slide`These rooms are properly rectilinear, but we're not *that* strict.\n\nWe're here for a fun (pseudo-rectilinear) time. So we can also replace any of the vertical walls in our rectilinear rooms with slanted walls if we want 💅 \n

\n

💥 Bada-boom 💥\n

\n\n\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":252,"value":"slide`That checks off the first 2 constraints\n > ✅ an even number of edges
\n > ✅ alternating horizontal and vertical or tilted edges\n\nbut we need to make sure we don't go too crazy. The other constraints for pseudo-rectilinearlity are:\n \n > 🔸 no vertices that are in the shadow of a tilted edge 🔸

\n >🔸 all interior angles ≤ 270°🔸\n\n\nThis means that only one vertical or slanted edge can occupy any given x-coordinates.\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":254,"value":"slide`

🔸 no vertices that are in the shadow of a tilted edge 🔸 \n
\n
\n
\n

\n \n`\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":288,"value":"slide`

🔸 all interior angles ≤ 270° 🔸 \n
\n
\n
\n

\n \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":291,"value":"slide`### Additional constraints:\n
\nThose are all the constraints for pseudo-rectinlinearity. For quadrilateralizing using Lubiw's Algorithm, we will impose one last constraint:

\n

\n 🔸 the input polygon must be monotone with respect to the x-axis 🔸
\n

\n
\nTo be x-monotone means that if we were to draw any line so that it was orthogonal to the x-axis, this line would only intersect the polygon once.\n

\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":315,"value":"slide`# Now on to Lubiw's Algorithm`","pinned":false,"hidden":false,"mode":"ojs"},{"id":323,"value":"slide` **Input:** a pseudo-rectilinear polygon as a list of (x,y) vertices in the clockwise direction. \n

**Output:** a list of quadrilaterals, each specified by 4 (x,y) coordinate in clockwise order.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":319,"value":"slide` **Input:** a pseudo-rectilinear polygon as a list of (x,y) vertices in the clockwise direction. \n

\n${graph_points(polygon_for_drawing(polygon_cleaned(input_vertices)), 400, 500)}

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":393,"value":"slide`In practice, our algorithm is easy to comprehend. \n ### There are 4 main steps:\n 1. We will check that the polygon is pseudo-rectilinear by making sure it adheres the constraints previously discussed.\n\n

\n${graph_points(polygon_for_drawing(polygon_cleaned(input_vertices)), 250, 330)}

\n\n > ${(isP_Rectilinear(input_dict).includes(\"even\")) ? \"❌\": \"✅\"} An even number of edges\n\n > ${(isP_Rectilinear(input_dict).includes(\"alternating\")) ? \"❌\": \"✅\"} Alternating horizontal and vertical/slanted edges\n\n > ${(isP_Rectilinear(input_dict).includes(\"overlap\")) ? \"❌\": \"✅\"} No vertical/slanted edges in the shadow of other vertical/slanted edges\n\n > ${(isP_Rectilinear(input_dict).includes(\"monotone\")) ? \"❌\": \"✅\"} Monotone with respect to the x-axis (and therefor no interior angles > 270°)\n\n\n \n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":456,"value":"slide`### There are 4 main steps:\n *2*. Find all of the polygon's left edges.

\n

\n${graph_w_leftedges(input_list, 400, 500)}

\n 🔅 A left edge is a vertical or slanted edge that lies to the left of the polygon, such that the interior of the polygon is to right of the edge.\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":560,"value":"slide`### There are 4 main steps:\n
\n*3*. Start with the polygon's right-most left edge.

\n

\n${graph_w_3(input_list, 0, 0, 400, 500)}

\n find it's right-most vertex (if the line is vertical, choose the bottom-most vertex). We'll call this α.
\n look for the closest vertex in the polygon that is to the right of α and still \"visible\" from α. Call this vertex ρ.
\n (\"visible\" means that a straight line from α to this vertex stays inside the polygon.)
\n find the vertex that is connected to α by a vetical edge. Call it α_v.
\n find the vertex that is connected to ρ by a vetical edge. Call it ρ_v.
\n α, ρ, α_v, and ρ_v form one of our output quadrilaterals!
\n f this output quadrilateral creates any new left edge (see picture), add these new left edges to our list of left edges.

\n
\n\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":662,"value":"slide`### There are 4 main steps:\n
\n*3*. Start with the polygon's right-most left edge.

\n

\n${graph_w_3(input_list, 0, 1, 400, 500)}

\n\n ▪️ Find it's right-most vertex (if the line is vertical, choose the bottom-most vertex). Call this α.
\n

\n look for the closest vertex in the polygon that is to the right of α and still \"visible\" from α. Call this vertex ρ.
\n (\"visible\" means that a straight line from α to this vertex stays inside the polygon.)
\n find the vertex that is connected to α by a vetical edge. Call it α_v.
\n find the vertex that is connected to ρ by a vetical edge. Call it ρ_v.
\n α, ρ, α_v, and ρ_v form one of our output quadrilaterals!
\n f this output quadrilateral creates any new left edge (see picture), add these new left edges to our list of left edges.

\n
\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":679,"value":"slide`### There are 4 main steps:\n
\n*3*. Start with the polygon's right-most left edge.

\n

\n${graph_w_3(input_list, 0, 2, 400, 500)}

\n find the vertex that is connected to α by a vetical edge. Call it α_v.
\n find the vertex that is connected to ρ by a vetical edge. Call it ρ_v.
\n α, ρ, α_v, and ρ_v form one of our output quadrilaterals!
\n f this output quadrilateral creates any new left edge (see picture), add these new left edges to our list of left edges.

\n
\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":686,"value":"slide`### There are 4 main steps:\n
\n*3*. Start with the polygon's right-most left edge.

\n

\n${graph_w_3(input_list, 0, 3, 400, 500)}

\n find the vertex that is connected to ρ by a vetical edge. Call it ρ_v.
\n α, ρ, α_v, and ρ_v form one of our output quadrilaterals!
\n f this output quadrilateral creates any new left edge (see picture), add these new left edges to our list of left edges.

\n
\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":703,"value":"slide`### There are 4 main steps:\n
\n*3*. Start with the polygon's right-most left edge.

\n

\n${graph_w_3(input_list, 0, 4, 400, 500)}

\n α, ρ, α_v, and ρ_v form one of our output quadrilaterals!
\n f this output quadrilateral creates any new left edge (see picture), add these new left edges to our list of left edges.

\n
\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":707,"value":"slide`### There are 4 main steps:\n
\n*3*. Start with the polygon's right-most left edge.

\n

\n${graph_w_3(input_list, 0, -1, 400, 500)}

\n f this output quadrilateral creates any new left edge (see picture), add these new left edges to our list of left edges.

\n
\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":725,"value":"slide`### There are 4 main steps:\n
\n*3*. Start with the polygon's right-most left edge.

\n

\n${graph_w_3(input_list, 0, -2, 400, 500)}

\n\n ▪️ Find it's right-most vertex (if the line is vertical, choose the bottom-most vertex). Call this α.

\n ▪️ Find the closest vertex in the polygon that is to the right of α and still \"visible\" from α. Call this vertex ρ.
\n (\"visible\" means that a straight line from α to this vertex stays inside the polygon.)

\n ▪️ Find the vertex that is connected to α by a vetical edge. Call it α_v.

\n ▪️ Find the vertex that is connected to ρ by a vetical edge. Call it ρ_v.
\n
\n🌟 α, ρ, α_v, and ρ_v form one of our output quadrilaterals! 🌟
\n\n ▪️ Lastly, if this output quadrilateral creates any new left edges, add these new left edges to our list of left edges.\n
\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":877,"value":"slide`### There are 4 main steps:\n
\n*4*. Repeat the steps on the previous slide with all the the left edges.

\n

\n${graph_w_3(input_list, counter_q, counter, 400, 500)}

\n
\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1090,"value":"viewof counter = Button([\n [\"Next\", value => (value < 4 && value >=0) ? value + 1 : ((value == -1) ? -2 : ((value == -2) ? 0 :-1))],\n [\"Back\", value => (value <= 4 && value >0) ? value - 1 : ((value == -1) ? 4 : ((value == -2) ? -1 : -2))],\n [\"Show all\", value => 100]\n], {value: 0, label: \"Change Steps in the Subroutine\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1159,"value":"viewof counter_q = Button([\n [\"Next\", value => (value < main_loop(input_vertices).length -1) ? value+1 : 0],\n [\"Back\", value => (value > 0) ? value -1 : main_loop(input_vertices).length -1],\n], {value: 0, label: \"Changes Quadrilaterals\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1330,"value":"md`_________`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1270,"value":"md`The polygon you currently have as input evaluates to:`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1325,"value":"main_loop(input_vertices)","pinned":false,"hidden":false,"mode":"ojs"},{"id":1333,"value":"md`_________`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1256,"value":"viewof polygon = rectPolygonInput({\n title: \"Draw your own pseudo-rectilinear polygon\",\n description: \"This will return an array of points.
Clear the input by refreshing this cell.\"\n});","pinned":false,"hidden":false,"mode":"ojs"},{"id":1265,"value":"viewof submit = Button([\n [\"Start\", value => 1],\n [\"Stop\", value => 0],\n], {value: 0, label: \"Populate using above input?\"})","pinned":false,"hidden":false,"mode":"ojs"},{"id":1571,"value":"md`_____________`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1559,"value":"md`The above polygon input is adapted from:
https://observablehq.com/@harrystevens/polygon-input
and references functions in:
https://observablehq.com/@jashkenas/inputs`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1337,"value":"md`_________`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1372,"value":"slide`## How do we do this in practice?\n

\nWell the whole algorithm is implemented on this page, adapted slightly to work in JavaScript. Feel free to explore the different blocks of code at the bottom. 🔎\n\nBut I'll still walk you through the general concepts.🚶‍♀️🚶🏿🚶‍🚶🏾‍♀️🚶🏼\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1386,"value":"slide`### First we check that the input is pseudo-rectilinear.\n

\nWe do this by:\n >*1.* walking through the input, checking for an even number of edges. *O(n)* time.

\n >*2.* walking through the input, checking for alternating horizontal and vertical or slanted edges.\n

\n >*3.*\n

\n >*4.*\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1452,"value":"slide`### First we check that the input is pseudo-rectilinear.\n

\nWe do this by:\n >*3.* walking through the input, checking that all slanted/vertical lines don't overlap in x-coordinates. \n

\nWe can do this by first finding the x-coordinate intervals of these lines in *O(n)* time. Then sorting the intervals by left end-points in *O(n log n)* time. Finally walking through the sorted list of intervals and comparing each interval to the one right before it in *O(n)* time. Overall, this takes *O(n log n)* time.

\n

\n

\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1464,"value":"slide`### First we check that the input is pseudo-rectilinear.\n

\nWe do this by:\n >*4.* checking that the polygon is montone wrt the x-axis by walking along the polygon's vertices. \n

At each vertex we can check to make sure that it is not farther right than both the vertex before it and vertex after it. \n

Only one such vertex can exist, so if we count more than one we can stop and report it. This takes O(n) time.\n

\n\n`","pinned":false,"hidden":false,"mode":"ojs"},{"id":1401,"value":"$31","pinned":false,"hidden":false,"mode":"ojs"},{"id":1408,"value":"$32","pinned":false,"hidden":false,"mode":"ojs"},{"id":1424,"value":"slide`## Lastly, we start at the right-most left edge.\n
Then, we run through the sequence we covered in step 3 of the conceptual walkthrough:\n

\n > *1.* Look at the list of left-edge vertices. The right-most of these vertices (and bottom-most in the case of a tie) is α.\n

\n > *2.* Look up α's right neighbor in constant time. This vertex is ρ.\n

\n > *3.* Find α's and ρ's right neighbors in constant time. These four vertices make up one of our output quadrilaterals. \n

\n > *4.* Output this quadrilateral in clockwise order starting from the bottom-left vertex. This takes constant time.\n

\n > *5.* Check the new edges we've drawn with this quadrilateral and see if they are left-edges. This can be done in constant time using the method we used to find the list of left edges. If any are left edges, we add them to the end of the list of left edges.\n `","pinned":false,"hidden":false,"mode":"ojs"},{"id":1433,"value":"slide`## Run through this sequence with all the left edges in the list. \n
This takes *O(n)* time.` ","pinned":false,"hidden":false,"mode":"ojs"},{"id":1437,"value":"slide`## And then we're done! \n### And we've kept overall time complexity at *O(n log n)*`","pinned":false,"hidden":false,"mode":"ojs"},{"id":139,"value":"slide.end('this ends the presentation')","pinned":false,"hidden":false,"mode":"ojs"},{"id":342,"value":"input_dict = polygon_cleaned(input_vertices)","pinned":false,"hidden":false,"mode":"ojs"},{"id":38,"value":"$33","pinned":false,"hidden":false,"mode":"ojs"},{"id":1252,"value":"import {rectPolygonInput} from \"@racquellevia/rectilinear-polygon-input\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":93,"value":"$34","pinned":false,"hidden":false,"mode":"ojs"},{"id":834,"value":"$35","pinned":false,"hidden":false,"mode":"ojs"},{"id":467,"value":"$36","pinned":false,"hidden":false,"mode":"ojs"},{"id":35,"value":"input_vertices = {\n var defaultP = [[38, 88.39999389648438],\n [147, 88.39999389648438],\n [147, 142],\n [237, 142],\n [237, 59],\n [287, 59],\n [287, 180],\n [69, 180]]\n \n if (polygon.length > 0 && submit!=0){\n if(isP_Rectilinear(polygon_cleaned(polygon))){\n return polygon\n }\n else{\n return defaultP\n }}\n else{\n return defaultP\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":478,"value":"input_list = polygon_for_drawing(input_dict)","pinned":false,"hidden":false,"mode":"ojs"},{"id":82,"value":"function main_loop(input_v){\n\n \n var good = isP_Rectilinear(input_dict)\n if(good == \"good\"){\n var retval = quad_part(make_left_edge_list(input_dict_wrn, find_v_edges(input_list)), input_dict_wrn)\n \n return retval\n }\n else{\n return good\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":473,"value":"input_dict_wrn = {\n if(isP_Rectilinear(input_dict) == \"good\"){\n return add_r_neighbor(input_dict, find_r_neighbor(input_dict, find_order(input_dict)))\n }\n else{\n return \"invalid input\"\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":65,"value":"function isP_Rectilinear(points){\n\n var keys = Object.keys(points)\n\n if(points.length%2 == 1){\n return \"The input must have an even number of edges. Click 'Stop' below, correct the input, then click 'Start'.\"\n }\n\n for(var i = 0; i < keys.length; i++){\n if(points[points[keys[i]].h_edge].y != points[keys[i]].y){\n return \"The input must have alternating horizontal and vertical/slanted edges. Click 'Stop' below, correct the input, then click 'Start'.\"\n }\n }\n\n if(!isMonotone_dict(points)){\n return \"The input must be monotone with respect to the x-axis. Click 'Stop' below, correct the input, then click 'Start'.\"\n }\n\n if(check_interval_overlap(find_intervals(find_v_edges(polygon_for_drawing(points)), points)) > 0){\n return \"There is \" + check_interval_overlap(find_intervals(find_v_edges(polygon_for_drawing(points)), points)) + \" overlap in vertical/slanted edges. Click 'Stop' below, correct the input, then click 'Start'.\"\n }\n\n return \"good\"\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":41,"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"},{"id":70,"value":"function find_intervals(list_edges, full_dict){\n var retval = []\n \n for(var i = 0; i < list_edges.length; i++){\n retval.push([Math.min(full_dict[list_edges[i][0]].x, full_dict[list_edges[i][1]].x), Math.max(full_dict[list_edges[i][0]].x, full_dict[list_edges[i][1]].x)])\n }\n \n return retval.sort((a,b) => d3.ascending(a[0], b[0]))\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":72,"value":"function check_interval_overlap(intvs){\n var big = intvs[0][1]\n var small = 0\n var retval = 0\n for(var i = 1; i < intvs.length; i++){\n small = intvs[i][0]\n if(small < big){\n retval++\n }\n big = intvs[i][1]\n }\n \n return retval\n}\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":44,"value":"function find_v_edges(input_list){\n var retval = new Set()\n \n for(var i = 0; i < input_list.length; i++){\n var edge_to_add = [input_list[i].name, input_list[i].v_edge].sort()[0] + [input_list[i].name, input_list[i].v_edge].sort()[1]\n if(edge_to_add.includes(\"a\") && !edge_to_add.includes(\"b\")){\n edge_to_add = edge_to_add[1] + edge_to_add[0]\n }\n retval.add(edge_to_add)\n }\n return Array.from(retval)\n }\n","pinned":false,"hidden":false,"mode":"ojs"},{"id":47,"value":"function find_order(in_dict){\n var intra = []\n var retval = []\n\n for(var key in in_dict){\n intra.push([in_dict[key].x, key])\n }\n\n intra = intra.sort((a,b) => d3.ascending(a[0],b[0]))\n\n for(var i = 0; i < intra.length; i++){\n retval.push(intra[i][1])\n }\n \n return retval\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":52,"value":"function check_if_left_edge(full_dict, edge_to_check){\n if(edge_to_check.includes('a') && !edge_to_check.includes('b')){\n edge_to_check = edge_to_check.split(\"\").sort().reverse()[0] + edge_to_check.split(\"\").sort().reverse()[1]\n }\n else{\n edge_to_check = edge_to_check.split(\"\").sort()[0] + edge_to_check.split(\"\").sort()[1]\n }\n var start_x = full_dict[edge_to_check[0]].x\n var start_y = full_dict[edge_to_check[0]].y\n var end_x = full_dict[edge_to_check[1]].x\n var end_y = full_dict[edge_to_check[1]].y\n\n if(start_y < end_y){\n return true\n }\n else{\n return false\n }\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":50,"value":"$37","pinned":false,"hidden":false,"mode":"ojs"},{"id":56,"value":"function add_r_neighbor(old_dict, rns){\n var newdict = JSON.parse(JSON.stringify(old_dict));\n for(var key in old_dict){\n newdict[key][\"rn\"] = rns[key]\n }\n return newdict\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":60,"value":"function make_left_edge_list(full_dict, edge_list){\n var start = -1\n var start_y = -1\n var start_x = -1\n var end = -1\n var end_y = -1\n var end_x = -1\n\n var retlist =[]\n \n for(var i = 0; i < edge_list.length; i ++){\n start = edge_list[i][0]\n end = edge_list[i][1]\n start_y = full_dict[start].y\n end_y = full_dict[end].y\n start_x = full_dict[start].x\n end_x = full_dict[end].x\n if(start_y <= end_y){\n retlist.push([edge_list[i], Math.max(start_x, end_x)])\n }\n }\n return retlist.sort((a,b) => d3.ascending(a[1], b[1]))\n}","pinned":false,"hidden":false,"mode":"ojs"},{"id":63,"value":"$38","pinned":false,"hidden":false,"mode":"ojs"},{"id":67,"value":"import {isMonotone_dict} from '@racquellevia/check-if-a-polygon-is-x-monotone'","pinned":false,"hidden":false,"mode":"ojs"},{"id":17,"value":"import {slide} from '@wolfiex/a-presentation-framework-built-on-a-observablehq-notebook'","pinned":false,"hidden":false,"mode":"ojs"},{"id":143,"value":"$39","pinned":false,"hidden":false,"mode":"ojs"},{"id":13,"value":"$3a","pinned":false,"hidden":false,"mode":"ojs"},{"id":7,"value":"hl = require(\"@observablehq/highlight.js@1.0.0/highlight.min.js\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":11,"value":"d3 = require(\"d3@6\")","pinned":false,"hidden":false,"mode":"ojs"},{"id":172,"value":"polygon_display_2 = [[36, 88],\n [79, 79],\n [109, 33],\n [158, 33],\n [168, 74],\n [228, 39],\n [275, 79],\n [250, 150],\n [298, 160],\n [250, 195],\n [186, 204],\n [186, 138],\n [141, 172],\n [112, 113],\n [40, 160],\n [73,163],\n [57, 203],\n [35, 195],\n [13, 177],\n [12, 121]]","pinned":false,"hidden":false,"mode":"ojs"},{"id":174,"value":"polygon_display_1 = [[86, 117],\n [188, 29],\n [281, 35],\n [305, 124],\n [261, 200],\n [211, 101]\n]","pinned":false,"hidden":false,"mode":"ojs"},{"id":1092,"value":"import {Button} from \"@observablehq/inputs\"","pinned":false,"hidden":false,"mode":"ojs"},{"id":1578,"value":"","pinned":true,"hidden":false,"mode":"ojs"},{"id":97,"value":"graph_points(polygon_for_drawing(polygon_cleaned(input_vertices)), 400, 500)","pinned":false,"hidden":false,"mode":"ojs"},{"id":26,"value":"$3b","pinned":false,"hidden":false,"mode":"ojs"},{"id":196,"value":"$3c","pinned":false,"hidden":false,"mode":"ojs"},{"id":190,"value":"$3d","pinned":false,"hidden":false,"mode":"ojs"}],"files":"$W3e","stdlib":"1","titling":"auto"}