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

Javascript OOP – Advanced

In the previous post we looked at the basics of creating classes and objects in Javascript. In this article we will see how inheritance can be  implemented. To truly appreciate this, We have to understand few basics of what is a function semantically.  What exactly is happening when you declare a function as below

function Person(){
         this.myname = "Vineel";
};

Lets make use of chrome web inspector console to fully understand what is happening. Inside chrome press Control+Shift+j  to open Chrome web inspector.

Chrome Web inspector
Chrome Web inspector

Paste the above code into the inspector and call console.dir(Person) . This console.dir function is used to get the internals of the any Javascript object or function.

Function as Objects
Function as Objects

Pause for a while and take a look at the highlighted rectangle containing various properties. Function containing properties may seem confusing at first for people who have experience in other programming languages. This is not true with Javascript. Currently what you are looking at is syntactically a function but semantically an object of type Function. Yes, In javascript even the functions you declare are just syntactic sugar on top of underlying Function objects. The properties that are shown in the Chrome inspector are nothing but the properties of the Function object created.

Function Internals
Function Internals

The most important properties of the above are the prototype and __proto__ These are the core for the current topic of interest.

Prototype

prototype  is the link to the Person class’s prototype(template). So if we create a function with Person as its name, Then Person.prototype  contains the template of how a Person will be. Note prototype does not include any of the properties(myname, work) that we declared in the Person function. The reason for this is every property that we declared gets created on the fly when the object of the function is created or when you run the Person() as a function. But since every prototype is an object it contains two important properties

  1. constructor
  2. __proto__
Object Constructor
Object Constructor
Function Prototype Internals
Function Prototype Internals

constructor property just acts as self pointer to Person function(cycle – try expanding constructor and then its prototype soon…) like a self pointer in C structures. __proto__ property acts like a pointer to its parent object which in this case is Object.  This __proto__ is the key for establish inheritance hierarchy.

Inheritance the Javascript way

Let us assume a Employee class which need to be a subclass of a Person. First declare both the classes separately as shown below.

function Person(){
	this.name = "Vineel";
	this.work = function(){
		console.log("Yes I work...");
	};
};
function Employee(){ };
Person & Employee
Person & Employee

Now what happens if we do the following

Employee.prototype = new Person();
Employee Hierarchy Hijacked
Employee Hierarchy Hijacked

The default object hierarchy Employee is hijacked with Person hierarchy. Isn’t this inheritance? Yes ofcourse – but only after few other modifications.
Firstly the contructor of the Employee got overwritten by Person object. So we need to patch it up as below.

Employee.prototype.constructor = Employee;

Once this inheritance link is established, Only then we need to declare any additional methods specific to Employee as shown below

Employee.prototype.salary = 10000;
Employee.prototype.printTotalWorkHours = function(){
      console.log("I work... "+ 24*7);
};

This is Javascript way of doing inheritance. There are many different ways in which we can achieve inheritance. This method of simulating inheritance with prototypes is called as  Prototypical Inheritance.

What happens when Employee object is created?

When you create a new Employee object using the new operator, Then we get a real object which contains the properties and methods that we have declared. Now when the hijacked Employee object is created, The internals of the object will be as shown below

Final Employee & Person Hierarchy
Final Employee & Person Hierarchy

__proto__ acts as an invisible link that makes inheritance possible. The methods of Person class can be accessed directly without the __proto__ link from the Employee. Note use of __proto__ directly is not recommended, Because it is implementation dependent and have some caveats.

Javascript object internals

Javascript Object Internals
Javascript Object Internals

The above picture gives complete rundown of how the connections are made between various objects involved before and after Object creation. The inheritance mechanism in Javascript is very flaky.  Things get very slippery when we start playing with multiple objects and multi level inheritances etc.

So the basic thing to remember for creating inheritance in Javascript is to play mindful with prototype object.

Hope this article helped in understanding the Javascript OOP internals better.

