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/

Basics of DOM

Document Object Model abbriveated as DOM is the single most important API that sits under the hood of every webpage. It is the mechanics of your webpage. To understand what it is and how to work with it lets look at a simple html page with  a body and two div tags

The above code is rendered as shown belowBut when the page is loaded in to a browser, the broswer creates the following structure as its internal representationDOM Structure

Each of the box in the above tree representation is called as a node or element. Every node is a JavaScript DOM object. This internal representation is the bread and butter to manipulate the structure of the webpage and to provide webpage interactivity. It helps the developer to access the contents of the webpage and manipulate them. We shall see in the following section exactly how we do this. Interactivity to a webpage is achieved in two steps

  1. Selecting the node
  2. Manipulating the selected node using its properties and methods

DOM NODE SELECTION

Each node in the above tree can be accessed in three ways using JavaScript supported functions.

  1. document.getElementById
  2. document.getElementsByTagName
  3. document.getElementsByClassName
First method takes id of an element as a string and returns the DOM Object  of the element corresponding with that id. This function returns only one element because id is considered to be unique for every element.
The usage is as shown below
var div = document.getElementById("div1"); //return DOM object for element with id 'div1'
console.log(div); //output the html node
the output in chrome inspector 
The other two methods take tag name , class name respectively. They return an array of nodes matching the tag or class name. The usage is as shown below
var div = document.getElementsByTagName("div"); //select all div tags
console.log(div); //output the array

output in chrome inspector

now the output has two div tags in the array.

DOM TREE TERMINOLOGY

Assume we have selected the first div node then the following picture illustrates the terminology used and the respective DOM properties to access the depicted nodes

DOM TREE NAVIGATION

Using the following properties we can navigate the entire DOM tree

DOM Property Description Examples
firstChild/firstElementChild First child node descending the selected node if your html tags are interleaved with newlines as shown in the code then firstChild may return Text Node corresponding to that new line, so in that case instead of firstChild use firstElementChild
lastChild/lastElementChild Last child node descending the selected node
parentNode Parent of the selected node
nextSibling/nextElementSibling Node that is to the right of the selected node
previousSibling/previousElementSibling Node that is to the left of the selected node
innerText Returns the text side the selected node. If node contains any other html nodes, the returned text contains only text exclusing those tags So for <div> text1 <i>  itext </i> text2 </div> the returned text is “text1 itext text2”
innerHTML Returns the HTML code inside the selected node So for <div> text1 <i>  itext </i> text2 </div> the returned text is “text1 <i>itext</i> text2”

example, say we have selected the first div node then

var div = document.getElementById(&quot;div1&quot;);
var parentNode = div.parentNode; // this returns the dom reference to body tag

METHODS TO MANIPULATE NODE ATTRIBUTES

The following methods are used to manipulate the attribute of each node( HTML attributes )

DOM Method Description
getAttribute Returns the attribute value of the given attribute of the selected node
setAttribute Sets the attribute value of the given attribute of the selected node
removeAttribute Removes the specified attribute of the selected node

METHODS TO MANIPULATE NODES

The following methods are used to manipulate the nodes. Like creating new nodes, deleting existing onces in the DOM Tree etc

DOM Method Description
createTextNode Creates a DOM Text Node
insertBefore Inserts before the given node(not selected node)
appendChild Inserts as a last child node to the selected node
removeChild Deletes the node from the DOM Tree

This article is by no means comprehensive, To get a better understanding of above concepts refer

  1. JavaScript Definitive Guide – David Flanagan
  2. Mozilla Developer Network
  3. DOM Reference

Using Chrome’s web inspector as a calculator

chromeEvery version of chrome comes with a built in JavaScript inspector(activated by pressing Shift+Ctrl+J ). This is basically a debugger for your web application. It has pretty much everything that a normal debugger has for other languages like C, Java. So in this post I will show you how to use this inspector as general purpose calculator.
Once you open the inspector click on console tab to get an interactive prompt with > symbol. This is a full featured JavaScript interpreter, So the possibility of playing with this prompt are endless. But lets constrain our self to using it as a basic calculator(In a future post I will demonstrate more advanced uses).

