CS221 Assignment 2

owg1Snapper.java

package cs21120.assignment2.solution;

import cs21120.assignment2.FloatImage;
import cs21120.assignment2.ISnapper;

import java.util.concurrent.PriorityBlockingQueue;
import java.util.LinkedList;
import java.awt.Point;

/**
* <h1>What was achieved?</h1>
* 
* I believe that I have implemented Dijkstra's algorithm completely and efficiently. 
* The program works as it should and there aren't any performance issues. 
* 
* <h1>Difficulties developing the solution. </h1>
*
* It took me a long time to develop this solution, mainly due to a lack of understanding 
* of how the interface I was given was supposed to work with the code provided. 
* This meant that I was initially trying to use Dijkstra's algorithm in the getPath method,
* to find the shortest path back to the seed; instead of running the algorithm over the 
* entire image and then pulling the path from the pre-computed map of nodes. 
*
* Once I had figured this out I made my own implementation that worked, but very inefficiently. 
* This was because I was using a collection to sort the list of nodes every time one was added to the list.
* Once I realised the mistake I changed it over to a PriorityQueue which solved the performance issues.
* From there I encountered a few bugs but the rest of the development went fairly smoothly. It just took 
* a lot longer than I would have liked to fully understand the problem and how my code was supposed to work 
* with the given code. 
*
*/
public class Owg1Snapper implements ISnapper, Runnable {

  private FloatImage[] imageData;
  private Node[][] nodes; 
  private int seedX, seedY;

  /**
   * Gets the path from the specified point back to the seed point This method is called on mouseDragged events.
   *
   * @param x 
   * This is an X co-ordinate given to the function. 
   * Together with Y it represents where the user has dragged to.
   *
   * @param y 
   * This is an Y co-ordinate given to the function. 
   * Together with X it represents where the user has dragged to.
   *
   * @return 
   * Returns a LinkedList of Points, that have been found as the quickest path. 
   *
   * Once the map had been built in the 2D array of nodes it was trivial to pull the shortest path out. 
   * I did this by simply looking at where the cheapest node from the initial point had been visited from. 
   */
  public LinkedList<Point> getPath(int x, int y) {
    LinkedList<Point> result = new LinkedList<Point>();
    
    // Add the first point
    result.add(new Point(x, y));

    try { // Null pointer if no drag
      Point tmp = nodes[x][y].getFrom(); 
      // Get the visitedFrom node until we reach the seed.
      while(tmp.y != seedY && tmp.x != seedX) {
        x = tmp.x; 
        y = tmp.y; 
        result.add(new Point(x, y));
        tmp = nodes[x][y].getFrom();
      }
    } catch(Exception e) {
      // NO DRAG EVENT;
    }
    result.add(new Point(seedX, seedY));
    return result;
  }

  /**
   * Set the start point for the estimation of the shortest paths.
   * The edge images contain the edge weights to use from pixel (x,y) to {(x+1, y), (x+1, y+1), (x, y+1) and (x-1, y+1)} in that order.
   * The weights in the other 8 directions can be found by symmetry as the graph is undirected. This method is called on mousePressed events
   *
   * @param x 
   * This is an X co-ordinate given to the function. 
   * Together with Y it represents where the user has initially clicked.
   *
   * @param y 
   * This is an Y co-ordinate given to the function. 
   * Together with X it represents where the user has initially clicked.
   *
   * @param edges
   * The edge images containing the weights to use between pixels in the order {E, NE, N, NW}
   *
   * This method took me a while to figure out correctly. I had getPath and setSeed round the wrong way. 
   * Once I knew that Dijkstra's algorithm was supposed to be implemented here development was a lot easier.
   */
  public void setSeed(int x, int y, FloatImage[] edges) {
    // Make these variables accessible within the class.
    imageData = edges;
    seedX = x;
    seedY = y;

    // Run Dijkstra's algorithm in a thread as it may take some time to complete.
    Thread finder = new Thread(this, "finder");
    finder.start();
  }