References:

  1. Douglas Crockford: “Advanced JavaScript” (1 of 3) (Google)
  2. Douglas Crockford: “Advanced JavaScript” (2 of 3) (Google)
  3. Douglas Crockford: “Advanced JavaScript” (3 of 3) (Google)
  4. Learning JavaScript Design Patterns By Addy Osmani
  5. http://stackoverflow.com/questions/4012998/what-it-the-significance-of-the-javascript-constructor-property

Javascript OOP – Basics

Javascript is by far the most misunderstood language ever created. It was the language created for scripting web pages to provide very basic interaction to the user. But with the advent of  very powerful javascript engines in all modern browsers, The landscape for creating rich internet applications increased almost exponentially and the true gems of language came into limelight.  Douglas Crockford a well known Javascript guru describes the salient features of language here and he call the language as

The World’s Most Misunderstood Programming Language

In this article I am trying to revisit the object oriented programming capabilities of the language. Most of the readers who are already familiar with OOP concepts with either C++ or Java may have to unlearn everything they know about OOP and should approach Javascript with a clean mind! Believe me or not all the OOP concepts in Javascript are modeled just with one keyword the function. The beauty of the language is appreciated only when you start realizing the language capabilities which combines concepts from functional programming and object oriented paradigm almost seamlessly.

Ok lets get started. Readers who are not familiar with the basics of the language can refer the link 1 in the reference section at the end of the article.

Class And Object Creation

Unlike most OOP languages javascript doesn’t have a separate keyword for creating a class. Like I said before it reuses the function keyword.

var Person = function(){
};

This is how you create a class in javascript. May seem exactly same as how a function is declared. Yes of course, In javascript classes are modelled with functions. The difference comes when you instantiate a class into object.

//invokes the function
Person();

/* creates an object of type Person and
invoke the function of the instantiated object */
new Person();

Currently the Person class doesn’t have any useful stuff to play with so lets add some members and methods to it.

var Person = function(){
	//This is how we declare members of a class
	this.age = 26;
	//This is how we declare a methods of a class
	this.printAge = function(){
		console.log('Age is: '+this.age);
	};
};

this keyword has the usual meaning as in other programming language. It refers to the current object that is created. There are some gotchas regarding the use of this though, We will get back to it later. If you observe closely both this.age and this.printAge  are variables but one points an integer object and other points to a function. In Javascript functions are used as first class citizens. Functions can be declared inside other functions, Functions can be assigned to variables, Functions can be passed returned from within the functions the list goes on and on.

There is another way of declaring the members of a class

var Person = function(){
};
//for the time being ignore what prototype is
Person.prototype.age = 26;
Person.prototype.printAge = function(){
	console.log('Age is: '+this.age);
};

Assessing object members

var vineel = new Person();

//this is how we access object variables and methods
vineel.age = 35;
vineel.printAge();

In the above code var  is the keyword used to create a variables(local). Also important to remember that when ever we access a member variable from a member function we need to use the this keyword before member variable. This can be observed in printAge function.

Private object members

Some properties like salary inside Person class may not have access to outside world. This can be achieved with the var  keyword.

var Person = function(){
	//This salary will be invisible outside the class
	var salary = 10000000;
	//Private helper function not visible outside the class
	var hike = function(){
		salary += 10000;
	};
	//functions with in the class can access the local members
	this.spend = function(){
		console.log('Spending.... '+salary);
		hike();
	};
};

var vineel = new Person();
//cannot access local members directly
vineel.salary; //undefined
vineel.hike(); //undefined
//print the salary
vineel.spend();

Basically var simulate public and private access modifier behaviour that is well known in other programming language.

Javascript is an interpreted language so all the properties that are declared inside the Person class are created only when you create an Object with new keyword or when you directly invoke Person as a function

Creating static members

Yet times many objects have to share a common data or a common method, This type of common data which is not associated with any one particular object but accessible to every one of the object is called static data. Following example will clearly illustrate the use case.

