Madking's Musings: JavaScript Drawing Program

I have decided to create a simple drawing program in JavaScript. My goal is to provide a simple <draw straight lines on graph paper> application. I won't support curves, line styles, or colors. I would like to support erase and undo/redo. All points will be automatically snapped to lattice points. My vision is that you'll start with a piece of graph paper (i.e. a light blue grid). You should be able to click on two points to create a line. It would be nice if it showed you what you were about to draw before you draw it. i.e. this should be just like many other drawing program, just with less features.

If you don't want to read any of the details, jump to the bottom and see the end result.

Implementation Highlights

HTML 5 provides this nice tag, <canvas>, which looks very useful for drawing. Every modern browser, except Internet Explorer, seems to support it including the Android and iPhone mobile devices. Since I am writing this for myself, I am ok with IE not being supported.

I see this app as having 3 layers. The bottom layer is the grid. The middle layer is the actual drawing. The top layer is the control layer where it shows you what you are about to draw. It seems logical to me to implement this as 3 canvas instances that are all in the same location. I do this by putting all 3 canvas instance in the same div, and positioning them absolutely to the top left of this div. This seems to do the trick, as when I play with it, all 3 are superimposed and drawing on a higher layer covers the lower layer, and erasing the higher layer reshows the lower layer.

  1 <html> 
  2   <head> 
  3     <style> 
  4 #windowcontainer {position:relative; height:400px;}
  5 .gridLayer {position: absolute; top: 0px; left: 0px;}
  6     </style> 
  7     <script> 
  8 // javascript code goes here 
  9     </script> 
 10   </head> 
 11   <body>  
 12     <div id='windowContainer'>  
 13       <canvas id="gridLayer" class="gridLayer" height="400" width="600"></canvas> 
 14       <canvas id="drawLayer" class="gridLayer" height="400" width="600"></canvas> 
 15       <canvas id="controlLayer" class="gridLayer" height="400" width="600"></canvas> 
 16     </div> 
 17   </body> 
 18 </html>

Now I create 3 classes, one for handling each layer. The Grid knows how to map between browser coordinates and lattice coordinates, as well as how to draw itself. The DrawingRecord knows how to draw lines and keeps track of all of the lines that have been drawn. The ControLayer actually registers the mouse listeners and determines when lines should be drawn, delegating functionality to the other two objects when appropriate.

  1 function Grid(canvas, width, height) { 
  2   this.ctx = canvas.getContext('2d');
  3   this.width = width; 
  4   this.height = height; 
  5 } 
  6 Grid.prototype.color = "#00FFFF"; 
  7 Grid.prototype.size = 25; 
  8 Grid.prototype.offsetX = 10; 
  9 Grid.prototype.offsetY = 10; 
 10 Grid.prototype.draw = function(){ /* implementation */ }
 11 Grid.prototype.getLatticePoint = function(x, y){ /* implementation */ }
 12 Grid.prototype.getReal = function(latticePoint){ /* implementation */ }
 13  
 14 function DrawingRecord(canvas, grid){ 
 15   this.canvas = canvas; 
 16   this.ctx = canvas.getContext('2d');
 17   this.grid = grid; 
 18   this.lines = {}; 
 19   this.nextLine = 0;
 20 } 
 21 DrawingRecord.prototype.addLine = function(p1, p2){ /* implementation */ }
 22 DrawingRecord.prototype.eraseLine = function(p1, p2){ /* implementation */ }
 23 DrawingRecord.prototype.draw = function(){ /* implementation */ }
 24 DrawingRecord.prototype.reset = function() { /* implementation */ }
 25  
 26 function ControlLayer(canvas, grid, drawRecord){
 27   this.ctx = canvas.getContext('2d');
 28   this.canvas = canvas; 
 29   this.grid = grid; 
 30   this.drawRecord = drawRecord; 
 31 } 
 32 ControlLayer.prototype.drawTempLine = function(){ /* implementation */ }
 33 ControlLayer.prototype.click = function(e){ /* implementation */ }
 34 ControlLayer.prototype.onmousemove = function(e){ /* implementation */ }
 35 ControlLayer.prototype.registerMouse = function(){
 36   var self = this;
 37   this.canvas.addEventListener("click", 
 38                    function(e){ self.click(e); }, 
 39                    false); 
 40   this.canvas.onmousemove = function(e){ self.onmousemove(e); }
 41 }

You can see one interesting JavaScript thing that I learned in the registerMouse method in lines 36-40. I create a self variable which is the same as this. If I don't do this, when canvas.onmousemove is called, the this object will refer to the canvas not the ControlLayer, since it is canvas's onmousemove that is being called. Since I don't actually want an infinite loop, I can't do this. By creating a local 'self' variable I make it a free variable (if I am using the closure terminology correctly) which will refer to this ControlLayer object for all time.

Erasing Lines

Erasing a line segment was more complicated than I had first hoped. It turns out that there doesn't seem to be a "clearLine" method in the canvas context. So, to accomplish an erase I do something like:

Remove the line segment from the list of lines that have been drawn

For each existing line segments

If it doesn't overlap with the erase line segment go to next segment
Remove the existing line segment.
Determine if the overlap if full or partial, and if partial, add the shorter new line segment(s) back to the list.

