How to determine if the point is inside an arbitrary shape

HTML5 CanvasIn many graphics applications it so happens almost all the times we have to determine whether a given point is inside an arbitrary shape or not. Recently when I am playing with HTML5 Canvas element, I stumbled up on the same problem. After googling for a while and referring to old school maths lead to solutions which specifically dealt with only well defined shapes(Rectangle, Polygon) and didn’t provided a generic solution(Arbitrary shapes). At the same time I am also playing around with a Javascript  canvas library called KineticJS, After grokking for a while with its source code I found a pretty clever and neat solution to the above problem. Now this article will illustrate the solution step by step.

CanvasGenerally whenever we work with graphics applications we will have a surface onto which all the graphics work will go. We call this surface the ‘Canvas‘.  Beginners new to graphics straight away work with this canvas by drawing different shapes, without ever thinking about the solution to the above problem. Once they encounter the problem they will have no idea what to do and occasionally fall back to some clumsy workarounds. This is what initially happened to me. As I said earlier, KineticJS showed me a whole new way of thinking the solution to the problem.

So following is the reiteration of the problem in terms of my work.

My Work
My Work

Currently there are two resistors on the canvas, Each of the resistor is bounded by an invisible rectangle. Make no mistake the bounding rectangles will not be parallel to any axis. Now my job is to find whether or not a point(user mouse click) fall inside the bounding rectangle. Instead of mathematically finding the solution to the problem by applying complex Analytic geometry techniques, What we do is maintain an invisible canvas which is of same size as this visible canvas.  Now following steps will explain the technique in detail.

  1. Step up the visible canvas to the required dimensions and positions in the HTML page (as shown below)
  2. Similarly step up a secondary hidden canvas with the same dimensions and position in the HTML page(as shown below)
    • <div style="position:relative;">
      <canvas id="c" width="1850" height="1050" draggable="false" style="position:absolute;top:0;left:0">
      </canvas>
      <canvas id="cHiddenCanvas" width="1850" height="1050" top="0" left="0" style="display:none;position:absolute;z-index:-1"></canvas></div>
      
  3. Whenever an arbitrary object is drawn to the original canvas we assign a random color to it.
    • Suppose we want draw an object, Assign a unique color(Say colorKey #RGB) let #120351 to it.
    • The color acts as a key to identify the object later. This does not interfere with actual objects look and feel. Its just a hidden attribute
  4. Now draw the same object to the hidden canvas, But fill the object with the color we have chosen.
  5. So effectively the visible canvas contains the actual shape and the hidden canvas contains the same shape with the color filled.
  6. Now to determine whether a point(mouse click) belong to that shape we do the following.
    • Get the point coordinates (X, Y) in the visible canvas (captured from event.clientX, event.clientY)
    • Get the same points pixel color in hidden canvas(as shown below)
    • //Get one pixel data of the point
      var pixel = hiddenCanvasContext.getImageData(point.x, point.y, 1, 1).data;
      //Convert the pixel array into HTML color string to obtain #120351
      var pixelColor = '#' + (((1 << 24) + (pixel[0] << 16) + (pixel[1] << 8) + pixel[2]).toString(16).slice(1));
      
    • Now determine for all the objects in the visible canvas which one has this color as its colorKey. The one matching with this color is the object on which the point fall on. If no object colorKey matches then the point lies outside of all the objects. Isn’t it neat? Pretty!
  7. Note: We take it granted that the color generated is unique for each object and use the following function to generate a random color everytime
    • 	this.getRandomColor = function() {
      		var randColor = (Math.random() * 0xFFFFFF << 0).toString(16);
      		while (randColor.length < 6) {
      			randColor = '0' + randColor;
      		}
      		return '#' + randColor;
      	};
      

Following image shows the layout of the page with hidden canvas

Visible & Hidden Canvases
Visible & Hidden Canvases

Now lets look at the page with visible canvas turned on(display: none disabled)

Overlap of Visible & Hidden Canvases
Overlap of Visible & Hidden Canvases

As clear from the picture above once we disable the display:none attribute on the hidden canvas we can see what is going on behind the visible canvas. The colored bounding rectangles are from the hidden canvas. They are drawn and modified hand in hand with the objects in the visible canvas. The key for this technique to work is the colorKey that bind both of these layer together object by object.

Reference:

Random Function Code: https://github.com/ericdrowell/KineticJS/blob/master/src/Util.js#L556
Point Verification COde: https://github.com/ericdrowell/KineticJS/blob/master/src/Layer.js#L22

Leave a comment

Leave a Reply