Sunday, January 6, 2013

Draw a Line with the Exact Real-world Length on Screen



Introduction

I played an educational game which teaches kids how to use a ruler to draw and measure a straight line. However, the unit length of the ruler widget on the computer does not equal to the actual length in the real world. For example, if you use the ruler widget to draw a 2 cm line, and then use a real ruler to measure it on the screen, the length is normally much greater than 2 cm. Although the game is for educational purpose and it is acceptable not to strictly follow the real length, it would be better if we can provide some ruler widget that has the same unit length with the real world ruler. Therefore, the problem we are trying to solve in this article is: Draw a  line with length of 1 centimeter on the computer screen, regardless of the screen’s physical size and  configurations, such as resolutions, orientation, etc.
  

Solution

The math part of the solution is pretty simple. Suppose the screen resolution is 1680×1024 and the computer screen’s physical size is 47cm×30cm (a typical 22-inch display), then horizontally, there are 1680/47 pixels per centimeter. Therefore, to draw a 1 cm line horizontally, we can just draw a line with 1680/47 pixels. The following is a C# code for the drawing part.

//Draw a horizontal line on the graphics g with color clr.
//The starting coordinate of the line defined in x, y.
//The length (in cm) of the line is defined in length.
//The screen's horizontal resolution (in pixels) is defined in horizoantalResolution
//The screen's physical width (in cm) is defined in screenWidth.
private void DrawHorizontalLine(Graphics g, Color clr, int x, int y, float length, int horizoantalResolution, int screenWidth)
{
   float pixelpercm = (float)horizoantalResolution / screenWidth;
   g.DrawLine(new Pen(new SolidBrush(clr), 1), x, y, x + length * pixelpercm, y);
}

It is easy to get the screen resolution in C#. The following code can get the resolution of the primary screen (a computer can connect to multiple screens).

int w = Screen.AllScreens[0].Bounds.Width;
int h = Screen.AllScreens[0].Bounds.Height;

It is a little bit hard to get the physical size of the computer screen. One technology we can use is to read the extended display identification data (EDID) of a connected display. The data structure of EDID can be found in the following Wikipedia page: http://en.wikipedia.org/wiki/Extended_display_identification_data . The display physical width and height are defined in the bytes 21 and 22 of EDID.

In Windows, the EDID are stored in the system registry under [HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Enum\DISPLAY\$DISPLAY_NAME\$DISPLAY_ID\Device Parameters], where $DISPLAY_NAME and $DISPLAY_ID are display specific strings. The following C# code example shows how to read the EDID from the registry and extract the physical size of the display from EDID. Note that there may exists more than one EDID entries if the computer has multiple displays connected. Also, we can read other display properties, such as model name, from EDID. Please refer to  http://en.wikipedia.org/wiki/Extended_display_identification_data on data format of EDID.

private void GetDisplays()
{
   RegistryKey key = Registry.LocalMachine.OpenSubKey("SYSTEM\\CurrentControlSet\\Enum\\DISPLAY");
   if (key == null)
      return;
   //sName is the display name
      foreach (string sName in key.GetSubKeyNames()) 
  { 
      if (sName == "Default_Monitor") 
         continue;
       RegistryKey keyDisplay = key.OpenSubKey(sName);
      //sDisplayID is the display ID
              foreach (string sDisplayID in keyDisplay.GetSubKeyNames())
      {
         RegistryKey keyDevice = keyDisplay.OpenSubKey(sDisplayID);
         if (keyDevice == null)
            continue;
         //sDriver is the display driver name
                    string  sDriver = (string)keyDevice.GetValue("Driver");
         RegistryKey keyParameter = keyDevice.OpenSubKey("Device Parameters");
         if (keyParameter == null)
         { 
            keyDevice.Close();
            continue;
         }
         byte[] EDID = (byte[])keyParameter.GetValue("EDID");
         keyParameter.Close();
         keyDevice.Close();
         if (EDID == null)
            continue;
         //Display's physical height and width
         int width = EDID[21];
         int height = EDID[22];
     }
     keyDisplay.Close();
   }
   key.Close();
}