First, doing basic arithmetic operations as shown below

Next, lets try converting a number from decimal to different bases (that ‘var n’ statement is required). The ‘toString(base)’ method can be invoked on any number and it takes the parameter base to which the actual number should be converted. In the first case it is evident that I am converting from decimal to binary format, then to octal and hexadecimal.

Next, Converting from other bases to decimal. The ‘parseInt(string,base)’ method takes a number in string format and converts it to the specified base 

Next, Converting from one base to other is a two step process

  1. convert from <any> base to decimal using parseInt method
  2. convert from decimal to <any> other base

Taking it a step further, we can type any valid JavaScript program at the prompt. Hope this is the start of your JavaScript journey!!

My first google chrome extension

Have you ever visited Indian railway PNR status enquiry page. Truth be told its a UX disaster.

Why I hate it

  1. Don’t know why they splited PNR in to 2 parts and provided 2 text fields to enter. Basic principle in user interface design – Keep It Simple Stupid
  2. Even before we enter the 10 digit PNR we get almost 2-3 popup(if u r lucky!!!)
Digging to solve the problem led me to write a chrome extension.
So a clean solution to those who are using google chrome.
  1. Make those two fields in to one
  2. No popups – I know what to enter 😉
here is before extension
here is after chrome extension

Here is the complete extension code: https://github.com/vineelkovvuri/pnrfix

UPDATE(Sun Mar 06 2016 16:27:57 IST): The website is now fixed properly :)

The Anatomy of Information Technology

The title is ‘The Anatomy of Computer Science Information Technology’ and I would like to talk about it in-general from technical point of view. As being an Information Technology graduate its always good to know what it is. Many people often ask me following questions
  1. “What is JQuery ? Is it mandatory to learn JavaScript to use JQuery?”
  2. “What is Win32 Api ? Can I develop sneeky GUI interfaces in it?”
  3. “In which language this piece of software might have been created?”
  4. “How do we create such effects in web pages? Is it done is photoshop or dreamweaver?”
  5. “What technology is right for particular task?”
  6. “How to write a virus program in Java?” 
  7. “bla……bla……e.t.c”
Though I may not give all the answers to the above questions in this article, but I am particularly excited to present you how we can classify various technologies that exist in todays market and their pros and cons.
The classification was done based on the platform and the type of development we do to accomplish the task.
Fundamentals are always important, today though we have ever growing gigantic frameworks to help us, Its always good to be aware of how the same task can be done without those frameworks. This is particularly true with JQuery. JQuery is an extension library to JavaScript. It only contains some easier functions to help program mundane JavaScript tasks. Though I don’t recommend you to be a black belt in JavaScript its good to know what it is and its +ves and -ves.
Get to know what is what with all the technologies. If you look at 4th question first of all we should know what will be done with photoshop and dream weaver. Then the answer is simple.
Choosing the right technology and tools plays an important role in fulfilling the task. If you look at the 6th question, small viruses can be written in Java but it is not the right one to choose, Because Java wont help us in querying low level system details(what are all the processes running on the current machine? Injecting malicious code in to winlogon process e.t.c)
Similarly Win32 api is a collection of low level windows system functions mainly suitable for writing windows drivers, Even though we can create GUI with it its not cake walk to code sneeky GUI interfaces like Windows Media Player, Kaspersky e.t.c in it.
I have not considered some of the technologies data exchange formats like XML, JSON e.t.c and ignored the description of all the software involved in the development process like Netbeans,Eclipse,Visual Studio,Tomcat,JBoss e.t.c

The above discussion is completely my own opinions and understandings. Please correct me If I was wrong. Please comment to the post if you have any queries related to a particular technology.

CSS selectors 101

This time I want to give glimpse of CSS(Cascading style sheets)
Before I jump in to CSS its better to know what comprises a web page. Basically any moderate web page is composed of 3 technologies.

  1. HTML – Content
  2. JavaScript – Behavior
  3. CSS – Presentation

Read on →