We’ve recently had to create a maintenance site which allows a user to specify several arbitrary polygons, over the top of an image. Various features needed to be included within this site, such as the ability to upload images, add some text and a name to it, but two features stood out as being complicated and different.
The first was this arbitrary polygon creation. HTML and javascript traditionally have had no way to draw lines, at arbitrary angles, on the page. Luckily since the advent of HTML5 and the canvas element we have a way to draw what ever we want, wherever we want, as long as it’s inside the canvas. If you’ve ever seen any code in methods that draw things on forms, or applets, or apps, then you’d probably be familiar with the concept of getting a drawing context, setting properties such as line colour, thickness etc, moving to a position within that context, and drawing lines, curves and shapes at various places.
This is the javascript code required to draw some shapes on a canvass. Fairly familiar stuff for those that have ever painted on a windows form or iPhone view:
var c = document.getElementById(“myCanvas”).getContext(‘2d’);
//A 10px by 10px square
c.globalAlpha = 1;
c.beginPath();
c.strokeStyle = “#000”;
c.moveTo(10, 10);
c.lineTo(20, 10);
c.lineTo(20, 20);
c.lineTo(10, 20);
c.closePath();
c.stroke();
//A 10px radius circle
c.beginPath();
c.strokeStyle = “#000”;
c.arc(15, 15, 10, 0, Math.PI * 2, true);
c.closePath();
c.stroke();
So I attached some event handlers to the canvas, which would respond to clicks, place points stored in an array in memory, and join up the dots in a redrawCanvas() function which I wrote. The drawing of the canvas is appreciably fast in Google Chrome, so I put in highlighting of corners, when the mouse hovers over them, into the redrawCanvas code. Dragging of corners is done by simply altering the in memory coordinates of a corner, on every mouse move event while the button is held down, then calling a redraw. A few other features I added include deleting a corner, by simply removing the highlighted corner in the array, then calling a redraw, and spliting a side up by adding in a corner halfway along the edge. All in all a relatively simple and elegant solution to the problem.
The second feature that was required involved a fair amount of Maths research, trigonometry and brain aching. The requirement was to place text inside one of these arbitrary polygons, in a nearly optimal way, so that we could place the text with largest font in one of four directions, horizontally (left to right), vertically (top to bottom), diagonally (From bottom left to top right) and another diagonally (From top left to bottom right). The first step to solving this was to simplify the problem by finding the largest rectangle that fitted inside the polygon. After lots of head scratching and research on various sites like http://math.stackexchange.com it appeared like the solution was going to have to be a brute force approach. This was not going to be a particularly quick algorithm as it would need to take a list of points in a grid, check if the point was inside the polygon, create 4 rectangles from that point, checking all four corners were inside the polygon, compare the area of each rectangle to the current largest and repeat for each rectangle in each of the 4 directions, for each point inside the polygon. This is a solution for which the time taken to solve, increases exponentially with the area of the polygon, not great in a web browser where the single threaded environment causes the UI to lock while it’s processing. Enter Web Workers, the Javascript solution to multi threadedness. The basic concept of a Web Worker is to have a separate piece of JS code, which is passed messages and can pass back messages to the calling thread. The code to create the largest rectangle was taken out to a separate file, and executed using the Web Worker paradigm, responding with a JSON object describing the largest rectangle for the polygon when it had finished. Each call to check each rectangle is done in its own thread, this way the UI was free to be updated while it waited asynchronously for the Web Worker to finish its job. The process itself is no quicker but doesn’t cause the browser to prompt about long running functions, and even in chrome which is notorious for being unresponsive with lengthy javascript processes running, responds just like nothing was happening.