Now we have enough information to draw a line, the screen resolution and the physical size of the screen. We can feed these parameters to the DrawHorizontalLine function.  Also it is not hard to extend the above horizontal solution to the vertical case or to the line with any slope.
   

Future Works 

  • The above solution is for Windows only. For other platforms, such as Mac, Linux, it should be pretty easy to get current screen's resolution. However, we need to do some more research on where EDID are stored in these platforms.
  • If the computer has multiple connected displays, we need extra code to determine in which display current application is running and then use the corresponding width and height parameters.
  • This solution is also useful for a new "Print Preview" feature, which can produce the preview exactly the same as what will be printed. Imagine the computer shows an A4 paper on the screen with the exact width and height as a real A4 paper, and all the content displayed on the paper has the same size as the content printed on a real A4 paper.
Posted by at No comments:
Labels: ,

Tuesday, January 1, 2013

C++ Code for Some Binary Tree Algorithms

The following C++ code contains several algorithms for binary tree operations.
  • Preorder tree traversal: recursive method; iterative method by using stack data structure; iterative method without stack, but by using a parent node in each tree node.
  • Inorder tree traversal: recursive method; iterative method by using stack data structure; iterative method without stack, but by using a parent node in each tree node.
  • Postorder tree traversal: recursive method; iterative method by using two stacks.
  • Depth first traversal: same as preorder tree traversal
  • Breadth first traversal: print the tree nodes level by level
  • Flattening traversal: flatten the binary tree to a singly linked list for traversal.
  • Encode/Decode a binary tree: Convert a binary tree to a formatted string or convert a formatted string to a binary tree.
  • Check if a binary tree is a binary search tree (BST)
  • Find the largest BST subtree of a binary tree
  • Binary search in a BST
  • Preorder search in a general binary tree
  • Find the lowest common ancestor (LCA) of two binary tree nodes
  • Build a binary tree from inorder and preorder traversal sequence

The tree structure definition is defined here (BinaryTree.h).



#pragma once
#include <string>
using namespace std;

typedef struct TreeNode
{
   TreeNode(int d)
   {
      data = d;
      left = NULL;
      right = NULL;
      parent = NULL;
   }
   int data;
   struct TreeNode *left;
   struct TreeNode *right;
   struct TreeNode *parent;
}
TreeNode;

class BinaryTree
{
public:
   BinaryTree();
   ~BinaryTree();
   void postorderRelease(TreeNode *node);

   void preorder();
   void inorder();
   void postorder();
   void depthFirst();
   void breadthFirst();
   void flatten();
   string encode();
   void decode(const string & s);
   bool isBST();
   TreeNode * binarySearch(int data);
   TreeNode * preorderSearch(TreeNode *node, int data);
   TreeNode * LCA(int data1, int data2);
   void buildFromInPreOrder(const vector<int> &inorder, const vector<int> &preorder);
private:
   void preorder(const TreeNode *node);
   void preorderIterative(const TreeNode *node);
   void preorderIterativeNoStack(const TreeNode *node);
   const TreeNode *preorderNext(const TreeNode *node);
   void inorder(const TreeNode *node);
   void inorderIterative(const TreeNode *node);
   void inorderIterativeNoStack(const TreeNode *node);
   const TreeNode *inorderNext(const TreeNode *node);
   void postorder(const TreeNode *node);
   void postorderIterative(const TreeNode *node);
   void preorderEncode(const TreeNode *node, string *encodeStr, vector<string> *data);
   TreeNode * preorderDecode(const string &encodeStr, const vector<int> &data, string::const_iterator &strItr, vector<int>::const_iterator &dataItr);
   bool isBST(const TreeNode *node, int *min, int *max);
   int BinaryTree::maxBST(TreeNode *node, int *min, int *max, TreeNode *&maxBSTRoot, int *maxBSTTotal);
   TreeNode * BSTLCA(int data1, int data2);
   TreeNode * LCA(TreeNode *rootNode, TreeNode *node1, TreeNode *node2);
   TreeNode * LCAIterative(TreeNode *rootNode, TreeNode *node1, TreeNode *node2);
   TreeNode * buildFromInPreOrder(const vector<int> &inorder, const vector<int> &preorder,
   int inorderStart, int inorderEnd, int preorderStart, int preorderEnd, map<int, int> &inorderMap);
private:
   TreeNode *root;
};
 

