Skip to content

Instantly share code, notes, and snippets.

@ravi4j

ravi4j/index.html

Last active July 30, 2017 22:11
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ravi4j/0e9a69a81bb8ccf989e6715df9931890 to your computer and use it in GitHub Desktop.
Save ravi4j/0e9a69a81bb8ccf989e6715df9931890 to your computer and use it in GitHub Desktop.
Download ZIP
Largest rectangle in histogram
Raw
index.html
<!DOCTYPE html>
<head>
<title>Largest Rectangle</title>
<meta charset="utf-8">
<script src="https://d3js.org/d3.v4.min.js"></script>
<script src="https://unpkg.com/vue"></script>
<style>
body {
width: 100%;
height: 100%;
font-family: monospace;
}
.controls {
position: fixed;
top: 16px;
left: 16px;
background: #f8f8f8;
padding: 0.5rem;
display: flex;
flex-direction: column;
}
.svg-container {
display: table;
border: 1px solid #f8f8f8;
box-shadow: 1px 2px 4px rgba(0, 0, 0, .5);
}
.controls>*+* {
margin-top: 1rem;
}
label {
display: block;
}
.links line {
stroke: #999;
stroke-opacity: 0.6;
}
.nodes circle {
stroke: #fff;
stroke-width: 1.5px;
}
.zoom {
cursor: move;
fill: none;
pointer-events: all;
}
</style>
</head>
<body>
<div id="app">
<div class="controls">
<div>
<label>Scale Screen</label>
<input type="range" v-model="settings.parent" min="0" max="100" />
</div>
<div>
{{ draw }}
</div>
<div>
<button v-on:click="largestRectangleArea">Calculate Area</button>
</div>
<div>
Area: {{ drawArea }}
</div>
<div>
<button v-on:click="reset">Reset</button>
</div>
</div>
<div id="container" class="svg-container" :style="{width: settings.parent + '%'}">
<svg viewBox="0 0 960 600">
</svg>
</div>
</div>
<script type="text/javascript">
class Stack {
constructor() {
this.items = [];
this.count = 0;
}
getLength() {
return this.count;
}
push(item) {
this.items.push(item);
this.count = this.count + 1;
}
pop() {
if (this.count > 0) {
this.count = this.count - 1;
}
return this.items.pop();
}
peek() {
return this.items.slice(-1)[0];
}
isEmpty() {
return this.count === 0 ? true : false;
}
clear() {
while (!this.isEmpty()) {
this.pop();
}
}
};
new Vue({
el: "#app",
data: function () {
var margin = {
top: 20,
right: 20,
bottom: 30,
left: 40
};
return {
x: null,
y: null,
innerSpace: null,
color: d3.scaleOrdinal().range(d3.schemeCategory20),
data: null,
data_n: 10,
area: null,
height_i: null,
left: null,
right: null,
settings: {
strokeColor: "#29B5FF",
width: 900,
height: 500,
parent: 100
},
margin: margin
};
},
mounted: function () {
var width = this.settings.width;
var height = this.settings.height;
var margin = this.margin;
var color = d3.scaleOrdinal().range(d3.schemeCategory20);
// set the dimensions and margins of the graph
width = width - margin.left - margin.right,
height = height - margin.top - margin.bottom;
// set the ranges
var x = d3.scaleBand()
.range([0, width]);
var y = d3.scaleLinear()
.range([height, 0]);
var svg = d3.select('svg');
var g = svg.append("g")
.attr("transform",
"translate(" + margin.left + "," + margin.top + ")");
this.innerSpace = g;
var random = function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
var data = [];
for (let i = 0; i < this.data_n; i++) {
data[i] = random(1, this.data_n);
}
this.data = data;
x.domain(data.map(function (d, i) {
return i;
})); // index
y.domain([0, Math.max(...data)]); // max of data
this.y = y;
this.x = x;
// add the x Axis
g.append("g")
.attr("transform", "translate(0," + height + ")")
.call(d3.axisBottom(x));
// add the y Axis
g.append("g")
.call(d3.axisLeft(y));
},
computed: {
style: function () {
return {
width: this.settings.parent
}
},
draw: function () {
let height = this.settings.height - this.margin.top - this.margin.bottom;
let x = this.x, y = this.y;
let color = this.color;
if (this.data) {
this.innerSpace.selectAll(".bar").remove();
this.innerSpace.selectAll(".bar")
.data(this.data)
.enter().append("rect")
.attr("class", "bar")
.attr("x", function (d, i) {
return x(i);
})
.attr("width", x.bandwidth())
.attr("y", function (d) {
return y(d);
})
.attr("height", function (d) {
return height - y(d);
})
.style('fill', function (d, i) {
return color(i)
});
return "";
}
},
drawArea: function () {
let height = this.settings.height - this.margin.top - this.margin.bottom;
let x = this.x, y = this.y;
if (this.area) {
let n = this.data_n, rect = [], left = this.left, right = this.right;
for (let i = 0; i < n; i++) {
if (i >= left && i <= right) {
rect[i] = this.height_i;
} else {
rect[i] = 0;
}
}
this.innerSpace.selectAll(".bar2").remove();
this.innerSpace.selectAll(".bar2").data(rect)
.enter().append("rect")
.attr("class", "bar")
.attr("x", function (d, i) {
return x(i);
})
.attr("y", function (d) {
return y(d);
})
.attr("width", this.x.bandwidth())
.attr("height", function (d) {
return height - y(d);
})
.style('opacity', 0.5)
.style('fill', "#FFFF00");
return this.area;
}
}
},
methods: {
largestRectangleArea: function () {
let heights = this.data;
if (heights === null || heights.length === 0)
return 0;
let stack = new Stack();
let left = [];
for (var i = 0; i < heights.length; i++) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
let l = stack.isEmpty() ? -1 : stack.peek();
left.push(l);
stack.push(i)
}
// clear stack
stack.clear();
let right = [];
for (let i = heights.length - 1; i >= 0; i--) {
while (!stack.isEmpty() && heights[stack.peek()] >= heights[i]) {
stack.pop();
}
right[i] = stack.isEmpty() ? heights.length : stack.peek();
stack.push(i);
}
let area = 0, l = 0, r = 0;
for (let i = 0; i < heights.length; i++) {
let area_i = heights[i] * (right[i] - left[i] - 1);
if (area_i > area) {
area = area_i;
l = left[i] + 1;
r = right[i] - 1;
this.height_i = heights[i];
}
}
this.area = area;
this.left = l;
this.right = r;
},
reset: function () {
var random = function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
var data = [];
for (let i = 0; i < 10; i++) {
data[i] = random(1, 10);
}
console.log('data-->', data);
this.data = data;
},
}
});
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment