Skip to content

Instantly share code, notes, and snippets.

@bag-man bag-man/owg1Snapper.java
Last active Aug 29, 2015

Embed
What would you like to do?
CS221 Assignment 2
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;
}
}
}
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.