  /**
   * Implements Dijkstra's algorithm on the image. Creates a 2D array of nodes, 
   * and uses that in combination with a priority queue to find all of the relative weights from the seed point. 
   * Returns void, runs Dijkstra's algorithm on the image 
   * to calculate all the relative weights for each node in the image.
   *
   * I have left the debugging code in the method but commented out. 
   * These code snippets really helped me to diagnose issues with my algorithm. 
   */
  public void run() {
    int x = seedX;
    int y = seedY;

    // Build a blank map, all weights are calculated for each node, and relative distance set to infinity.
    nodes = new Node[imageData[0].getWidth()][imageData[0].getHeight()];
    for(int X = 0; X < imageData[0].getWidth(); X++) {
      for(int Y = 0; Y < imageData[0].getHeight(); Y++) {
        nodes[X][Y] = new Node(X, Y, getWeights(X,Y));
      }
    }

    PriorityBlockingQueue<Node> tentativeValues = new PriorityBlockingQueue<Node>();

    // Set the seed node, its relative distance is set to 0.
    nodes[seedX][seedY].setSeed();
    tentativeValues.add(nodes[seedX][seedY]);

    do {
      // Pull cheapest node off the queue, set it to visited.
      Node n = tentativeValues.remove();      
      n.setVisited();
      
      /* DEBUG
      System.out.print("CURRENT \t |  ");
      n.printNode();
      */

      x = n.getLocation().x;
      y = n.getLocation().y;

      // For each node around the node, check if the realtive distance for it is less than its current distance.
      for(DIRECTION d: DIRECTION.values()) {
        int tmpX = x + d.p.x;
        int tmpY = y + d.p.y;
        if(tmpX < 0 || tmpY < 0 || tmpX >= imageData[0].getWidth() || tmpY >= imageData[0].getHeight()) {
          continue;
        }
        Node tmp = nodes[tmpX][tmpY];
        if(!tmp.visited()) { 
          if(tmp.setDistance(nodes[x][y].getWeights()[d.ordinal()], new Point(x,y))) {
            // If it hasn't been visited and has a lower value add it to the queue.
            tmp.setVisitedFrom(new Point(x,y));
            tentativeValues.add(tmp); 
            
            /* DEBUG
            System.out.print(d.name() + "    \t |  ");
            tmp.printNode();
            */
          }
        }
      }

      /* DEBUG
      try{ 
        System.in.read();
      } catch(e Exception) {
        // Do nothing 
      }
      */

    // Repeat until queue is empty, comepleting the map of the image.
    } while(!tentativeValues.isEmpty());

  }

  /**
   * Enum which contains the point modifiers to find all points around a initial point.
   */
  private enum DIRECTION {
    NORTH_WEST(new Point(-1,-1)), 
         NORTH(new Point(0,-1)),
    NORTH_EAST(new Point(1,-1)),
          EAST(new Point(1,0)),   
    SOUTH_EAST(new Point(1,1)),
         SOUTH(new Point(0,1)),   
    SOUTH_WEST(new Point(-1,1)),
          WEST(new Point(-1,0));

    public final Point p;

    DIRECTION(Point p) {
      this.p = p;
    }
  };

  /**
   * This method puts a nodes weights into an array.
   *
   * @param x 
   * This is an X co-ordinate given to the function. 
   * Together with Y it represents a point in the image.
   *
   * @param y 
   * This is an Y co-ordinate given to the function. 
   * Together with X it represents a point in the image.
   *
   * @return 
   * Returns an array of floats in the correct order. 
   * These floats represent the weights of the edges from a node, going clockwise from North West (0) to West (7).
   */
  public float[] getWeights(int x, int y) {
    float[] weight = new float[8];

    weight[0] = imageData[3].get(x, y);       // NORTH WEST
    weight[1] = imageData[2].get(x, y);       // NORTH
    weight[2] = imageData[1].get(x, y);       // NORTH EAST
    weight[3] = imageData[0].get(x, y);       // EAST
    weight[4] = imageData[3].get(x +1, y -1); // SOUTH EAST
    weight[5] = imageData[2].get(x, y -1);    // SOUTH
    weight[6] = imageData[1].get(x -1, y -1); // SOUTH WEST
    weight[7] = imageData[0].get(x -1, y);    // WEST

    return weight;
  }

  /**
   * This class represents each node (vertex) in the image. 
   * A 2D array of these is created when Dijkstra's algorithm is ran, each node contains meta data about itself.
   * This is then used as a map to find the shortest path. 
   */
  class Node implements Comparable<Node> {
    private int x, y;
    private boolean visited;
    private float[] weights;
    private float distance = Float.POSITIVE_INFINITY;
    private Point visitedFrom;

    /**
     * Constructor takes its position and the weights around it 
     *
     * @param x This represents the X location of the node.
     * @param y This represents the Y location of the node.
     * @param weights An array of 8 floats that represent the distance from this node
     * to the NW, N.. SW, W nodes surrounding it. 
     */
    Node(int x, int y, float[] weights) {
      this.x = x;
      this.y = y;
      this.weights = weights;
    }

    /**
     * Print out a nodes data for debugging purposes.
     */
    public void printNode() {
      if(distance == 0) {
        System.out.println(distance  + " (SEED) \t | (" + x + "," + y + ")\t | " + visited + " \t | (" + visitedFrom.x + "," + visitedFrom.y + ")");
      } else {
        System.out.println(distance  + " \t | (" + x + "," + y + ")\t | " + visited + " \t | (" + visitedFrom.x + "," + visitedFrom.y + ")");
      }
    }

    /**
     * The compareTo method from Comparable. 
     * Used to determine if one node is cheaper that it so the priority queue can be sorted by cheapest node. 
     *
     * @param n The node to compare against.
     * @see Node
     * @return int representing if the node is a smaller or larger distance.
     */ 
    public int compareTo(Node n) {
      if (n.getDistance() > distance)
        return -1;
      else if (n.getDistance() < distance)
        return 1;
      return 0;
    }

    /**
     * @return Boolean value of whether the node has been visited or not.
     */
    public boolean visited() {
      return visited;
    }

    /**
     * Set the node to visited.
     */
    public void setVisited() {
      visited = true;
    }

    /**
     * @return Point where the node is located in the image.
     */
    public Point getLocation() {
      return new Point(x, y);
    }

    /**
     * @return Point where the node was visited from by Dijkstra's algorithm.
     */
    public Point getFrom() {
      return new Point(visitedFrom.x, visitedFrom.y);
    }

    /**
     * Set where the node was visited from by Dijkstra's algorithm.
     * @param from A Point representing the location that the node was visited from.
     */
    public void setVisitedFrom(Point from) {
      visitedFrom = from;
    }

    /**
     * Update the relative distance from the seed if lower.
     *
     * @param weight The distance from the previous node to this node.
     * @param from The point where this node was visited from.
     * @return Boolean for whether or not the new distance is lower than the existing one.
     *
     */
    public boolean setDistance(float weight, Point from) {
      float cumulative = nodes[from.x][from.y].getDistance();
      if((weight + cumulative) < distance) {
        distance = weight + cumulative;
        return true;
      }
      return false;
    }

    /**
     * Set the node to be the seed. Set distance to 0 and set it to visited.
     */
    public void setSeed() {
      distance = 0;
      visited = true;
      visitedFrom = new Point(x, y);
    }

    /**
     * @return Float that represents to total relative distance of this node from the seed. 
     */
    public float getDistance() {
      return distance;
    }

    /**
     * @return Float array of 8 weights of the distance from this node to its 8 neighbours.
     */
    public float[] getWeights() {
      return weights;
    }
  }
}

run.sh

wmname LG3D
javac owg1Snapper.java
mv *.class cs21120/assignment2/solution/
jar cf test.jar cs21120
click() {

sleep 2
xdotool mousemove 47 88
xdotool click 1 

}
click &
clear
java -jar ../CS21120-A2-Fixed.jar /root/CS211/owg1/test.jar cs21120.assignment2.solution.owg1Snapper ../iCub27-200x300.jpg
#File > Select Snapper > Find Jar > Add > OK > Load Image