var Account = function(){
	this.balance = 200000;
	this.printBalance = function(){
		console.log('Balance.... ' + this.balance);
	};
};
//observe no prototype here
Account.MinimumBalance = 1000;
Account.PrintMinimumBalance = function(){
	console.log(Account.MinimumBalance);
}

Creating object constructors

Constructors are methods of the class which will be automatically called when the object is created. These are very helpful in providing the object a meaningful state.

var Person = function(name, age){
	//This simulates constructor functionality in other programming languages
	this.name = name;
	this.age = age;

	this.printName = function(){
		console.log('Name is: '+this.name);
	};

	this.printAge = function(){
		console.log('Age is: '+this.age);
	};
};

//This is how we pass information to the object being created
var vineel = new Person("vineel", 26);
var ram = new Person("ram", 34);

vineel.printName(); //prints "vineel"
ram.printName(); //prints "ram"

Gotchas with global variables

variable declared without a var statement or this statement are automatically hosted as global variables so in the following code

Global variables In Javascript
Global variables In Javascript

Every global function we create in the language is added to global namespace. This global namespace in every browser happens to be the window object. Hence even though we invoke a function like alert()  this actually refers to window.alert() similarly in step 1 above Person() refers to window.Person() 

Gotchas with this

//Use of this inside function declaration.
//Improper use can polute global namespace or
//May lead to undefined reference errors
var Person = function(age){
	//This is how we declare members of a class
	this.age = age;
};
var p1 = new Person(20);
// in the Person function this.age refers to p1 object age
var p2 = new Person(40);
// in the Person function this.age refers to p2 object age
Person(30);
// in the Person function this.age refers to global object age and this is associated with window object
// the last call polutes the global window object.
// we can verify this as below
console.log(window.age);// prints 30

We just touched the surface of the language from OOP standpoint. I would like to discuss inheritance and talk about prototypes and the internals of the inheritance in a follow up article.

References:

  1. Douglas Crockford: “The JavaScript Programming Language” (1 of 4)(Google)
  2. Douglas Crockford: “The JavaScript Programming Language” (2 of 4)(Google)
  3. Douglas Crockford: “The JavaScript Programming Language” (3 of 4)(Google)
  4. Douglas Crockford: “The JavaScript Programming Language” (4 of 4)(Google)
  5. https://developers.google.com/chrome-developer-tools/

Git revisited

  1. git add -u
    • Add all modified files into staging area.
  2. git commit -a
    • Automatically adds all tracked files  to staging area for committing
  3. git diff –staged
    • Diff the content already added to staging area( using git add command )
  4. git remote add <alias> <remote git repo location>
    • Makes a reference to the remote repository with the given name
    • Example: git remote add origin https://github.com/vineel567/project123.git
    • orgin acts as an alias to the remote repository
  5. git remote -v
    • List all remote repositories aliased
    • Example: git remote -v
    • origin  https://github.com/vineel567/project123.git (fetch)
    • origin  https://github.com/vineel567/project123.git (push)
  6. git fetch <remote alias>
    • Fetches the remote repo to local but does not merge on to the current branch, Instead creates a new remote tracking branch
    • git br -a  will show all the remote branches in red color
      • * master
        remotes/origin/master
    • git remote show <remote alias> will show the info of all the remote and local branches with respect to the remote repo.
      • * remote origin
        Fetch URL: https://github.com/vineel567/project123.git
        Push URL: https://github.com/vineel567/project123.git
        HEAD branch: master
        Remote branch:
        master                tracked
        Local ref configured for ‘git push’:
        master pushes to master (local out of date)
  7. git pull <remote alias> <remote branch>
    • Fetches the remote repo to local and also merges onto the current branch, Also creates a new remote tracking branch
    • git br -a  will show all the remote branches in red color
      • * master
      • remotes/origin/master
    • git log will show the detailed commits recreated after the pull
  8. git push <remote alias> <branch>
    • Find a ref that matches <branch> in the source repository (most likely, it would find refs/heads/master), and update the same ref (e.g. refs/heads/master) in <remote alias> repository with it. If <branch> did not exist remotely, it would be created.

References: http://gitref.org/