The source code is implemented here  (BinaryTree.cpp).



#include <iostream>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include "BinaryTree.h"

BinaryTree::BinaryTree()
{
   this->root = NULL;
}

BinaryTree::~BinaryTree()
{
   postorderRelease(root);
}

void BinaryTree::postorderRelease(TreeNode *node)
{
   if (node == NULL)
      return;
   postorderRelease(node->left);
   postorderRelease(node->right);
   delete node;
}

void BinaryTree::preorder()
{
   preorder(root);
   cout<<endl;
   preorderIterative(root);
   cout<<endl;
   preorderIterativeNoStack(root);
   cout<<endl;
}

void BinaryTree::inorder()
{
   inorder(root);
   cout<<endl;
   inorderIterative(root);
   cout<<endl;
   inorderIterativeNoStack(root);
   cout<<endl;
}

void BinaryTree::postorder()
{
   postorder(root);
   cout<<endl;
   postorderIterative(root);
   cout<<endl;
}

void BinaryTree::preorder(const TreeNode  *node)
{
   if (node == NULL)
      return;
   cout<<node->data<<" ";
    preorder(node->left);
    preorder(node->right);
}

void BinaryTree::inorder(const TreeNode  *node)
{
   if (node == NULL)
      return;
    inorder(node->left);
    cout<<node->data<<" ";
    inorder(node->right);
}

void BinaryTree::postorder(const TreeNode  *node)
{
   if (node == NULL)
      return;
    postorder(node->left);
    postorder(node->right);
    cout<<node->data<<" ";
}

void BinaryTree::preorderIterative(const TreeNode *node)
{
   if (node == NULL)
      return;
   stack<const TreeNode *> nodes;
   nodes.push(node);
   while (!nodes.empty())
   {
      const TreeNode *currentNode = nodes.top();
      cout<<currentNode->data<<" ";
      nodes.pop();
      if (currentNode->right)
         nodes.push(currentNode->right);
      if (currentNode->left)
         nodes.push(currentNode->left);
   }
}

//The next node of node X in the preorder sequence is:
// 1. X's left child if it is not NULL;
// 2. X's right child if it is not NULL;
// 3. The right child of the lowest ancester of node X whose left child is also the ancestor of node X and whose right child is not NULL.
// 4. NULL if we finished the search.
const TreeNode * BinaryTree::preorderNext(const TreeNode *node)
{
   if (node == NULL)
      return NULL;
   else if (node->left)
      return node->left;
   else if (node->right)
      return node->right;
   else
   {
      TreeNode *parent = node->parent;
      while (parent != NULL && (node == parent->right || parent->right == NULL))
      {
         node = parent;
         parent = parent->parent;
      }
      if (parent == NULL)
         return NULL;
      else
         return parent->right;
   }
}

//preorder traveral without using a stack. This method depends on the parent pointer
//of the tree node.
void BinaryTree::preorderIterativeNoStack(const TreeNode *node)
{
   while (node)
   {
      cout<<node->data<<" ";
      node = preorderNext(node);
   }
}

void BinaryTree::inorderIterative(const TreeNode *node)
{
   if (node == NULL)
      return;
   stack<const TreeNode *> nodes;
   const TreeNode *currentNode = node;
   while (true)
   {
      if (currentNode)
      {
         nodes.push(currentNode);
         currentNode = currentNode->left;
      }
      else
      {
         if (!nodes.empty())
         {
            currentNode = nodes.top();
            cout<<currentNode->data<<" ";
            nodes.pop();
            currentNode = currentNode->right;
         }
         else
         {
            return;
         }
      }
   }
}

//inorder traveral without using a stack. This method depends on the parent pointer
//of the tree node.
void BinaryTree::inorderIterativeNoStack(const TreeNode *node)
{
   if (node == NULL)
      return;
   while(node->left)
   {
      node = node->left;
   }
   while (node)
   {
      cout<<node->data<<" ";
      node = inorderNext(node);
   }
}

//The next node of node X in the inorder sequence is:
// 1. The left most node of X's right sub tree if X's right child is not NULL;
// 2. the lowest ancester of node X whose left child is also the ancestor of node X.
// 3. NULL if we finished the search.
const TreeNode * BinaryTree::inorderNext(const TreeNode *node)
{
   if (node == NULL)
      return NULL;
   else if (node->right)
   {
      node = node->right;
      while(node->left)
      {
         node = node->left;
      }
      return node;
   }
   else
   {
      TreeNode *parent = node->parent;
      while (parent != NULL && node != parent->left)
      {
         node = parent;
         parent = parent->parent;
      }
      return parent;
   }
}

void BinaryTree::postorderIterative(const TreeNode *node)
{
   if (node == NULL)
      return;
   stack<const TreeNode *> nodes;
   stack<const TreeNode *> outputs;
   nodes.push(node);
   while (!nodes.empty())
   {
      const TreeNode *currentNode = nodes.top();
      outputs.push(currentNode);
      nodes.pop();
      //push left children first
      if (currentNode->left)
         nodes.push(currentNode->left);
      if (currentNode->right)
         nodes.push(currentNode->right);
   }
   while (!outputs.empty())
   {
      cout<<outputs.top()->data<<" ";
      outputs.pop();
   }
}


void BinaryTree::depthFirst()
{
   //preorder is the same as the depthFirst search in graph
   preorder(root);
   cout<<endl;
}

//breadth first traveral, print the nodes level by level
void BinaryTree::breadthFirst()
{
   queue<TreeNode*> queue;
   queue.push(root);
   while (!queue.empty())
   {
      TreeNode *node = queue.front();
      cout<<node->data<<" ";
      queue.pop();
      if (node->left)
         queue.push(node->left);
      if (node->right)
         queue.push(node->right);
   }
   cout<<endl;
}

void BinaryTree::flatten()
{
    TreeNode *tail = root;
    while (tail->left)
   {
        tail=tail->left;
   }
   vector<TreeNode*> tails;
   tails.push_back(tail);
    TreeNode *node = root;
    while(node)
    {
      cout<<node->data<<" ";
        if (node->right)
      {
            tail->left = node->right;
            while(tail->left)
                tail=tail->left;
         tails.push_back(tail);
       }
        node=node->left;
    }
    //restore
    for (unsigned int i = 0; i < tails.size(); i++)
        tails[i]->left = NULL;
   cout<<endl;
}

//encode the binary tree to a string. We use "\n" as delimiter.
string BinaryTree::encode()
{
   vector<string> data;
   string encodeStr = "";
   preorderEncode(root, &encodeStr, &data);
   encodeStr += "\n";
   for (vector<string>::const_iterator itr = data.begin(); itr != data.end(); itr++)
   {
      encodeStr += *itr;
      encodeStr += "\n";
   }
   return encodeStr;
}

//use preorder traversal to encode the binary tree.
//We put extra "dummy" NULL nodes to each tree node so that the tree is a "complete" tree,
//i.e., each tree node has exactly two children (either a "real" tree node or a "dummy" node)
//In the encode string, if it is a tree node, the bit is set to 1,
//if it is a dummy NULL node (e.g. a leaf node has two dummy NULL child nodes), the bit is set to 0.
//Therefore, if the tree has n nodes, then we need 2n+1 bits to encode.
//data vector stores the node data in a preorder sequence.
//we use bit string to encode, i.e. "1110000". It is possible to use int array for a more compact storage.
void BinaryTree::preorderEncode(const TreeNode *node, string *encodeStr, vector<string> *data)
{
   if (data == NULL || encodeStr == NULL)
      throw std::exception();
   if (node == NULL)
   {
      *encodeStr += "0";
      return;
   }
   *encodeStr += "1";
   ostringstream convert; //convert int to string.
   convert<<node->data;
   data->push_back(convert.str());
   preorderEncode(node->left, encodeStr, data);
   preorderEncode(node->right, encodeStr, data);
}

void BinaryTree::decode(const string& s)
{
   vector<int> data;
   string encodeStr = "";
   unsigned int index = 0;
   string currentStr = "";
   while (index < s.length())
   {
      if (s[index]=='\n')
      {
         if (encodeStr.length() > 0)
         {
            int value = atoi(currentStr.c_str());
            data.push_back(value);
         }
         else
         {
            encodeStr = currentStr;
         }
         currentStr = "";
      }
      else
      {
         currentStr += s[index];
      }
      index++;
   }
   string::const_iterator strItr= encodeStr.begin();
   vector<int>::const_iterator dataItr = data.begin();
   root = preorderDecode(encodeStr, data, strItr, dataItr);
}

TreeNode * BinaryTree::preorderDecode(const string &encodeStr, const vector<int> &data, string::const_iterator &strItr, vector<int>::const_iterator &dataItr)
{
   if (strItr == encodeStr.end())
      throw std::exception();
   if (*strItr == '0')
   {
      strItr++;
      return NULL;
   }
   if (dataItr == data.end())
      throw std::exception();
   TreeNode *node = new TreeNode(*dataItr);
   dataItr++;
   strItr++;
   node->left = preorderDecode(encodeStr, data, strItr, dataItr);
   node->right = preorderDecode(encodeStr, data, strItr, dataItr);
   if (node->left)
      node->left->parent = node;
   if (node->right)
      node->right->parent = node;
   return node;
}

//check if a binary tree is a binary search tree (BST).
//for every node of a binary tree, if it satisfies:
//the max of its left sub tree <= node->data <= the min of its right sub tree.
//then it is a BST.
bool BinaryTree::isBST()
{
   int min, max;
   bool r = isBST(root, &min, &max);
   cout<<"min="<<min<<" max="<<max<<endl;

   TreeNode *maxBSTRoot = NULL;
   int maxBSTTotal = 0;
   int total = maxBST(root, &min, &max, maxBSTRoot, &maxBSTTotal);
   cout<<"min="<<min<<" max="<<max<<" total="<<maxBSTTotal<<" max BST root: "<<maxBSTRoot->data<<endl;

   return r;
}

bool BinaryTree::isBST(const TreeNode *node, int *min, int *max)
{
   if (node == NULL || min == NULL || max == NULL)
      return false;
   int leftMin = node->data;
   int leftMax = node->data;
   int rightMin = node->data;
   int rightMax = node->data;
   bool left = true;
   bool right = true;
   if (node->left)
      left = isBST(node->left, &leftMin, &leftMax);
   if (node->right)
      right = isBST(node->right, &rightMin, &rightMax);
   bool self = (leftMax <= node->data) && (node->data <= rightMin);
   *min = leftMin;
   *max = rightMax;
   return left && right && self;
}

//Find the largest subtree which is a BST.
//largest: the tree with largest number of nodes
//subtree: a part of the original tree whose leaf set is a subset of the original tree's leaf set.
int BinaryTree::maxBST(TreeNode *node, int *min, int *max, TreeNode *&maxBSTRoot, int *maxBSTTotal)
{
   if (node == NULL || min == NULL || max == NULL)
      return -1;
   int leftMin = node->data;
   int leftMax = node->data;
   int rightMin = node->data;
   int rightMax = node->data;
   int left = 0;
   int right = 0;
   if (node->left)
      left = maxBST(node->left, &leftMin, &leftMax, maxBSTRoot, maxBSTTotal);
   if (node->right)
      right = maxBST(node->right, &rightMin, &rightMax, maxBSTRoot, maxBSTTotal);
   bool self = (leftMax <= node->data) && (node->data <= rightMin);
   *min = leftMin;
   *max = rightMax;
   if (left >= 0 && right >= 0 && self)
   {
      int total = left + right + 1;
      if (total > *maxBSTTotal)
      {
         *maxBSTTotal = total;
         maxBSTRoot = node;
      }
      return total;
   }
   else
      return -1;
  
}

TreeNode * BinaryTree::binarySearch(int data)
{
   TreeNode *node = root;
   while (node)
   {
      if (node->data == data)
         break;
      else if (node->data > data)
         node = node->left;
      else
         node = node->right;
   }
   return node;
}

TreeNode * BinaryTree::preorderSearch(TreeNode *node, int data)
{
   if (node == NULL)
      return NULL;
   if (node->data == data)
      return node;
    TreeNode *left = preorderSearch(node->left, data);
   if (left)
      return left;
    TreeNode *right = preorderSearch(node->right, data);
   if (right)
      return right;
   return NULL;
}

TreeNode * BinaryTree::LCA(int data1, int data2)
{
   TreeNode* node = BSTLCA(data1, data2);
   cout<<node->data<<" ";
   return node;
}

//find the least common ancester(LCA) of two nodes in BST.
//the input parameters are two numbers.
//we assume the data in each tree node is unique.
TreeNode * BinaryTree::BSTLCA(int data1, int data2)
{
   TreeNode *node = root;
   while (node)
   {
      if (node->data >= data1 && node->data <= data2)
         break;
      else if (node->data > data2)
         node = node->left;
      else
         node = node->right;
   }
   return node;
}

//find the LCA of two nodes in a general binary tree.
//use bottom up approach.
TreeNode * BinaryTree::LCA(TreeNode *rootNode, TreeNode *node1, TreeNode *node2)
{
   if (rootNode == NULL) return NULL;
   if (rootNode == node1 || rootNode == node2)
      return rootNode;
   TreeNode *left = LCA(rootNode->left, node1, node2);
   TreeNode *right = LCA(rootNode->right, node1, node2);
   if (left && right)
      return rootNode;
   else if (left)
      return left;
   else
      return right;
}

//find the LCA of two nodes in a general binary tree.
//we assume the parent link exists in each tree node.
//________
//        \_________
//________/
//
TreeNode * BinaryTree::LCAIterative(TreeNode *rootNode, TreeNode *node1, TreeNode *node2)
{
   if (rootNode == NULL || node1 == NULL || node2 == NULL)
      return NULL;
   int count1 = 0;
   TreeNode *parent1 = node1;
   while (parent1 && parent1 != rootNode)
   {
      count1++;
      parent1 = parent1->parent;
   }
   int count2 = 0;
   TreeNode *parent2 = node2;
   while (parent2 && parent2 != rootNode)
   {
      count2++;
      parent2 = parent2->parent;
   }
   int offset = 0;
   parent1 = node1;
   parent2 = node2;
   if (count1 > count2)
   {
      offset = count1 - count2;
      while (offset > 0)
      {
         offset--;
         parent1 = parent1->parent;
      }
   }
   else
   {
      offset = count2 - count1;
      while (offset > 0)
      {
         offset--;
         parent2 = parent2->parent;
      }
   }
   while(parent1 != parent2 && parent1 && parent2)
   {
      parent1 = parent1->parent;
      parent2 = parent2->parent;
   }
   if (parent1 == NULL || parent2 == NULL)
      return NULL;
   else
      return parent1;
}
void BinaryTree::buildFromInPreOrder(const vector<int> &inorder, const vector<int> &preorder)
{
   map<int, int> inorderMap;
   for (unsigned int i = 0; i < inorder.size(); i++)
   {
      inorderMap[inorder[i]] = i;
   }
  root = buildFromInPreOrder(inorder, preorder, 0, inorder.size() - 1, 0, preorder.size() - 1, inorderMap);
}

TreeNode * BinaryTree::buildFromInPreOrder(const vector<int> &inorder, const vector<int> &preorder,
   int inorderStart, int inorderEnd, int preorderStart, int preorderEnd, map<int, int> &inorderMap)
{
   if (inorderStart > inorderEnd || preorderStart > preorderEnd)
   {
      return NULL;
   }
   int data = preorder[preorderStart];
   TreeNode *node = new TreeNode(data);
   int index = inorderMap[data];
   TreeNode *leftNode = buildFromInPreOrder(inorder, preorder, inorderStart, index - 1,
      preorderStart+1, preorderStart + (index - inorderStart), inorderMap);
   node->left = leftNode;
   if (leftNode)
      leftNode->parent = node;
   TreeNode *rightNode = buildFromInPreOrder(inorder, preorder, index + 1, inorderEnd,
      preorderStart + (index - inorderStart)+ 1, preorderEnd, inorderMap);
   node->right = rightNode;
   if (rightNode)
      rightNode->parent = node;
   return node;
}


 

Posted by at No comments:
Subscribe to: Comments (Atom)