PlainSight · August 29, 2015 14:21
diff --git a/triangle pathing b/triangle pathing
 <html>
 <head>
 <!-- import some shit -->
 </head>
 <body>

 <div>

 <canvas id="mrcanvas">

 </canvas>

 </div>

 <div>
 <h4>
 Intructerinos
 </h4>
 <p>
 	Left click selects a triangles or move the path nodes
 <p>
 <p>
 	Right click adds a vertex to the graph
 <p>
 <p>
 	Shift (or Control) + click toggles pathability of a triangle
 <p>
 </div>

 <div style="font-size: 2pt;">
 All credit to ben macdonald for testing
 </div>


 <script type="text/javascript">

 Array.prototype.remove = function(val) {
    for (var i = 0; i < this.length; i++) {
        if (this[i] === val) {
            this.splice(i, 1);
            i--;
        }
    }
    return this;
 }

 Math.hypot = Math.hypot || function(x, y) {
  return Math.sqrt(x*x + y*y);
 };

 //magic constants
 var TOPLEFT = { x: 0, y: 0 };
 var TOPRIGHT = { x: 800, y: 0 };
 var BOTTOMLEFT = { x: 0, y: 600 };
 var BOTTOMRIGHT = { x: 800, y: 600 };

 //variable names no longer refer to color within
 var LIGHTLIGHTBLUE = '#87CEEB';
 var LIGHTBLUE = '#169D5B';
 var DARKBLUE = '#513317';
 var LIGHTYELLOW = '#FFF176';
 var LIGHTRED = '#F01A24';
 var LIGHTORANGE = '#F15A23';
 var BLACK = '#181B19';

 var c=document.getElementById("mrcanvas");
 c.width = TOPRIGHT.x;
 c.height = BOTTOMLEFT.y;
 c.oncontextmenu = function (e) {
    e.preventDefault();
 };

 var PathVertices = [ 
 {
 	x: TOPLEFT.x + 40,
 	y: TOPRIGHT.y + 40
 }, 
 {
 	x: BOTTOMRIGHT.x - 40,
 	y: BOTTOMRIGHT.y - 40
 }
 ];

 var DraggingPathNode = null;

 var MouseDown = function(e) {
 	var x = e.pageX;
 	var y = e.pageY;
 	var vertex = { x: x - c.offsetLeft, y: y - c.offsetTop};
 	
 	//toggle triangle pathability
 	if(e.shiftKey || e.ctrlKey) {
 		TogglePathability(vertex);		
 		return;
 	}
 	
 	//left click
 	if(e.button === 0) {
 		var pathNode = GetPathNodeSelection(vertex);
 		//check if grabbing a pathnode
 		if(pathNode != null) {
 			DraggingPathNode = pathNode;
 		} else {
 			SelectTriangle(vertex);
 		}
 	}
 	
 	//right click
 	if(e.button === 2) {
 		AddVertex(vertex);
 		DrawTriangles();
 	}
 }

 var MouseUp = function(e) {
 	if(DraggingPathNode != null) {
 		DraggingPathNode = null;
 		DrawTriangles();
 		FindPath(PathVertices[0], PathVertices[1]);
 		FindGridPath(PathVertices[0], PathVertices[1]);
 	}
 }

 var MouseMove = function(e) {
 	var x = e.pageX;
 	var y = e.pageY;
 	var vertex = { x: x - c.offsetLeft, y: y - c.offsetTop};
 	
 	if(DraggingPathNode != null) {
 		DraggingPathNode.x = vertex.x;
 		DraggingPathNode.y = vertex.y;
 		DrawTriangles();
 	}
 }

 var MouseLeave = function(e) {
 	DraggingPathNode = null;
 }

 c.addEventListener("mousedown", MouseDown, false);
 c.addEventListener("mousemove", MouseMove, false);
 c.addEventListener("mouseup", MouseUp, false);
 c.addEventListener("mouseleave", MouseLeave, false);
 var Ctx=c.getContext("2d");
 Ctx.lineWidth = 2;

 var DrawVertices = function(triangle, colour) {
 	Ctx.strokeStyle = colour;
 	Ctx.fillStyle = colour;
 	for(var i = 0; i < 3; i++) {
 		Ctx.beginPath();
 		Ctx.arc(triangle.vertices[i].x, triangle.vertices[i].y, 5, 0, 2 * Math.PI, false);
 		Ctx.stroke();
 		Ctx.fill();
 		Ctx.closePath();
 	}
 }

 var DrawTriangle = function(triangle, highlight, ispathnode) {
 	Ctx.strokeStyle = DARKBLUE;
 		
 	if(highlight) {
 		DrawVertices(triangle, LIGHTRED);
 		
 		Ctx.strokeStyle= LIGHTRED;
 		var circle = triangle.GetCircumcircle();
 		Ctx.beginPath();
 		Ctx.arc(circle.x, circle.y, circle.r, 0, 2 * Math.PI, false);
 		Ctx.stroke();
 		Ctx.closePath();
 	}
 	
 	Ctx.beginPath();
 	for (var i = 0; i < 3; i++) {
 		var j = (i + 1) % 3;
 		var x1 = triangle.vertices[i].x;
 		var y1 = triangle.vertices[i].y;
 		var x2 = triangle.vertices[j].x;
 		var y2 = triangle.vertices[j].y;
 		if(i === 0) {
 			Ctx.moveTo(x1, y1);
 		}
 		Ctx.lineTo(x2, y2);
 	}
 	Ctx.closePath();
 	if(!triangle.pathNode.pathable) {
 		Ctx.fillStyle = LIGHTBLUE;
 		Ctx.fill();
 	}
 	if(ispathnode) {
 		Ctx.fillStyle = LIGHTYELLOW;
 		Ctx.fill();
 	}
 	Ctx.stroke();
 }

 var DrawTriangles = function() { 
 	Ctx.clearRect(0, 0, c.width, c.height);
 	for(var i = 0; i < Triangles.length; i++) {
 		DrawTriangle(Triangles[i]);
 	}
 	DrawPathNodes();
 }

 var DrawGridSpace = function(space, colour) {
 	Ctx.strokeStyle = colour;
 	Ctx.fillStyle = colour;

 	Ctx.beginPath();
 	Ctx.arc(space.vertex.x, space.vertex.y, 2, 0, 2 * Math.PI, false);
 	Ctx.stroke();
 	Ctx.fill();
 	Ctx.closePath();
 	
 	if(space.pathNode.parent != null) {
 		DrawLines([space.GetMiddle(), space.pathNode.parent.triangle.GetMiddle()], colour);
 	}
 }

 var SelectTriangle = function(vertex) {
 	DrawTriangles();
 	var triangle = GetTriangle(vertex);
 	DrawTriangle(triangle, true);
 }

 var DrawLines = function(path, color) {
 	Ctx.strokeStyle = LIGHTORANGE;
 	if(color) {
 		Ctx.strokeStyle = color;
 	}
 	Ctx.beginPath();
 	Ctx.moveTo(path[0].x, path[0].y);
 	for(var i = 1; i < path.length; i++) {
 		Ctx.lineTo(path[i].x, path[i].y);
 	}
 	Ctx.stroke();
 	Ctx.closePath();
 }

 var DrawPathNodes = function() {
 	for(var i = 0; i < 2; i++) {
 		Ctx.beginPath();
 		Ctx.strokeStyle = BLACK;
 		Ctx.fillStyle = DARKBLUE;
 		Ctx.arc(PathVertices[i].x, PathVertices[i].y, 10, 0, 2 * Math.PI, false);
 		Ctx.stroke();
 		Ctx.fill();
 		Ctx.closePath();
 	}
 }

 var DrawPath = function(path) {
 	if(path.length > 1) {
 		var triangles = path.map(function(pn) { return pn.triangle });
 		for(var i = 0; i < triangles.length; i++) {
 			DrawTriangle(triangles[i], false, true);
 		}
 	}
 	DrawLines(triangles.map(function(t) { return t.GetMiddle(); }));
 	DrawPathNodes();
 }

 var DrawGridPath = function(path) {
 	var grids = path.map(function(pn) { return pn.triangle });
 	DrawLines(grids.map(function(t) { return t.GetMiddle(); }), LIGHTRED);
 	DrawPathNodes();
 }

 var DrawText = function(text, y) {
 	var x = 30;
 	Ctx.font = "bold 20px Arial";
 	Ctx.strokeStyle = 'black';
 	Ctx.lineWidth = 3;
 	Ctx.strokeText(text, x, y);
 	Ctx.fillStyle = 'white';
 	Ctx.fillText(text, x, y);
 }

 var GetPathNodeSelection = function(vertex) {
 	for(var i = 0; i < 2; i++) {
 		if(Math.hypot(PathVertices[i].x - vertex.x, PathVertices[i].y - vertex.y) < 11) {
 			return PathVertices[i];
 		}
 	}
 }

 </script>

 <script type="text/javascript">

 //triangle array
 var Triangles = [];

 //triangle object 
 var Triangle = function(v1, v2, v3) {
 	this.vertices = [ v1, v2, v3 ];
 	this.adjacent = [];
 	this.dead = false;
 	this.pathNode = new PathNode(this);
 }
 //v for vertexxa
 Triangle.prototype.IsVertexInside = function(v) {

 	var a = this.vertices[0];
 	var b = this.vertices[1];
 	var c = this.vertices[2];
 	
 	var av_x = v.x - a.x;
 	var av_y = v.y - a.y;

 	var v_ab = (b.x - a.x) * av_y - (b.y - a.y) * av_x > 0;

 	if((c.x - a.x) * av_y - (c.y - a.y) * av_x > 0 == v_ab) return false;

 	if((c.x - b.x) * (v.y - b.y) - (c.y - b.y) * (v.x - b.x) > 0 != v_ab) return false;

 	return true;
 }
 //v for vertex, r for radius
 Triangle.prototype.HasPointInCircle = function(triangle) {
 	var p = triangle.UniqueVertex(this);

 	var one = this.vertices[0];
 	var two = this.vertices[1];
 	var three = this.vertices[2];
 	
 	//arange points counter clockwise because reasons
 	if(!IsLeft([ three, one ], two)) {
 		var temp = one;
 		one = two;
 		two = temp;
 	}
 	
 	var a = one.x - p.x;
 	var b = one.y - p.y;
 	var c = (one.x * one.x - p.x * p.x) + (one.y * one.y - p.y * p.y);
 	var d = two.x - p.x;
 	var e = two.y - p.y;
 	var f = (two.x * two.x - p.x * p.x) + (two.y * two.y - p.y * p.y);
 	var g = three.x - p.x;
 	var h = three.y - p.y;
 	var i = (three.x * three.x - p.x * p.x) + (three.y * three.y - p.y * p.y);
 	
 	var det = (a * (e * i - f * h)) - (b * (d * i - f * g)) + (c * (d * h - e * g));
 	
 	return det > 0;
 }
 //returns the unique vertex of the current triangle given the passed triangle
 Triangle.prototype.UniqueVertex = function(triangle) {
 	for(var i = 0; i < 3; i++) {
 		var equal = false;
 		for(var j = 0; j < 3; j++) {
 			if(this.vertices[i].x == triangle.vertices[j].x && this.vertices[i].y == triangle.vertices[j].y) {
 				equal = true;
 			}
 		}
 		if(!equal) {
 			return this.vertices[i];
 		}
 	}
 	return null;
 }
 //returns if the triangles share two vertices
 Triangle.prototype.ShareTwoPoints = function(other) {
 	var count = 0;
 	for(var i = 0; i < 3; i++) {
 		for(var j = 0; j < 3; j++) {
 			if(this.vertices[i].x == other.vertices[j].x && this.vertices[i].y == other.vertices[j].y) {
 				count++;
 			}
 		}
 	}
 	return 2 == count;
 }
 //Adds a vertex to the current triangle. this kills the current triangle
 Triangle.prototype.AddVertex = function(vertex) {
 	var triangle = GetTriangle(vertex);

 	var t1 = new Triangle(this.vertices[0], this.vertices[1], vertex);
 	var t2 = new Triangle(this.vertices[1], this.vertices[2], vertex);
 	var t3 = new Triangle(this.vertices[0], this.vertices[2], vertex);

 	for(var i = 0; i < this.adjacent.length; i++) {
 		var t = this.adjacent[i];
 		t.adjacent.remove(this);
 		if(t1.ShareTwoPoints(t)) {
 			t.adjacent.push(t1);
 			t1.adjacent.push(t);
 		}
 		if(t2.ShareTwoPoints(t)) {
 			t.adjacent.push(t2);
 			t2.adjacent.push(t);
 		}
 		if(t3.ShareTwoPoints(t)) {
 			t.adjacent.push(t3);
 			t3.adjacent.push(t);
 		}
 	}
 	
 	t1.adjacent.push(t2);
 	t1.adjacent.push(t3);
 	
 	t2.adjacent.push(t1);
 	t2.adjacent.push(t3);
 	
 	t3.adjacent.push(t1);
 	t3.adjacent.push(t2);
 	
 	Triangles.push(t1);
 	Triangles.push(t2);
 	Triangles.push(t3);
 	
 	Triangles.remove(this);
 	
 	return [ t1, t2, t3 ];
 }
 //Gets the vertices shared between the two triangles
 Triangle.prototype.SharedVertices = function(other) {
 	var shared = [];
 	var numfound = 0;
 	for(var i = 0; i < 3; i++) {
 		for(var j = 0; j < 3; j++) {
 			if(this.vertices[i].x == other.vertices[j].x && this.vertices[i].y == other.vertices[j].y) {
 				shared[numfound++] = this.vertices[i];
 			}
 		}
 	}
 	return shared;
 }
 //Get circle centre and radius
 Triangle.prototype.GetCircumcircle = function() {
 	var ax = this.vertices[0].x;
 	var ax2 = ax * ax;
 	var ay = this.vertices[0].y;
 	var ay2 = ay * ay;
 	var bx = this.vertices[1].x;
 	var bx2 = bx * bx;
 	var by = this.vertices[1].y;
 	var by2 = by * by;
 	var cx = this.vertices[2].x;
 	var cx2 = cx * cx;
 	var cy = this.vertices[2].y;
 	var cy2 = cy * cy;

 	var d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by));

 	var ux = ((ax2+ay2)*(by-cy)+(bx2+by2)*(cy-ay)+(cx2+cy2)*(ay-by)) / d;
 	var uy = ((ax2+ay2)*(cx-bx)+(bx2+by2)*(ax-cx)+(cx2+cy2)*(bx-ax)) / d;

 	var ur = Math.hypot(ux - ax, uy - ay);

 	return {
 		x: ux,
 		y: uy,
 		r: ur
 	};
 }
 //Get triangle midpoint
 Triangle.prototype.GetMiddle = function() {
 	var ax = this.vertices[0].x + this.vertices[1].x + this.vertices[2].x;
 	var ay = this.vertices[0].y + this.vertices[1].y + this.vertices[2].y;
 	
 	return { x: ax / 3, y: ay / 3 };
 }

 var GridStep = 10;
 var GridMax = 1000;

 var CoordinateToIndex = function(x, y) {
 	return ((x / (GridStep/2)) * GridMax) + (y / (GridStep/2));
 }

 var GridSpace = function(vertex) {
 	this.vertex = vertex;
 	this.adjacent = [];
 	this.pathNode = new PathNode(this);
 }
 GridSpace.prototype.GetMiddle = function() {
 	return this.vertex;
 }

 var PathNode = function(tri) {
 	this.triangle = tri;
 	this.pathable = true;
 	this.parent = null;
 	this.visited = false;
 	this.heuristic = 0;
 	this.pathlength = 0;
 	this.value = 0;
 }
 PathNode.prototype.TogglePathable = function() {
 	this.pathable = !this.pathable;
 }
 PathNode.prototype.GetAdjacent = function() {
 	return this.triangle.adjacent.map(function (tri) {
 		return tri.pathNode;
 	});
 }
 PathNode.prototype.GetDistance = function(other) {
 	var center = this.triangle.GetMiddle();
 	var targetcenter = other.triangle.GetMiddle();
 	return Math.hypot(center.x - targetcenter.x, center.y - targetcenter.y);
 }
 PathNode.prototype.Visit = function(parent, target) {
 	this.parent = parent;
 	this.visited = true;
 	this.pathlength = this.GetDistance(parent) + parent.pathlength;
 	this.heuristic = this.GetDistance(target);
 	this.value = this.pathlength + this.heuristic;
 }

 var GridSpaces = [];

 var BuildGrid = function() {
 	GridSpaces = [];

 	var startx = TOPLEFT.x + (GridStep/2);
 	var endx = TOPRIGHT.x - (GridStep/2);
 	var starty = TOPLEFT.y + (GridStep/2);
 	var endy = BOTTOMLEFT.y - (GridStep/2);
 	
 	for(var x = startx; x <= endx; x += GridStep) {
 		for(var y = starty; y <= endy; y += GridStep) {
 			var vertex = { x: x, y: y };
 			var newSpace = new GridSpace(vertex);
 			var triangle = GetTriangle(vertex);
 			if(triangle == null) {
 				triangle = GetNearestTriangle(vertex);
 			}
 			newSpace.pathNode.pathable = triangle.pathNode.pathable;
 			GridSpaces[CoordinateToIndex(x, y)] = newSpace;
 		}
 	}
 	
 	for(var x = startx; x <= endx; x += GridStep) {
 		for(var y = starty; y <= endy; y+= GridStep) {
 			var space = GridSpaces[CoordinateToIndex(x, y)]
 			var adj = [];
 			for(var xx = -1; xx < 2; xx++) {
 				for(var yy = -1; yy < 2; yy++) {
 					if(xx == 0 && yy == 0) continue;
 					var gridSpace = GridSpaces[CoordinateToIndex(x + (xx * GridStep), y + (yy * GridStep))];
 					if(gridSpace) {
 						adj.push(gridSpace);
 					}
 				}
 			}
 			space.adjacent = adj;
 		}
 	}
 }

 var FindGridPath = function(startVertex, endVertex) {
 	BuildGrid();

 	var GridPath = [];

 	var startNode = GetGridSpace(startVertex).pathNode;
 	var endNode = GetGridSpace(endVertex).pathNode;
 		
 	if(startNode.pathable == false || endNode.pathable == false) {
 		//return if either start or end are not pathable
 		return;
 	}

 	var openSet = [];
 	
 	var visited = 0;
 	var polled = 0;
 	
 	startNode.pathlength = 0;
 	startNode.heuristic = startNode.GetDistance(endNode);
 	startNode.value = startNode.heuristic;
 	startNode.visited = true;
 	
 	openSet.push(startNode);
 	
 	while(openSet.length != 0) {
 		
 		openSet.sort(function(a, b) { return b.value - a.value; });
 		
 		var nominated = openSet.pop();
 		
 		polled++;
 		
 		if(nominated === endNode) {
 			break;
 		}
 	
 		var adjacent = nominated.GetAdjacent();
 		
 		for(var i = 0; i < adjacent.length; i++) {
 			var current = adjacent[i];
 			
 			if(current.pathable) {
 				if(!current.visited) {
 					visited++;
 					current.Visit(nominated, endNode);
 					openSet.push(current);
 				} else {
 					var newPathLength = nominated.pathlength + nominated.GetDistance(current);
 					if(newPathLength < current.pathlength) {
 						current.Visit(nominated, endNode);
 					}
 				}
 			}
 		}
 	}
 	
 	//end node either has parent == null: no path, or parent == something: path exists
 	var currentNode = endNode;
 	while(currentNode != null) {
 		GridPath.push(currentNode);
 		//DrawGridSpace(currentNode.triangle, LIGHTRED);
 		currentNode = currentNode.parent;
 	}
 		
 	DrawGridPath(GridPath);
 	DrawText("Grid - discovered: " + visited + ", polled: " + polled, 20);
 }

 var FindPath = function(startVertex, endVertex) {
 	
 	var Path = [];
 	
 	for(var i = 0; i < Triangles.length; i++) {
 		Triangles[i].pathNode.parent = null;
 		Triangles[i].pathNode.visited = false;
 		Triangles[i].pathNode.heuristic = 0;
 		Triangles[i].pathNode.pathlength = 0;
 		Triangles[i].pathNode.value = 0;
 	}
 	
 	var startNode = GetTriangle(startVertex).pathNode;
 	var endNode = GetTriangle(endVertex).pathNode;
 	
 	if(startNode.pathable == false || endNode.pathable == false) {
 		//return if either start or end are not pathable
 		return;
 	}

 	var openSet = [];
 	
 	var visited = 0;
 	var polled = 0;
 	
 	startNode.pathlength = 0;
 	startNode.heuristic = startNode.GetDistance(endNode);
 	startNode.value = startNode.heuristic;
 	startNode.visited = true;
 	
 	openSet.push(startNode);
 	
 	while(openSet.length != 0) {
 		
 		openSet.sort(function(a, b) { return b.value - a.value; });
 		
 		var nominated = openSet.pop();
 		
 		polled++;
 		
 		if(nominated === endNode) {
 			break;
 		}
 	
 		var adjacent = nominated.GetAdjacent();

 		for(var i = 0; i < adjacent.length; i++) {
 			var current = adjacent[i];
 			
 			if(current.pathable) {
 				if(!current.visited) {
 					visited++;
 					current.Visit(nominated, endNode);
 					openSet.push(current);
 				} else {
 					
 					var newPathLength = nominated.pathlength + current.GetDistance(nominated);
 					
 					if(newPathLength < current.pathlength) {
 						current.Visit(nominated, endNode);
 					}
 				}
 			}
 		}
 	}
 	
 	//end node either has parent == null: no path, or parent == something: path exists
 	var currentNode = endNode;
 	while(currentNode != null) {
 		Path.push(currentNode);
 		currentNode = currentNode.parent;
 	}
 	
 	DrawPath(Path);
 	DrawText("Triangle - discovered: " + visited + ", polled: " + polled, 50);
 }

 //fun static methods because organisation is for scrubs

 //determines if candidate is to the left of line where line is vertex a -> b
 var IsLeft = function(line, candidate) {
 	return ((line[1].x - line[0].x)*(candidate.y - line[0].y) - (line[1].y - line[0].y)*(candidate.x - line[0].x)) >= 0;
 }

 var GetTriangle = function(vertex) {
 	for(var i = 0; i < Triangles.length; i++) {
 		if(Triangles[i].IsVertexInside(vertex)) {
 			return Triangles[i];
 		}
 	}
 	return null;
 }

 var GetNearestTriangle = function(vertex) {
 	var nearest = null;
 	var nearestDistance = 9999999999;
 	for(var i = 0; i < Triangles.length; i++) {
 		var trianglecentre = Triangles[i].GetMiddle();
 		var distance = Math.hypot(trianglecentre.x - vertex.x, trianglecentre.y - vertex.y);
 		if(distance < nearestDistance) {
 			nearest = Triangles[i];
 			nearestDistance = distance;
 		}
 	}
 	return nearest;
 }

 var GetGridSpace = function(vertex) {
 	var x = (Math.floor(vertex.x / GridStep) * GridStep) + (GridStep/2);
 	var y = (Math.floor(vertex.y / GridStep) * GridStep) + (GridStep/2);
 	var index = CoordinateToIndex(x, y);
 	
 	return GridSpaces[index];
 }

 var Flip = function(t1, t2) {
 	var common = t1.SharedVertices(t2);
 	
 	var uncommon = [];
 	uncommon[0] = t1.UniqueVertex(t2);
 	uncommon[1] = t2.UniqueVertex(t1);
 	
 	//make new triangles
 	var t1n = new Triangle(uncommon[0], uncommon[1], common[0]);
 	var t2n = new Triangle(uncommon[0], uncommon[1], common[1]);
 	
 	var adjacents = [];
 	
 	for(var i = 0; i < t1.adjacent.length; i++) {
 		adjacents.push(t1.adjacent[i]);
 	}
 	for(var i = 0; i < t2.adjacent.length; i++) {
 		adjacents.push(t2.adjacent[i]);
 	}
 	adjacents.remove(t1);
 	adjacents.remove(t2);
 	
 	//remove old triangles from their neighbours adjacent lists
 	for(var i = 0; i < t1.adjacent.length; i++) {
 		var t = t1.adjacent[i];
 		t.adjacent.remove(t1);
 	}
 	
 	for(var i = 0; i < t2.adjacent.length; i++) {
 		var t = t2.adjacent[i];
 		t.adjacent.remove(t2);
 	}
 	
 	for(var i = 0; i < adjacents.length; i++) {
 		var t = adjacents[i];
 		if(t1n.ShareTwoPoints(t)) {
 			t.adjacent.push(t1n);
 			t1n.adjacent.push(t);
 		}
 		
 		if(t2n.ShareTwoPoints(t)) {
 			t.adjacent.push(t2n);
 			t2n.adjacent.push(t);
 		}	
 	}
 	
 	t1n.adjacent.push(t2n);
 	t2n.adjacent.push(t1n);
 		
 	Triangles.remove(t1);
 	t1.dead = true;
 	Triangles.remove(t2);
 	t2.dead = true;
 	Triangles.push(t1n);
 	Triangles.push(t2n);
 			
 	return [ t1n, t2n ];
 }

 var AddVertex = function(vertex) {
 	var inside = null;
 	var edge = null;

 	for(var i = 0; i < Triangles.length; i++) {
 		var t = Triangles[i];
 		if(t.IsVertexInside(vertex)) {
 			inside = t;
 		}
 		if(edge != null || inside != null) {
 			break;
 		}
 	}
 	if(inside != null) {
 		var newTriangles = inside.AddVertex(vertex);
 		for(var i = 0; i < newTriangles.length; i++) {
 			if(!newTriangles[i].dead) {
 				CheckAndFlip(newTriangles[i]);
 			}
 		}
 	}
 }

 var CheckAndFlip = function(t) {
 			
 	for(var i = 0; i < t.adjacent.length; i++) {
 		var tt = t.adjacent[i];
 					
 		if(t.HasPointInCircle(tt)) {
 			var newTriangles = Flip(t, tt);
 			CheckAndFlip(newTriangles[0]);
 			if(!newTriangles[1].dead) {
 				CheckAndFlip(newTriangles[1]);
 			}
 			return;
 		}
 	}
 }

 var TogglePathability = function(vertex) {
 	var triangle = GetTriangle(vertex);
 	if(triangle !== null) {		
 		triangle.pathNode.TogglePathable();
 		DrawTriangles();
 	}
 }

 var Initialize = function() {

 Triangles = [];

 var t1 = new Triangle(TOPLEFT, TOPRIGHT, BOTTOMLEFT);
 var t2 = new Triangle(BOTTOMRIGHT, TOPRIGHT, BOTTOMLEFT);
 t1.adjacent.push(t2);
 t2.adjacent.push(t1);
 Triangles.push(t1);
 Triangles.push(t2);

 DrawTriangles();

 }

 window.onload = function() {
 	Initialize();
 }

 </script>

 <style type="text/css">

 #mrcanvas {
 	width: 800px;;
 	height: 600px;
 }

 </style>


 </body>
 </html>
	<html>
	<head>
	<!-- import some shit -->
	</head>
	<body>

	<div>

	<canvas id="mrcanvas">

	</canvas>

	</div>

	<div>
	<h4>
	Intructerinos
	</h4>
	<p>
	Left click selects a triangles or move the path nodes
	<p>
	<p>
	Right click adds a vertex to the graph
	<p>
	<p>
	Shift (or Control) + click toggles pathability of a triangle
	<p>
	</div>

	<div style="font-size: 2pt;">
	All credit to ben macdonald for testing
	</div>


	<script type="text/javascript">

	Array.prototype.remove = function(val) {
	for (var i = 0; i < this.length; i++) {
	if (this[i] === val) {
	this.splice(i, 1);
	i--;
	}
	}
	return this;
	}

	Math.hypot = Math.hypot \|\| function(x, y) {
	return Math.sqrt(xx + yy);
	};

	//magic constants
	var TOPLEFT = { x: 0, y: 0 };
	var TOPRIGHT = { x: 800, y: 0 };
	var BOTTOMLEFT = { x: 0, y: 600 };
	var BOTTOMRIGHT = { x: 800, y: 600 };

	//variable names no longer refer to color within
	var LIGHTLIGHTBLUE = '#87CEEB';
	var LIGHTBLUE = '#169D5B';
	var DARKBLUE = '#513317';
	var LIGHTYELLOW = '#FFF176';
	var LIGHTRED = '#F01A24';
	var LIGHTORANGE = '#F15A23';
	var BLACK = '#181B19';

	var c=document.getElementById("mrcanvas");
	c.width = TOPRIGHT.x;
	c.height = BOTTOMLEFT.y;
	c.oncontextmenu = function (e) {
	e.preventDefault();
	};

	var PathVertices = [
	{
	x: TOPLEFT.x + 40,
	y: TOPRIGHT.y + 40
	},
	{
	x: BOTTOMRIGHT.x - 40,
	y: BOTTOMRIGHT.y - 40
	}
	];

	var DraggingPathNode = null;

	var MouseDown = function(e) {
	var x = e.pageX;
	var y = e.pageY;
	var vertex = { x: x - c.offsetLeft, y: y - c.offsetTop};

	//toggle triangle pathability
	if(e.shiftKey \|\| e.ctrlKey) {
	TogglePathability(vertex);
	return;
	}

	//left click
	if(e.button === 0) {
	var pathNode = GetPathNodeSelection(vertex);
	//check if grabbing a pathnode
	if(pathNode != null) {
	DraggingPathNode = pathNode;
	} else {
	SelectTriangle(vertex);
	}
	}

	//right click
	if(e.button === 2) {
	AddVertex(vertex);
	DrawTriangles();
	}
	}

	var MouseUp = function(e) {
	if(DraggingPathNode != null) {
	DraggingPathNode = null;
	DrawTriangles();
	FindPath(PathVertices[0], PathVertices[1]);
	FindGridPath(PathVertices[0], PathVertices[1]);
	}
	}

	var MouseMove = function(e) {
	var x = e.pageX;
	var y = e.pageY;
	var vertex = { x: x - c.offsetLeft, y: y - c.offsetTop};

	if(DraggingPathNode != null) {
	DraggingPathNode.x = vertex.x;
	DraggingPathNode.y = vertex.y;
	DrawTriangles();
	}
	}

	var MouseLeave = function(e) {
	DraggingPathNode = null;
	}

	c.addEventListener("mousedown", MouseDown, false);
	c.addEventListener("mousemove", MouseMove, false);
	c.addEventListener("mouseup", MouseUp, false);
	c.addEventListener("mouseleave", MouseLeave, false);
	var Ctx=c.getContext("2d");
	Ctx.lineWidth = 2;

	var DrawVertices = function(triangle, colour) {
	Ctx.strokeStyle = colour;
	Ctx.fillStyle = colour;
	for(var i = 0; i < 3; i++) {
	Ctx.beginPath();
	Ctx.arc(triangle.vertices[i].x, triangle.vertices[i].y, 5, 0, 2 * Math.PI, false);
	Ctx.stroke();
	Ctx.fill();
	Ctx.closePath();
	}
	}

	var DrawTriangle = function(triangle, highlight, ispathnode) {
	Ctx.strokeStyle = DARKBLUE;

	if(highlight) {
	DrawVertices(triangle, LIGHTRED);

	Ctx.strokeStyle= LIGHTRED;
	var circle = triangle.GetCircumcircle();
	Ctx.beginPath();
	Ctx.arc(circle.x, circle.y, circle.r, 0, 2 * Math.PI, false);
	Ctx.stroke();
	Ctx.closePath();
	}

	Ctx.beginPath();
	for (var i = 0; i < 3; i++) {
	var j = (i + 1) % 3;
	var x1 = triangle.vertices[i].x;
	var y1 = triangle.vertices[i].y;
	var x2 = triangle.vertices[j].x;
	var y2 = triangle.vertices[j].y;
	if(i === 0) {
	Ctx.moveTo(x1, y1);
	}
	Ctx.lineTo(x2, y2);
	}
	Ctx.closePath();
	if(!triangle.pathNode.pathable) {
	Ctx.fillStyle = LIGHTBLUE;
	Ctx.fill();
	}
	if(ispathnode) {
	Ctx.fillStyle = LIGHTYELLOW;
	Ctx.fill();
	}
	Ctx.stroke();
	}

	var DrawTriangles = function() {
	Ctx.clearRect(0, 0, c.width, c.height);
	for(var i = 0; i < Triangles.length; i++) {
	DrawTriangle(Triangles[i]);
	}
	DrawPathNodes();
	}

	var DrawGridSpace = function(space, colour) {
	Ctx.strokeStyle = colour;
	Ctx.fillStyle = colour;

	Ctx.beginPath();
	Ctx.arc(space.vertex.x, space.vertex.y, 2, 0, 2 * Math.PI, false);
	Ctx.stroke();
	Ctx.fill();
	Ctx.closePath();

	if(space.pathNode.parent != null) {
	DrawLines([space.GetMiddle(), space.pathNode.parent.triangle.GetMiddle()], colour);
	}
	}

	var SelectTriangle = function(vertex) {
	DrawTriangles();
	var triangle = GetTriangle(vertex);
	DrawTriangle(triangle, true);
	}

	var DrawLines = function(path, color) {
	Ctx.strokeStyle = LIGHTORANGE;
	if(color) {
	Ctx.strokeStyle = color;
	}
	Ctx.beginPath();
	Ctx.moveTo(path[0].x, path[0].y);
	for(var i = 1; i < path.length; i++) {
	Ctx.lineTo(path[i].x, path[i].y);
	}
	Ctx.stroke();
	Ctx.closePath();
	}

	var DrawPathNodes = function() {
	for(var i = 0; i < 2; i++) {
	Ctx.beginPath();
	Ctx.strokeStyle = BLACK;
	Ctx.fillStyle = DARKBLUE;
	Ctx.arc(PathVertices[i].x, PathVertices[i].y, 10, 0, 2 * Math.PI, false);
	Ctx.stroke();
	Ctx.fill();
	Ctx.closePath();
	}
	}

	var DrawPath = function(path) {
	if(path.length > 1) {
	var triangles = path.map(function(pn) { return pn.triangle });
	for(var i = 0; i < triangles.length; i++) {
	DrawTriangle(triangles[i], false, true);
	}
	}
	DrawLines(triangles.map(function(t) { return t.GetMiddle(); }));
	DrawPathNodes();
	}

	var DrawGridPath = function(path) {
	var grids = path.map(function(pn) { return pn.triangle });
	DrawLines(grids.map(function(t) { return t.GetMiddle(); }), LIGHTRED);
	DrawPathNodes();
	}

	var DrawText = function(text, y) {
	var x = 30;
	Ctx.font = "bold 20px Arial";
	Ctx.strokeStyle = 'black';
	Ctx.lineWidth = 3;
	Ctx.strokeText(text, x, y);
	Ctx.fillStyle = 'white';
	Ctx.fillText(text, x, y);
	}

	var GetPathNodeSelection = function(vertex) {
	for(var i = 0; i < 2; i++) {
	if(Math.hypot(PathVertices[i].x - vertex.x, PathVertices[i].y - vertex.y) < 11) {
	return PathVertices[i];
	}
	}
	}

	</script>

	<script type="text/javascript">

	//triangle array
	var Triangles = [];

	//triangle object
	var Triangle = function(v1, v2, v3) {
	this.vertices = [ v1, v2, v3 ];
	this.adjacent = [];
	this.dead = false;
	this.pathNode = new PathNode(this);
	}
	//v for vertexxa
	Triangle.prototype.IsVertexInside = function(v) {

	var a = this.vertices[0];
	var b = this.vertices[1];
	var c = this.vertices[2];

	var av_x = v.x - a.x;
	var av_y = v.y - a.y;

	var v_ab = (b.x - a.x) * av_y - (b.y - a.y) * av_x > 0;

	if((c.x - a.x) * av_y - (c.y - a.y) * av_x > 0 == v_ab) return false;

	if((c.x - b.x) * (v.y - b.y) - (c.y - b.y) * (v.x - b.x) > 0 != v_ab) return false;

	return true;
	}
	//v for vertex, r for radius
	Triangle.prototype.HasPointInCircle = function(triangle) {
	var p = triangle.UniqueVertex(this);

	var one = this.vertices[0];
	var two = this.vertices[1];
	var three = this.vertices[2];

	//arange points counter clockwise because reasons
	if(!IsLeft([ three, one ], two)) {
	var temp = one;
	one = two;
	two = temp;
	}

	var a = one.x - p.x;
	var b = one.y - p.y;
	var c = (one.x * one.x - p.x * p.x) + (one.y * one.y - p.y * p.y);
	var d = two.x - p.x;
	var e = two.y - p.y;
	var f = (two.x * two.x - p.x * p.x) + (two.y * two.y - p.y * p.y);
	var g = three.x - p.x;
	var h = three.y - p.y;
	var i = (three.x * three.x - p.x * p.x) + (three.y * three.y - p.y * p.y);

	var det = (a * (e * i - f * h)) - (b * (d * i - f * g)) + (c * (d * h - e * g));

	return det > 0;
	}
	//returns the unique vertex of the current triangle given the passed triangle
	Triangle.prototype.UniqueVertex = function(triangle) {
	for(var i = 0; i < 3; i++) {
	var equal = false;
	for(var j = 0; j < 3; j++) {
	if(this.vertices[i].x == triangle.vertices[j].x && this.vertices[i].y == triangle.vertices[j].y) {
	equal = true;
	}
	}
	if(!equal) {
	return this.vertices[i];
	}
	}
	return null;
	}
	//returns if the triangles share two vertices
	Triangle.prototype.ShareTwoPoints = function(other) {
	var count = 0;
	for(var i = 0; i < 3; i++) {
	for(var j = 0; j < 3; j++) {
	if(this.vertices[i].x == other.vertices[j].x && this.vertices[i].y == other.vertices[j].y) {
	count++;
	}
	}
	}
	return 2 == count;
	}
	//Adds a vertex to the current triangle. this kills the current triangle
	Triangle.prototype.AddVertex = function(vertex) {
	var triangle = GetTriangle(vertex);

	var t1 = new Triangle(this.vertices[0], this.vertices[1], vertex);
	var t2 = new Triangle(this.vertices[1], this.vertices[2], vertex);
	var t3 = new Triangle(this.vertices[0], this.vertices[2], vertex);

	for(var i = 0; i < this.adjacent.length; i++) {
	var t = this.adjacent[i];
	t.adjacent.remove(this);
	if(t1.ShareTwoPoints(t)) {
	t.adjacent.push(t1);
	t1.adjacent.push(t);
	}
	if(t2.ShareTwoPoints(t)) {
	t.adjacent.push(t2);
	t2.adjacent.push(t);
	}
	if(t3.ShareTwoPoints(t)) {
	t.adjacent.push(t3);
	t3.adjacent.push(t);
	}
	}

	t1.adjacent.push(t2);
	t1.adjacent.push(t3);

	t2.adjacent.push(t1);
	t2.adjacent.push(t3);

	t3.adjacent.push(t1);
	t3.adjacent.push(t2);

	Triangles.push(t1);
	Triangles.push(t2);
	Triangles.push(t3);

	Triangles.remove(this);

	return [ t1, t2, t3 ];
	}
	//Gets the vertices shared between the two triangles
	Triangle.prototype.SharedVertices = function(other) {
	var shared = [];
	var numfound = 0;
	for(var i = 0; i < 3; i++) {
	for(var j = 0; j < 3; j++) {
	if(this.vertices[i].x == other.vertices[j].x && this.vertices[i].y == other.vertices[j].y) {
	shared[numfound++] = this.vertices[i];
	}
	}
	}
	return shared;
	}
	//Get circle centre and radius
	Triangle.prototype.GetCircumcircle = function() {
	var ax = this.vertices[0].x;
	var ax2 = ax * ax;
	var ay = this.vertices[0].y;
	var ay2 = ay * ay;
	var bx = this.vertices[1].x;
	var bx2 = bx * bx;
	var by = this.vertices[1].y;
	var by2 = by * by;
	var cx = this.vertices[2].x;
	var cx2 = cx * cx;
	var cy = this.vertices[2].y;
	var cy2 = cy * cy;

	var d = 2 * (ax * (by - cy) + bx * (cy - ay) + cx * (ay - by));

	var ux = ((ax2+ay2)(by-cy)+(bx2+by2)(cy-ay)+(cx2+cy2)*(ay-by)) / d;
	var uy = ((ax2+ay2)(cx-bx)+(bx2+by2)(ax-cx)+(cx2+cy2)*(bx-ax)) / d;

	var ur = Math.hypot(ux - ax, uy - ay);

	return {
	x: ux,
	y: uy,
	r: ur
	};
	}
	//Get triangle midpoint
	Triangle.prototype.GetMiddle = function() {
	var ax = this.vertices[0].x + this.vertices[1].x + this.vertices[2].x;
	var ay = this.vertices[0].y + this.vertices[1].y + this.vertices[2].y;

	return { x: ax / 3, y: ay / 3 };
	}

	var GridStep = 10;
	var GridMax = 1000;

	var CoordinateToIndex = function(x, y) {
	return ((x / (GridStep/2)) * GridMax) + (y / (GridStep/2));
	}

	var GridSpace = function(vertex) {
	this.vertex = vertex;
	this.adjacent = [];
	this.pathNode = new PathNode(this);
	}
	GridSpace.prototype.GetMiddle = function() {
	return this.vertex;
	}

	var PathNode = function(tri) {
	this.triangle = tri;
	this.pathable = true;
	this.parent = null;
	this.visited = false;
	this.heuristic = 0;
	this.pathlength = 0;
	this.value = 0;
	}
	PathNode.prototype.TogglePathable = function() {
	this.pathable = !this.pathable;
	}
	PathNode.prototype.GetAdjacent = function() {
	return this.triangle.adjacent.map(function (tri) {
	return tri.pathNode;
	});
	}
	PathNode.prototype.GetDistance = function(other) {
	var center = this.triangle.GetMiddle();
	var targetcenter = other.triangle.GetMiddle();
	return Math.hypot(center.x - targetcenter.x, center.y - targetcenter.y);
	}
	PathNode.prototype.Visit = function(parent, target) {
	this.parent = parent;
	this.visited = true;
	this.pathlength = this.GetDistance(parent) + parent.pathlength;
	this.heuristic = this.GetDistance(target);
	this.value = this.pathlength + this.heuristic;
	}

	var GridSpaces = [];

	var BuildGrid = function() {
	GridSpaces = [];

	var startx = TOPLEFT.x + (GridStep/2);
	var endx = TOPRIGHT.x - (GridStep/2);
	var starty = TOPLEFT.y + (GridStep/2);
	var endy = BOTTOMLEFT.y - (GridStep/2);

	for(var x = startx; x <= endx; x += GridStep) {
	for(var y = starty; y <= endy; y += GridStep) {
	var vertex = { x: x, y: y };
	var newSpace = new GridSpace(vertex);
	var triangle = GetTriangle(vertex);
	if(triangle == null) {
	triangle = GetNearestTriangle(vertex);
	}
	newSpace.pathNode.pathable = triangle.pathNode.pathable;
	GridSpaces[CoordinateToIndex(x, y)] = newSpace;
	}
	}

	for(var x = startx; x <= endx; x += GridStep) {
	for(var y = starty; y <= endy; y+= GridStep) {
	var space = GridSpaces[CoordinateToIndex(x, y)]
	var adj = [];
	for(var xx = -1; xx < 2; xx++) {
	for(var yy = -1; yy < 2; yy++) {
	if(xx == 0 && yy == 0) continue;
	var gridSpace = GridSpaces[CoordinateToIndex(x + (xx * GridStep), y + (yy * GridStep))];
	if(gridSpace) {
	adj.push(gridSpace);
	}
	}
	}
	space.adjacent = adj;
	}
	}
	}

	var FindGridPath = function(startVertex, endVertex) {
	BuildGrid();

	var GridPath = [];

	var startNode = GetGridSpace(startVertex).pathNode;
	var endNode = GetGridSpace(endVertex).pathNode;

	if(startNode.pathable == false \|\| endNode.pathable == false) {
	//return if either start or end are not pathable
	return;
	}

	var openSet = [];

	var visited = 0;
	var polled = 0;

	startNode.pathlength = 0;
	startNode.heuristic = startNode.GetDistance(endNode);
	startNode.value = startNode.heuristic;
	startNode.visited = true;

	openSet.push(startNode);

	while(openSet.length != 0) {

	openSet.sort(function(a, b) { return b.value - a.value; });

	var nominated = openSet.pop();

	polled++;

	if(nominated === endNode) {
	break;
	}

	var adjacent = nominated.GetAdjacent();

	for(var i = 0; i < adjacent.length; i++) {
	var current = adjacent[i];

	if(current.pathable) {
	if(!current.visited) {
	visited++;
	current.Visit(nominated, endNode);
	openSet.push(current);
	} else {
	var newPathLength = nominated.pathlength + nominated.GetDistance(current);
	if(newPathLength < current.pathlength) {
	current.Visit(nominated, endNode);
	}
	}
	}
	}
	}

	//end node either has parent == null: no path, or parent == something: path exists
	var currentNode = endNode;
	while(currentNode != null) {
	GridPath.push(currentNode);
	//DrawGridSpace(currentNode.triangle, LIGHTRED);
	currentNode = currentNode.parent;
	}

	DrawGridPath(GridPath);
	DrawText("Grid - discovered: " + visited + ", polled: " + polled, 20);
	}

	var FindPath = function(startVertex, endVertex) {

	var Path = [];

	for(var i = 0; i < Triangles.length; i++) {
	Triangles[i].pathNode.parent = null;
	Triangles[i].pathNode.visited = false;
	Triangles[i].pathNode.heuristic = 0;
	Triangles[i].pathNode.pathlength = 0;
	Triangles[i].pathNode.value = 0;
	}

	var startNode = GetTriangle(startVertex).pathNode;
	var endNode = GetTriangle(endVertex).pathNode;

	if(startNode.pathable == false \|\| endNode.pathable == false) {
	//return if either start or end are not pathable
	return;
	}

	var openSet = [];

	var visited = 0;
	var polled = 0;

	startNode.pathlength = 0;
	startNode.heuristic = startNode.GetDistance(endNode);
	startNode.value = startNode.heuristic;
	startNode.visited = true;

	openSet.push(startNode);

	while(openSet.length != 0) {

	openSet.sort(function(a, b) { return b.value - a.value; });

	var nominated = openSet.pop();

	polled++;

	if(nominated === endNode) {
	break;
	}

	var adjacent = nominated.GetAdjacent();

	for(var i = 0; i < adjacent.length; i++) {
	var current = adjacent[i];

	if(current.pathable) {
	if(!current.visited) {
	visited++;
	current.Visit(nominated, endNode);
	openSet.push(current);
	} else {

	var newPathLength = nominated.pathlength + current.GetDistance(nominated);

	if(newPathLength < current.pathlength) {
	current.Visit(nominated, endNode);
	}
	}
	}
	}
	}

	//end node either has parent == null: no path, or parent == something: path exists
	var currentNode = endNode;
	while(currentNode != null) {
	Path.push(currentNode);
	currentNode = currentNode.parent;
	}

	DrawPath(Path);
	DrawText("Triangle - discovered: " + visited + ", polled: " + polled, 50);
	}

	//fun static methods because organisation is for scrubs

	//determines if candidate is to the left of line where line is vertex a -> b
	var IsLeft = function(line, candidate) {
	return ((line[1].x - line[0].x)(candidate.y - line[0].y) - (line[1].y - line[0].y)(candidate.x - line[0].x)) >= 0;
	}

	var GetTriangle = function(vertex) {
	for(var i = 0; i < Triangles.length; i++) {
	if(Triangles[i].IsVertexInside(vertex)) {
	return Triangles[i];
	}
	}
	return null;
	}

	var GetNearestTriangle = function(vertex) {
	var nearest = null;
	var nearestDistance = 9999999999;
	for(var i = 0; i < Triangles.length; i++) {
	var trianglecentre = Triangles[i].GetMiddle();
	var distance = Math.hypot(trianglecentre.x - vertex.x, trianglecentre.y - vertex.y);
	if(distance < nearestDistance) {
	nearest = Triangles[i];
	nearestDistance = distance;
	}
	}
	return nearest;
	}

	var GetGridSpace = function(vertex) {
	var x = (Math.floor(vertex.x / GridStep) * GridStep) + (GridStep/2);
	var y = (Math.floor(vertex.y / GridStep) * GridStep) + (GridStep/2);
	var index = CoordinateToIndex(x, y);

	return GridSpaces[index];
	}

	var Flip = function(t1, t2) {
	var common = t1.SharedVertices(t2);

	var uncommon = [];
	uncommon[0] = t1.UniqueVertex(t2);
	uncommon[1] = t2.UniqueVertex(t1);

	//make new triangles
	var t1n = new Triangle(uncommon[0], uncommon[1], common[0]);
	var t2n = new Triangle(uncommon[0], uncommon[1], common[1]);

	var adjacents = [];

	for(var i = 0; i < t1.adjacent.length; i++) {
	adjacents.push(t1.adjacent[i]);
	}
	for(var i = 0; i < t2.adjacent.length; i++) {
	adjacents.push(t2.adjacent[i]);
	}
	adjacents.remove(t1);
	adjacents.remove(t2);

	//remove old triangles from their neighbours adjacent lists
	for(var i = 0; i < t1.adjacent.length; i++) {
	var t = t1.adjacent[i];
	t.adjacent.remove(t1);
	}

	for(var i = 0; i < t2.adjacent.length; i++) {
	var t = t2.adjacent[i];
	t.adjacent.remove(t2);
	}

	for(var i = 0; i < adjacents.length; i++) {
	var t = adjacents[i];
	if(t1n.ShareTwoPoints(t)) {
	t.adjacent.push(t1n);
	t1n.adjacent.push(t);
	}

	if(t2n.ShareTwoPoints(t)) {
	t.adjacent.push(t2n);
	t2n.adjacent.push(t);
	}
	}

	t1n.adjacent.push(t2n);
	t2n.adjacent.push(t1n);

	Triangles.remove(t1);
	t1.dead = true;
	Triangles.remove(t2);
	t2.dead = true;
	Triangles.push(t1n);
	Triangles.push(t2n);

	return [ t1n, t2n ];
	}

	var AddVertex = function(vertex) {
	var inside = null;
	var edge = null;

	for(var i = 0; i < Triangles.length; i++) {
	var t = Triangles[i];
	if(t.IsVertexInside(vertex)) {
	inside = t;
	}
	if(edge != null \|\| inside != null) {
	break;
	}
	}
	if(inside != null) {
	var newTriangles = inside.AddVertex(vertex);
	for(var i = 0; i < newTriangles.length; i++) {
	if(!newTriangles[i].dead) {
	CheckAndFlip(newTriangles[i]);
	}
	}
	}
	}

	var CheckAndFlip = function(t) {

	for(var i = 0; i < t.adjacent.length; i++) {
	var tt = t.adjacent[i];

	if(t.HasPointInCircle(tt)) {
	var newTriangles = Flip(t, tt);
	CheckAndFlip(newTriangles[0]);
	if(!newTriangles[1].dead) {
	CheckAndFlip(newTriangles[1]);
	}
	return;
	}
	}
	}

	var TogglePathability = function(vertex) {
	var triangle = GetTriangle(vertex);
	if(triangle !== null) {
	triangle.pathNode.TogglePathable();
	DrawTriangles();
	}
	}

	var Initialize = function() {

	Triangles = [];

	var t1 = new Triangle(TOPLEFT, TOPRIGHT, BOTTOMLEFT);
	var t2 = new Triangle(BOTTOMRIGHT, TOPRIGHT, BOTTOMLEFT);
	t1.adjacent.push(t2);
	t2.adjacent.push(t1);
	Triangles.push(t1);
	Triangles.push(t2);

	DrawTriangles();

	}

	window.onload = function() {
	Initialize();
	}

	</script>

	<style type="text/css">

	#mrcanvas {
	width: 800px;;
	height: 600px;
	}

	</style>


	</body>
	</html>