Clear the drawing layer
Redraw all of the existing line segments

Undo/Redo

An undo feature is always really nice to have, and I once read (I don't remember where) about a project where it was a real pain to retrofit it in after the fact. So undo/redo is one of the first features I am writing. Logically, what I have is a stack of actions. Undo moves us down the stack and redo moves us back up. Since functions are first class objects, it is easy to store them on the stack. Redo is easy, as I just run the command again. But what about undo? My first thought was to have undo just do the inverse function, so if the action was drawLine, then undo would eraseLine. Unfortunately eraseLine isn't actually the opposite of drawLine, as I'll show.

Imagine I draw a horizontal line on the x-axis from 1 to 4. Now I draw a second line from 3 to 6. When I undo, if I erase from 3 to 6, I'll have erased too much. I really want to only erase from 4 to 6 so I don't erase any of the first line.

With some work, I could actually determine the real inverse action, and I may still need to do that. However, a much simpler, though more computationally expensive, idea occurred to me. If a user has done actions 0 through N, and then does an Undo, rather than try to reverse step N, just clear the state and then replay actions 0 through N-1. This feels wasteful, but if I turn off drawing while doing this, this is just replaying a bunch of simple calculations which will happen really quick (assuming we aren't talking millions of steps - but if you are doing that much work, this toy drawing program is not for you), and then I can just do a single draw of the final state. i.e. something like:

  1 function UndoStack(draw){ 
  2   this.stack = []; 
  3   this.maxCmds = 0;
  4   this.curCmd = 0;
  5   this.draw = draw; 
  6 } 
  7 UndoStack.prototype.add = function(cmd) { 
  8   this.stack[this.curCmd++] = cmd;
  9   this.maxCmds = this.curCmd;
 10 } 
 11 UndoStack.prototype.undo = function(){ 
 12   this.draw.reset(); 
 13   this.draw.dontDraw = true;
 14   this.curCmd--; 
 15   for (var i = 0; i < this.curCmd; i++) {
 16     this.stack[i](); 
 17   } 
 18   this.draw.dontDraw = false;
 19   this.draw.draw(); 
 20 } 
 21 UndoStack.prototype.redo = function(){ 
 22   this.stack[this.curCmd++]();
 23 }

And the code in the ControlLayer looks like

  1 var p1 = this.firstPoint;
  2 var p2 = this.currentPoint;
  3 var drawRecord = this.drawRecord;
  4 var drawFunc = this.erase ? drawRecord.eraseLine 
  5                           : drawRecord.addLine; 
  6 var func; 
  7 if (this.rect) { // draw all 4 sides of rectangle as one action
  8   func = function(){ 
  9     drawFunc.call(drawRecord, p1, new Point(p2.x, p1.y));
 10     drawFunc.call(drawRecord, p1, new Point(p1.x, p2.y));
 11     drawFunc.call(drawRecord, p2, new Point(p2.x, p1.y));
 12     drawFunc.call(drawRecord, p2, new Point(p1.x, p2.y));
 13   } 
 14 } else { 
 15   func = function(){drawFunc.call(drawRecord, p1, p2);}
 16 } 
 17 func(); 
 18 this.undoStack.add(func);

Geometry
Computation geometry problems are a set of problems that always seem to bite me in programming contests. So I tried to keep things simple and created a couple of helper classes.

Point
I created a Point class, which just has an x and y coordinate and the ability to compare points with Fortran style methods .lt, .ge, .eq, etc. My definition of ordering is, Point A is less than Point B iff A.x < B.x OR (A.x == B.x AND A.y < B.y). This definition provides the expected ordering of points that are collinear which is useful when calculating line overlaps.

Line
My Line class is just two points, p1 and p2. For simplicity, I ensure that p1 < p2. I also store a slope object of the line which is just a rise and a run. The slope is canonicalized so that rise and run are in lowest terms, and that run is nonnegative.

  1 function Slope(p1, p2) { 
  2   var rise = p1.y - p2.y; 
  3   var run = p1.x - p2.x; 
  4   var gcd = Slope.gcd(Math.abs(rise), Math.abs(run));
  5   rise /= gcd; 
  6   run /= gcd; 
  7   if (run < 0) {
  8     rise *= -1; 
  9     run *= -1; 
 10   } else if (run == 0) {
 11     rise = 1; 
 12   } 
 13   this.rise = rise; 
 14   this.run = run; 
 15 }

I can now determine if two lines overlap by seeing if they are collinear

  1 Line.prototype.collinear = function(line) {
  2   if (!this.slope.eq(line.slope)) return false;
  3   if (!this.p1.eq(line.p1) &&
  4       !this.slope.eq(new Line(this.p1, line.p1).slope)) return false;
  5   return true;
  6 }

and if their endpoints overlap.

  1 Line.prototype.overlaps = function(line) {
  2   return this.collinear(line) &&
  3          this.p1.lt(line.p2) && this.p2.gt(line.p1);
  4 }

Demo
And here is what the end product looks like, at least if you are using a compatible browser. Feel free to view the source and see all the code that I left out of the examples above, if you are at all curious.

Madking's Musings

Sunday, August 29, 2010

JavaScript Drawing Program

No comments: