Wednesday, February 29, 2012

Nearest Neighbor Search Using KdTree





//Input should be in input.txt file
//10(2.1,4.3)(3.3,1.5)(4.7,11.1)(4.9,1.6)(5.0,12.3)(5.1,1.2)(6.7,3.3)(19.2,5.4)(20.5,7.9)(100.3,52)
//The first number is the number of points, n, and following it are the coordinates of the n points in ascending order of the x-coordinate.


import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.StringTokenizer;

class KDNode {
    int axis;
    double[] x;
    int id;
    boolean checked;
    boolean orientation;

    KDNode Parent;
    KDNode Left;
    KDNode Right;

    public KDNode(double[] x0, int axis0) {
        x = new double[2];
        axis = axis0;
        for (int k = 0; k < 2; k++)
            x[k] = x0[k];

        Left = Right = Parent = null;
        checked = false;
        id = 0;
    }

    public KDNode FindParent(double[] x0) {
        KDNode parent = null;
        KDNode next = this;
        int split;
        while (next != null) {
            split = next.axis;
            parent = next;
            if (x0[split] > next.x[split])
                next = next.Right;
            else
                next = next.Left;
        }
        return parent;
    }

    public KDNode Insert(double[] p) {
        x = new double[2];
        KDNode parent = FindParent(p);
        if (equal(p, parent.x, 2) == true)
            return null;

        KDNode newNode = new KDNode(p, parent.axis + 1 < 2 ? parent.axis + 1 : 0);
        newNode.Parent = parent;

        if (p[parent.axis] > parent.x[parent.axis]) {
            parent.Right = newNode;
            newNode.orientation = true; //
        } else {
            parent.Left = newNode;
            newNode.orientation = false; //
        }

        return newNode;
    }

    boolean equal(double[] x1, double[] x2, int dim) {
        for (int k = 0; k < dim; k++) {
            if (x1[k] != x2[k])
                return false;
        }

        return true;
    }
    double distance2(double[] x1, double[] x2, int dim) {
        double S = 0;
        for (int k = 0; k < dim; k++)
            S += (x1[k] - x2[k]) * (x1[k] - x2[k]);
        return S;
    }
};

class KDTree {
    KDNode Root;

    int TimeStart, TimeFinish;
    int CounterFreq;

    double d_min;
    KDNode nearest_neighbour;

    int KD_id;

    int nList;

    KDNode CheckedNodes[];
    int checked_nodes;
    KDNode List[];

    double x_min[], x_max[];
    boolean max_boundary[], min_boundary[];
    int n_boundary;

    public KDTree(int i) {
        Root = null;
        KD_id = 1;
        nList = 0;
        List = new KDNode[i];
        CheckedNodes = new KDNode[i];
        max_boundary = new boolean[2];
        min_boundary = new boolean[2];
        x_min = new double[2];
        x_max = new double[2];
    }

    public boolean add(double[] x) {
        if (nList >= 2000000 - 1)
            return false; //can't add more points

        if (Root == null) {
            Root = new KDNode(x, 0);
            Root.id = KD_id++;
            List[nList++] = Root;
        } else {
            KDNode pNode;
            if ((pNode = Root.Insert(x)) != null) {
                pNode.id = KD_id++;
                List[nList++] = pNode;
            }
        }

        return true;
    }

    public KDNode find_nearest(double[] x) {
        if (Root == null)
            return null;

        checked_nodes = 0;
        KDNode parent = Root.FindParent(x);
        nearest_neighbour = parent;
        d_min = Root.distance2(x, parent.x, 2);;

        if (parent.equal(x, parent.x, 2) == true)
            return nearest_neighbour;

        search_parent(parent, x);
        uncheck();

        return nearest_neighbour;
    }

    public void check_subtree(KDNode node, double[] x) {
        if ((node == null) || node.checked)
            return;

        CheckedNodes[checked_nodes++] = node;
        node.checked = true;
        set_bounding_cube(node, x);

        int dim = node.axis;
        double d = node.x[dim] - x[dim];

        if (d * d > d_min) {
            if (node.x[dim] > x[dim])
                check_subtree(node.Left, x);
            else
                check_subtree(node.Right, x);
        } else {
            check_subtree(node.Left, x);
            check_subtree(node.Right, x);
        }
    }

    public void set_bounding_cube(KDNode node, double[] x) {
        if (node == null)
            return;
        int d = 0;
        double dx;
        for (int k = 0; k < 2; k++) {
            dx = node.x[k] - x[k];
            if (dx > 0) {
                dx *= dx;
                if (!max_boundary[k]) {
                    if (dx > x_max[k])
                        x_max[k] = dx;
                    if (x_max[k] > d_min) {
                        max_boundary[k] = true;
                        n_boundary++;
                    }
                }
            } else {
                dx *= dx;
                if (!min_boundary[k]) {
                    if (dx > x_min[k])
                        x_min[k] = dx;
                    if (x_min[k] > d_min) {
                        min_boundary[k] = true;
                        n_boundary++;
                    }
                }
            }
            d += dx;
            if (d > d_min)
                return;

        }

        if (d < d_min) {
            d_min = d;
            nearest_neighbour = node;
        }
    }

    public KDNode search_parent(KDNode parent, double[] x) {
        for (int k = 0; k < 2; k++) {
            x_min[k] = x_max[k] = 0;
            max_boundary[k] = min_boundary[k] = false; //
        }
        n_boundary = 0;

        double dx;
        KDNode search_root = parent;
        while (parent != null && (n_boundary != 2 * 2)) {
            check_subtree(parent, x);
            search_root = parent;
            parent = parent.Parent;
        }

        return search_root;
    }

    public void uncheck() {
        for (int n = 0; n < checked_nodes; n++)
            CheckedNodes[n].checked = false;
    }

};

public class KDTNearest {

    public static void main(String args[]) throws IOException {
        BufferedReader in = new BufferedReader(new FileReader("input.txt"));
        String strLin;
        strLin = in .readLine();

        StringTokenizer strLi = new StringTokenizer(strLin, "(,) ");
        int numpoints = Integer.parseInt(strLi.nextToken());

        KDTree kdt = new KDTree(numpoints);

        while (strLi.hasMoreTokens()) {

            double x[] = new double[2];
            for (int i = 0; i < numpoints; i++) {

                x[0] = Double.parseDouble(strLi.nextToken());
                x[1] = Double.parseDouble(strLi.nextToken());
                kdt.add(x);
            }
        }
        System.out.println("Enter the co-ordinates of the point: (one after the other)");
        InputStreamReader reader = new InputStreamReader(System. in );
        BufferedReader br = new BufferedReader(reader);
        double sx = Double.parseDouble(br.readLine());
        double sy = Double.parseDouble(br.readLine());

        double s[] = {
            sx, sy
        };
        KDNode kdn = kdt.find_nearest(s);
        System.out.println("(" + kdn.x[0] + " , " + kdn.x[1] + ")");
    }
}

Monday, February 27, 2012

Facebook User Authentication: Get access to user data

This is the extension of my previous article on facebook share. But, no need of prior knowledge. Proceed from here.

After registering a developer account @ https://developers.facebook.com/ , create an app.
Note the App-Id and don't forget to add the redirect url under the app settings section.
Also add all the access permissions you would like to get from the user under Auth Dalog section.

All these permissions are to be used later to retrieve corresponding data.

URL pattern to implement the authentication is as follows:

http://m.facebook.com/dialog/oauth?client_id=<APP-ID>
&redirect_uri=<PATH- TO-TARGETTED-LOCATION>
&scope=<ALL-THE-PERMISSIONS-LIKE-email,offline_access>
&response_type=token

Just modify the CAPITAL lettered data, and for the redirect-url no need of using quotation marks("")

Twitter Custom Share

We can add the tweet button directly from the twitter website.

But if you want a image of you wish, then it's easy to get it.

<a href="http://m.twitter.com/home?status=WHATEVER-YOU-WOULD-LIKE">

<img src="SOME IMAGE, BUT KEEP IT RELEVANT" /></a>

And if you are developing any application and want to implement authentication,

use OAuth provided in twitter API:

https://dev.twitter.com/docs/auth/oauth

Note: You have to register a developer account and create a app there.

For authentication use the access token generated on the app settings page.

Facebook Share (URL based)

This is the most simplest way to add a facebook share button.

Use the following code as the reference(href) attribute of your anchor tag(<a>)

"http://www.facebook.com/sharer.php?u=<text or url to post on wall>"

You can use any image to show the share button, but be precise in selecting it,

as the user should get on it easily.

Consider the following sample code:

<a href="http://www.facebook.com/sharer.php?u=https://thechaithanya.wordpress.com"><img src="http://www.acrnet.org/uploadedImages/Get_Involved/facebook-logo.png" alt="share on facebook"></a>

If you are developing any applicetion or website and want the post to be displayed as it was posted from your app,

like "via theChaithanya", use the following code:

         "http://m.facebook.com/dialog/feed?app_id=YOUR-APP-ID&link=LINK-TO-BE-POSTED&redirect_uri=PATH-TO-LOCATION-AFTER-SHARE"

On successful sharing it will redirect you to the redirect-url along with post-id.

Note: To get APP-ID, you have to register a developer account and create an app.

Also the redirect url should be added there in the app settings.

For further info visit: https://developers.facebook.com/

Something went wrong! How do I reset Unity or Compiz?

You can easily reset Unity or Compizusing the following commands (be careful when using these commands and only use them if you really have to!):

- to reset the Unity launcher icons:
unity --reset-icons
- to reset Unity:
unity --reset
- to reset Compiz:
gconftool-2 --recursive-unset /apps/compiz-1 unity --reset

Ubuntu : Disable the user switcher indicator



The user switcher indicator (or Me-User-Indicator or whatever is called) can be useful if multiple users log in on your computer but if it's just one user, you can get more space by disabling it. Presuming you've already installed the "dconf-tools" package: press ALT + F2 or open a terminal and enter:
dconf-editor
Ubuntu : Disable the user switcher indicator


Then navigate to apps > indicator-session and uncheck the box next to "user-show-menu", then restat Unity (ALT + F2 and enter "unity --replace") or log out and log back in.

Ubuntu : Re-enable the systray (notification area)

Ubuntu : Re-enable the systray


You no longer need to whitelist Qt applications but you may still need the systray for other applications such as Shutter, Jupiter, etc. You can whitelist the systray using the following command:
gsettings set com.canonical.Unity.Panel systray-whitelist "['all']"
Then log out and log back in.

Disable Overlay Scrollbars (Quite Disturbing)

Disable Overlay Scrollbars

If you don't like the overlay scrollbars, you can remove them using the following command:
sudo apt-get remove overlay-scrollbar liboverlay-scrollbar3-0.2-0 liboverlay-scrollbar-0.2-0
Then, restart your computer (performing a logout only may not be enough).

To revert this change, install the packages back:
sudo apt-get install overlay-scrollbar liboverlay-scrollbar3-0.2-0 liboverlay-scrollbar-0.2-0
And restart your computer.

Ubuntu : Re-enable Syanaptic Package Manager

Install Syanptic (Ubuntu has omitted it, but I like it)

Ubuntu : Re-enable Syanaptic Package Manager
Synaptic package manager is not installed by default in Ubuntu 11.10 and while Ubuntu Software Center got many new features, it still can't do everything Synaptic can. Install Synaptic back using the following command:
sudo apt-get install synaptic

Ubuntu : Mac style dock - Cairo-Dock


Ubuntu : Mac style dock - Cairo-Dock

Cairo dock is a Mac OSX dock-like application that you can install in your Linux machine. One of the advantage that it has over other docks is that it does not require any compositing window manager to work. Even on a low-end PC, it will still work fine. This is not possible for docks like Avant Window Navigator which depends on compositing manager (such as Compiz) to function.

If you are using a PC that does not support any compositing manager, or you wanted to try out alternative dock for your Ubuntu machine, follow this tutorial to install and configure Cairo Dock on your Ubuntu Intrepid.

*It can also be installed directly from the Ubuntu Software Center*

Installing Cairo dock


Adding the repository

In your terminal,
gksu gedit /etc/apt/sources.list
Add the following line to the end of the file. Save and close.
deb http://repository.cairo-dock.org/ubuntu intrepid cairo-dock
Add the signed GPG key:
wget -q http://repository.cairo-dock.org/ubuntu/cairo-dock.gpg -O- | sudo apt-key add -
Install the application:
sudo apt-get update
sudo apt-get install cairo-dock cairo-dock-plugins

lxsplit : split and join files

lxSplit is a simple tool for splitting files and joining the splitted files on unix-like platforms, such as Linux, FreeBSD, OpenBSD, etc.

lxSplit splits and merges files with the -s and -j flags respectively. Starting with version 0.2.1, lxSplit can handle large files (>= 4 GB) both when splitting and joining.

It can be installed from the ubuntu software centre.

Usage:
To split a big file into smaller pieces of 15 MB each, run the following command:
lxsplit -s hugefile.bin 15M
Output size can be given in (M)egabytes, (k)ilobytes and (b)ytes.

To merge (join) the already split pieces into the original big file, run this command:
 lxsplit -j smallfiles.bin.001
All resulting files (from either splitting or joining) will be placed in the current directory.

The official location of this document: http://lxsplit.sourceforge.net/

Resize the launcher - Compiz Config Settings Manager

Install Compiz Config Settings Manager
Resize the launcher - Compiz Config Settings Manager

Compiz desktop effects are available in your Ubuntu by default and if you have any kind of 3D acceleration available(graphics driver ie), you are good to go with Compiz.

Now to tweak Compiz desktop effects in Ubuntu, you need to install "compizconfig-settings-manager" package. Simply copy paste the following command into Terminal to install "compizconfig-settings-manager".
sudo apt-get install compizconfig-settings-manager
Then change the size and transparency levels as per your wish