Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Comparator;
- import java.util.PriorityQueue;
- public class Lab2b {
- public static double[] simplifyShape(double[] poly, int k) {
- PriorityQueue<DLList<Point>.Node> queue = new PriorityQueue<DLList<Point>.Node>(poly.length/2, new NodePointComparator());
- DLList<Point> list = new DLList<Point>();
- list.addFirst(new Point(poly[0],poly[1],-1)); // adds the first point
- for (int i = 2; i < poly.length - 2; i = i + 2) { //aads all the middle points with value calculated
- double value;
- double length1 = Math.sqrt(Math.pow((poly[i - 2] - poly[i]),2) + Math.pow((poly[i - 1] - poly[i + 1]),2));
- //L-P
- double length2 = Math.sqrt(Math.pow((poly[i] - poly[i + 2]),2) + Math.pow((poly[i + 1] - poly[i + 3]),2));
- //P-R
- double length3 = Math.sqrt(Math.pow((poly[i - 2] - poly[i + 2]),2) + Math.pow((poly[i - 1] - poly[i + 3]),2));
- //L-R
- value = length1 + length2 - length3;
- //l1, l2 och l3
- Point point = new Point(poly[i], poly[i+1],value);
- DLList<Point>.Node node = list.addLast(point);
- queue.add(node);
- }
- list.addLast(new Point(poly[poly.length-1],poly[poly.length-2],-1)); // adds the last point
- while(queue.size()+2 > k){
- //removes the node from both the queue and the list and saves the neighbours to the removed node
- DLList<Point>.Node node = queue.poll();
- DLList<Point>.Node nodeL = node.prev;
- DLList<Point>.Node nodeR = node.next;
- list.remove(node);
- if(nodeL!= list.getFirst()) {
- //removes from queue to recalculate the neighbours to the removed node, these nodes will be added again.
- queue.remove(nodeL);
- //recalculate the value for the nodes just removeds neighbour's
- setPointValue(nodeL.prev, nodeL, nodeL.next);
- //adds the nodes again after they have been updated
- queue.add(nodeL);
- }
- if(nodeR!= list.getLast()) {
- //removes from queue to recalculate the neighbours to the removed node, these nodes will be added again.
- queue.remove(nodeR);
- //recalculate the value for the nodes just removeds neighbour's
- setPointValue(nodeR.prev, nodeR, nodeR.next);
- //adds the nodes again after they have been updated
- queue.add(nodeR);
- }
- }
- //copies the linked list to an array
- DLList<Point>.Node currentNode = list.getFirst();
- double[] retur = new double[k*2];
- for(int i=0; i<k*2; i=i+2){
- retur[i] = currentNode.elt.getX();
- retur[i+1] = currentNode.elt.getY();
- currentNode = currentNode.next;
- }
- return retur; //returns the linked list as an array
- }
- //Class that represents a point that each node will hold
- private static class Point implements Comparable<Point> {
- private double x; //x-value
- private double y; //y-value
- private double value; //value for the value used to calulate the prioroity
- public Point(double x, double y, double value){
- this.x = x;
- this.y = y;
- this.value = value;
- }
- public double getX(){
- return x;
- }
- public double getY(){
- return y;
- }
- @Override
- public int compareTo(Point p) { //only compares the value
- double compValue = this.value - p.value;
- if( compValue<0){
- return -1;
- }else if(compValue >0){
- return 1;
- }
- return 0;
- }
- }
- protected static class NodePointComparator implements Comparator<DLList<Point>.Node> {
- //class to compare Nodes with points as data.
- @Override
- public int compare(DLList<Point>.Node o1, DLList<Point>.Node o2) {
- return (o1.elt).compareTo(o2.elt); //use points compareTO method
- }
- }
- private static void setPointValue(DLList<Point>.Node nodeL, DLList<Point>.Node nodeM, DLList<Point>.Node nodeR){
- double value;
- double length1 = Math.sqrt(Math.pow((nodeL.elt.getX() - nodeM.elt.getX()),2)
- + Math.pow((nodeL.elt.getY() - nodeM.elt.getY()),2));
- //L-P
- double length2 = Math.sqrt(Math.pow((nodeM.elt.getX() - nodeR.elt.getX()),2)
- + Math.pow((nodeM.elt.getY() - nodeR.elt.getY()),2));
- //P-R
- double length3 = Math.sqrt(Math.pow((nodeL.elt.getX() - nodeR.elt.getX()),2)
- + Math.pow((nodeL.elt.getY() - nodeR.elt.getY()),2));
- //L-R
- value = length1 + length2 - length3;
- //l1, l2 och
- nodeM.elt.value = value;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement