naive tree implementation

author: Julie Lala <jules@okfoc.us> 2014-04-14 09:22:07 -0400
committer: Julie Lala <jules@okfoc.us> 2014-04-14 09:22:07 -0400
commit: 2fdd2f4ee268b8d159e57a91bb0dbf977f6fecef (patch)
tree: 597d43b1c42252ea6bb6e6897a3338967bf6aec2
parent: ad3c9f89e76b1221fb6ee096f0ad7c0c395f000c (diff)
2 files changed, 290 insertions, 0 deletions
diff --git a/rectangles-split.html b/rectangles-split.html
new file mode 100644
index 0000000..20baac4
--- /dev/null
+++ b/rectangles-split.html
@@ -0,0 +1,266 @@
+<!doctype html>
+<html>
+<head>
+	<link rel="stylesheet" type="text/css" href="assets/stylesheets/css.css">
+<style type="text/css">
+body > div {
+	float: left;
+}
+#info {
+	padding: 30px;
+}
+</style>
+</head>
+<body>
+
+<div id="map"></div>
+<div id="info">
+	<select id="palette">
+		<option>colors</option>
+		<option>redblue</option>
+		<option>gray</option>
+		<option selected>alpha</option>
+	</select>
+	<div id="intersects"></div>
+</div>
+
+</body>
+<script type="text/javascript" src="assets/javascripts/util.js"></script>
+<script type="text/javascript" src="rect.js"></script>
+<script type="text/javascript" src="vec2.js"></script>
+<script type="text/javascript">
+
+(function(){
+	var color_palettes = {
+		alpha: [
+			"rgba(0,0,0,0.1)",
+		],
+		redblue: [
+			"rgba(0,0,0,0.2)",
+			"rgba(255,0,0,0.2)",
+			"rgba(0,0,255,0.2)",
+			"rgba(200,200,200,0.2)",
+		],
+		gray: [
+			"rgba(0,0,0,0.1)",
+			"rgba(0,0,0,0.2)",
+			"rgba(0,0,0,0.3)",
+			"rgba(0,0,0,0.4)",
+		],
+		colors: [
+			"rgba(255,0,0,0.5)",
+			"rgba(255,128,0,0.5)",
+			"rgba(128,255,0,0.5)",
+			"rgba(0,255,0,0.5)",
+			"rgba(0,255,128,0.5)",
+			"rgba(0,128,255,0.5)",
+			"rgba(0,0,255,0.5)",
+			"rgba(128,0,255,0.5)",
+			"rgba(255,0,255,0.5)",
+			"rgba(255,0,128,0.5)",
+		]
+	}
+
+	var select = document.querySelector("#palette")
+	select.addEventListener("change", function(){ colors = color_palettes[select.value] })
+
+	window.colors = color_palettes[select.value]
+})()
+
+var canvas = document.createElement("canvas")
+var ctx = canvas.getContext("2d")
+var w = canvas.width = 500
+var h = canvas.height = 500
+document.querySelector("#map").appendChild(canvas)
+
+var rects = [
+	new rect(100,100, 300,300),
+	new rect(200,200, 400,400),
+]
+
+var creating = false, dragging = false
+var mouse = new rect(0,0,0,0)
+canvas.addEventListener("mousedown", function(e){
+	var x = e.pageX, y = e.pageY
+	mouse = new rect (x,y)
+	if (e.shiftKey) {
+		mouse.quantize(10)
+	}
+
+	var intersects = rects.filter(function(r){ return r.contains(x,y) })
+	console.log(intersects)
+	
+	if (intersects.length){
+		dragging = intersects[0]
+	}
+	else {
+		creating = true
+	}
+	if (e.shiftKey && dragging) {
+		dragging.quantize(10)
+	}
+})
+canvas.addEventListener("mousemove", function(e){
+	var x, y
+	if (e.shiftKey) {
+		x = quantize( e.pageX, 10 )
+		y = quantize( e.pageY, 10 )
+	}
+	else {
+		x = e.pageX
+		y = e.pageY
+	}
+
+	mouse.x.b = x
+	mouse.y.b = y
+	
+	if (dragging) {
+		dragging.translation.a = mouse.x.magnitude()
+		dragging.translation.b = mouse.y.magnitude()
+	}
+	else if (creating) {
+		mouse.x.b = x
+		mouse.y.b = y
+	}
+	else {
+		mouse.x.a = mouse.x.b
+		mouse.y.a = mouse.y.b
+	}
+})
+document.addEventListener("mouseup", function(e){
+	if (creating) {
+		if (mouse.height() != 0 && mouse.width() != 0) {
+			rects.push(mouse.normalize())
+		}
+	}
+	if (dragging) {
+		dragging.normalize()
+	}
+	mouse = new rect(e.pageX, e.pageY)
+	creating = dragging = false
+})
+
+function animate(){
+	requestAnimationFrame(animate)
+	ctx.fillStyle = "#fff"
+	ctx.fillRect(0,0,w,h)
+	
+	solve_rects()
+	draw_ruler()
+	draw_rects()
+	draw_mouse()
+}
+animate()
+
+function draw_ruler(){
+	ctx.strokeStyle = "rgba(80,80,80,0.5)"
+	ctx.lineWidth = 1
+	var len = 5
+	for (var i = 0.5; i < w; i += 10) {
+		line(i, 0, i, len)
+		line(0, i, len, i)
+	}
+}
+
+function line (x,y,a,b,translation){
+	if (translation) {
+		x += translation.a
+		a += translation.a
+		y += translation.b
+		b += translation.b
+	}
+	ctx.beginPath()
+	ctx.moveTo(x,y)
+	ctx.lineTo(a,b)
+	ctx.stroke()
+}
+
+function solve_rects(){
+	rects = sort_rects()
+
+	for (var i = 0; i < rects.length; i++) {
+		rects[i].reset()
+	}
+	regions = []
+
+	var left, right
+	for (var i = 0; i < rects.length; i++) {
+		left = rects[i]
+		for (var j = i+1; j < rects.length; j++) {
+			right = rects[j]
+			if (left.intersects(right)) {
+				left.clipTo(right)
+				right.clipTo(left)
+			}
+			if (left.x.b < right.x.a) {
+				break
+			}
+		}
+	}
+	for (var i = 0; i < rects.length; i++) {
+		regions = regions.concat(rects[i].regions)
+	}
+	// handle when two walls are coplanar
+	// generate floor and ceiling for some regions
+	// generate walls from surviving regions
+	// generate ceiling-walls where ceiling has discontinuity
+
+	regions = regions.filter(function(r){ return !!r })
+	for (var i = 0; i < regions.length; i++) {
+		ctx.fillStyle = colors[i % colors.length]
+		regions[i] && regions[i].fill()
+	}
+
+	document.getElementById("intersects").innerHTML = regions.join("<br>")
+}
+function sort_rects(){
+	return rects.sort(function(a,b){
+		if (a.x.a <= b.x.a) {
+			return -1
+		}
+		if (a.x.a > b.x.a) {
+			return 1
+		}
+		if (a.y.a < b.y.a) {
+			return -1
+		}
+		if (a.y.a > b.y.a) {
+			return 1
+		}
+		return 0
+	})
+}
+function draw_regions(){
+}
+function draw_rects(){
+	ctx.strokeStyle = "rgba(80,80,80,0.5)"
+	ctx.lineWidth = 1
+	// ctx.setLineDash([randint(5)+2,randint(2)+2]);
+	ctx.setLineDash([1,1]);
+
+	for (var i = 0; i < rects.length; i++) {
+		ctx.fillStyle = "rgba(0,200,220,0.2)"
+//		rects[i].fill()
+// 			line(rect.x, 0, rect.x, rect.y)
+// 			line(0, rect.y, rect.x, rect.y)
+	}
+}
+function draw_mouse(){
+	ctx.fillStyle = "rgba(255,0,0,0.4)";
+	ctx.beginPath();
+	ctx.arc(mouse.x.b, mouse.y.b, 5, 0, 2*Math.PI, false);
+	ctx.fill();
+
+	if (mouse.width() != 0 && mouse.height() != 0) {
+		if (dragging) {
+			mouse.stroke()
+		}
+		else {
+			ctx.fillStyle = "rgba(255,255,0,0.5)"
+			mouse.clone().normalize().fill()
+		}
+	}
+}
+
+</script>
+</html>
diff --git a/tree.js b/tree.js
new file mode 100644
index 0000000..8229cae
--- /dev/null
+++ b/tree.js
@@ -0,0 +1,24 @@
+var tree = function(n, data){
+	this.lo = null
+	this.hi = null
+	this.value = n
+	this.data = data
+}
+tree.prototype.find = function(n){
+	if (n == this.value) return this
+	if (n < this.value) return this.lo ? this.lo.find(n) : this
+	if (n > this.value) return this.hi ? this.hi.find(n) : this
+}
+tree.prototype.add = function(n, data){
+	var closest = this.find(n)
+	if (n == closest.value) return
+	if (n < closest.value) closest.lo = new tree(n, data)
+	if (n > closest.value) closest.hi = new tree(n, data)
+}
+tree.prototype.toString = function(){
+	var s = "";
+	if (this.lo) s += this.lo.toString()
+	s += this.value + ","
+	if (this.hi) s += this.hi.toString()
+	return s
+}
author	Julie Lala <jules@okfoc.us>	2014-04-14 09:22:07 -0400
committer	Julie Lala <jules@okfoc.us>	2014-04-14 09:22:07 -0400
commit	2fdd2f4ee268b8d159e57a91bb0dbf977f6fecef (patch)
tree	597d43b1c42252ea6bb6e6897a3338967bf6aec2
parent	ad3c9f89e76b1221fb6ee096f0ad7c0c395f000c (diff)