Public
Edited
Mar 19, 2022
Skyline Problem
viewof updateButton = html`<button id="runAnimation">Run Again</button>`
<div id="chart"></div>
reRun = () => {
startAnimation().then(d => {
drawSkyline(allResults[1]);
});
}
svg = {
const svgBackgroundColor = "#081c15",
numLines = 100,
lineWidth = 3,
svg = d3.select("#chart")
.append('svg')
.attr("width", width + margin.left + margin.right)
.attr("height", height + margin.top + margin.bottom)
.style("background-color", svgBackgroundColor);
return svg;
}
d3.select("button#runAnimation").on("click", reRun);
container = svg.append("g").attr('transform', `translate(${margin.top}, ${margin.left})`)
numBuildings = 10
buildingColors = d3.scaleSequential()
.domain([0,numBuildings])
.interpolator(d3.interpolateRainbow)
buildings = generateBuildings(numBuildings)
generateBuildings = (numBuildings) => {
return d3.range(numBuildings).map(i => {
let end = numCols - 1;
let randomStart = _.random(numCols-2)//-2 to make sure it's not the absolute last point
let randEnd = end > randomStart+1+4 ? randomStart + 5 : end
let randomEnd = _.random(randomStart+1,randEnd)
let width = randomEnd - randomStart;
let height = _.random(numRows-1)
let bldg = {id: i, x: randomStart, x2: randomEnd, height: height, width: width,status: 'inactive'}
return bldg;
});
}
buildingsList = generateBuildings(numBuildings)
bldgPts = bldgPoints()
bldgPoints = () => {
let points = [];
buildingsList.forEach((pt) => {
let pt1 = {x: pt.x,y: pt.height, id: `${pt.x}${pt.height}`,bid: pt.id}
let pt2 = {x: pt.x2,y: 0, id: `${pt.x2}${0}`, bid: pt.id}
points.push(pt1)
points.push(pt2)
})
return points;
}
update = async (data) => {
let buildingLines = [],
buildingPoints = [],
resultIds,
updatedSet,
dividePoints;
if(data.type == "divide"){
resultIds = data.data.map(d => d.id);
updatedSet = new Set(resultIds);
}else{
resultIds = [];
updatedSet = new Set();
}
buildingsList.forEach((d,i) => {
if(updatedSet.has(d.id)){
d.status = 'active';
}else{
d.status = 'inactive';
}
let line1 = {
status: d.status,
id: d.id,
bid: d.id,
l1: [[x(d.x),y(0)],[x(d.x),y(d.height)]]
};
let line2 = {
status: d.status,
id: d.id + buildingsList.length,
bid: d.id,
l1: [[x(d.x2),y(0)],[x(d.x2),y(d.height)]]
}
buildingLines.push(line1);
buildingLines.push(line2);
})
let rects = container.selectAll("rect")
.data(buildingsList, d => d.id);
let lines = container.selectAll(".lines")
.data(buildingLines, d => d.id)
rects
.join(
enter => enter.append("rect")
.attr('x', d => x(d.x))
.attr('y', d => y(d.height))
.attr('width', d => d.width * x.bandwidth())
.attr('height', d => height - (y(d.height) + y.bandwidth()))
.attr("fill", (d,i) => buildingColors(d.id))
.style("opacity", 0.1),
update => update
.style("opacity", d => d.status == 'active' ? 0.3 : 0.1),
exit => exit.remove()
)
lines
.join(
enter => enter.append("path")
.classed("lines", true)
.attr('d', d => bldgLine(d.l1))
.attr("fill", "none")
.style("opacity", 0.1)
.attr("stroke", (d,i) => buildingColors(d.id%buildingsList.length))
.attr("stroke-width", 2)
.attr("stroke-opacity", .1),
update => update
.style("opacity", d => d.status == 'active' ? 1 : 0.1)
.attr("stroke-opacity", d => d.status == 'active' ? 1 : 0.1),
exit => exit.remove()
)
if(data.type == 'conquer'){
let circles = container.selectAll("circle")
.data(data.data, d => `${d.x}${d.y}`);
circles
.join(
enter => enter.append("circle")
.attr('cx', d => x(d.x))
.attr('cy', d => y(d.y))
.attr('r', 5)
.attr("fill", d => colors[d.status]),
update => update
.style("opacity", 1)
.attr("fill", d => colors[d.status])
),
exit => exit.remove()
}
}
bldgLine = d3.line().x(d => d[0]).y(d => d[1])
drawSkyline = (lines) => {
let bldgOutline = container.selectAll(".outline")
.data(lines)
.join(
enter => enter.append("path")
.classed("outline", true)
.attr('d', d => d3.line().x(d => x(d[0])).y(d => y(d[1]))(d))
.attr("stroke-width", 5)
.attr("stroke", colors.outline)
.attr("fill", "none")
.style("opacity", 0)
.transition()
.duration(500)
.delay((d,i) => i * 300)
.style("opacity", 1)
)
}
{
startAnimation().then(d => {
drawSkyline(allResults[1]);
});
}
startAnimation = async() => {
d3.selectAll('.outline').remove();
for (let x of animate()){
let ans = await x.then(d => d);
await update(ans);
}
}
function* animate() {
for (let i = 0; i < result.length; i++) {
yield Promises.delay(800,result[i]);
}
}
allResults = getSkyline(buildingsList)
result = {return allResults[2];}
getSkyline = (buildingsList) => {
let animationSteps = [];
const skyLine = (buildings) => {
//for the animation
if(buildings.length){
let dCopy = JSON.parse(JSON.stringify(buildings));
let step = {type: "divide", data:dCopy};
animationSteps.push(step);
}
if(!buildings.length){
return [];
}
if(buildings.length == 1){
let pt1 = {id: `${buildings[0].x}${buildings[0].height}`, x: buildings[0].x, y: buildings[0].height,status: "divided"}
let pt2 = {id: `${buildings[0].x2}${0}`, x: buildings[0].x2, y: 0, status: "divided"};
return [pt1,pt2];
//return [[buildings[0].x,buildings[0].height],[buildings[0].x2,0]];
}
//divide the array in half
let midPoint = Math.floor(buildings.length/2);
let left = buildings.slice(0,midPoint);
let right = buildings.slice(midPoint,buildings.length);
//sort left and right sides recursively
left = skyLine(left);
right = skyLine(right);
let solution = [];
let h1 = 0,
h2 = 0,
x = 0,
height = 0;
//merge
while(left.length && right.length){
//each point pair being compared
let l = left[0];
l.status = "compare";
let r = right[0];
r.status = "compare";
let mg = [l,r];
let cCopy = JSON.parse(JSON.stringify(mg));
let step2 = {type: "conquer", data:cCopy};
animationSteps.push(step2);
if(left[0].x < right[0].x){
x = left[0].x;
h1 = left[0].y;
left.shift();
}else{
if(left[0].x > right[0].x){
x = right[0].x;
h2 = right[0].y;
right.shift();
}else{
x = left[0].x;
h1 = left[0].y;
h2 = right[0].y;
left.shift();
right.shift();
}
}
//show left x + height, right x +height,
//take min x, or if equal, take max height of the two
//take min x + height, or if x same for both buildings, add it w/ max height to solution
height = d3.max([h1,h2]);
let solPt = {id: `${x}${height}`, x: x, y: height}
let ptCopy,step3;
if(!solution.length || height != solution[solution.length-1].y){
solPt.status = "solution";
ptCopy = JSON.parse(JSON.stringify([solPt]));
step3 = {type: "conquer", data:ptCopy};
animationSteps.push(step3);
solution.push(solPt);
}else{
solPt.status = "discard";
ptCopy = JSON.parse(JSON.stringify([solPt]));
step3 = {type: "conquer", data:ptCopy};
animationSteps.push(step3);
}
}
while(left.length){
let solPtL = left.shift();
solPtL.status = "solution";
let slCopy = JSON.parse(JSON.stringify([solPtL]));
let step4 = {type: "conquer", data:slCopy};
animationSteps.push(step4);
solution.push(solPtL);
}
while(right.length){
let solPtR = right.shift()
solPtR.status = "solution";
let srCopy = JSON.parse(JSON.stringify([solPtR]));
let step5 = {type: "conquer", data:srCopy};
animationSteps.push(step5);
solution.push(solPtR);
}
//for visualization
if(solution.length){
let sCopy = JSON.parse(JSON.stringify(solution));
animationSteps.push({type: "conquer", action: "solution", data: sCopy});
}
return solution;
}
let sortedSkyline = skyLine(buildingsList);
let outline = getLines(sortedSkyline);
return [sortedSkyline,outline,animationSteps];
}
getLines = (skylinePoints) => {
//construct skyline segments from points returned
const path_points = [];
skylinePoints.forEach((d,i) => {
let prev,curr,pt1,pt2,pt3,pt4,lastPt;
if(i == 0){
prev = [d.x,0];
curr = [d.x,d.y];
pt1 = [d.x,0];
pt2 = [d.x,d.y];
path_points.push([pt1,pt2]);
pt3 = [d.x,d.y];
pt4 = [skylinePoints[i+1].x,d.y]
path_points.push([pt3,pt4]);
}else{
curr = d
lastPt = path_points.slice(-1)[0][1]
pt1 = lastPt
pt2 = [d.x,d.y]
path_points.push([pt1,pt2]);
if (i+1 < skylinePoints.length){
pt3 = [d.x,d.y]
pt4 = [skylinePoints[i+1].x,d.y]
path_points.push([pt3,pt4]);
}
}
})
return path_points;
}
y = d3.scaleBand()
.range([height,0])
.domain(d3.range(numRows))
x = d3.scaleBand()
.range([0,width])
.domain(d3.range(numCols))
numCols = 40
numRows = 25
margin = ({top: 10, bottom: 10, left: 10, right: 10})
width = 800 - margin.left - margin.right
height = 400 - margin.top - margin.bottom
colors = ({
outline: "#FFFFFF",
solution: "green",
compare: "yellow",
discard: "red",
buildingLine: "#efefef",
})
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
