Advertisement
Guest User

Untitled

a guest
Feb 8th, 2016
81
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.87 KB | None | 0 0
  1. import java.util.Comparator;
  2. import java.util.PriorityQueue;
  3.  
  4.  
  5. public class Lab2b {
  6.  
  7. public static double[] simplifyShape(double[] poly, int k) {
  8.  
  9. PriorityQueue<DLList<Point>.Node> queue = new PriorityQueue<DLList<Point>.Node>(poly.length/2, new NodePointComparator());
  10. DLList<Point> list = new DLList<Point>();
  11.  
  12. list.addFirst(new Point(poly[0],poly[1],-1)); // adds the first point
  13.  
  14. for (int i = 2; i < poly.length - 2; i = i + 2) { //aads all the middle points with value calculated
  15. double value;
  16. double length1 = Math.sqrt(Math.pow((poly[i - 2] - poly[i]),2) + Math.pow((poly[i - 1] - poly[i + 1]),2));
  17. //L-P
  18. double length2 = Math.sqrt(Math.pow((poly[i] - poly[i + 2]),2) + Math.pow((poly[i + 1] - poly[i + 3]),2));
  19. //P-R
  20. double length3 = Math.sqrt(Math.pow((poly[i - 2] - poly[i + 2]),2) + Math.pow((poly[i - 1] - poly[i + 3]),2));
  21. //L-R
  22. value = length1 + length2 - length3;
  23. //l1, l2 och l3
  24.  
  25. Point point = new Point(poly[i], poly[i+1],value);
  26. DLList<Point>.Node node = list.addLast(point);
  27. queue.add(node);
  28. }
  29. list.addLast(new Point(poly[poly.length-1],poly[poly.length-2],-1)); // adds the last point
  30.  
  31. while(queue.size()+2 > k){
  32.  
  33. //removes the node from both the queue and the list and saves the neighbours to the removed node
  34. DLList<Point>.Node node = queue.poll();
  35. DLList<Point>.Node nodeL = node.prev;
  36. DLList<Point>.Node nodeR = node.next;
  37. list.remove(node);
  38.  
  39. if(nodeL!= list.getFirst()) {
  40. //removes from queue to recalculate the neighbours to the removed node, these nodes will be added again.
  41. queue.remove(nodeL);
  42. //recalculate the value for the nodes just removeds neighbour's
  43. setPointValue(nodeL.prev, nodeL, nodeL.next);
  44. //adds the nodes again after they have been updated
  45. queue.add(nodeL);
  46. }
  47. if(nodeR!= list.getLast()) {
  48. //removes from queue to recalculate the neighbours to the removed node, these nodes will be added again.
  49. queue.remove(nodeR);
  50. //recalculate the value for the nodes just removeds neighbour's
  51. setPointValue(nodeR.prev, nodeR, nodeR.next);
  52. //adds the nodes again after they have been updated
  53. queue.add(nodeR);
  54. }
  55.  
  56. }
  57.  
  58. //copies the linked list to an array
  59. DLList<Point>.Node currentNode = list.getFirst();
  60. double[] retur = new double[k*2];
  61. for(int i=0; i<k*2; i=i+2){
  62. retur[i] = currentNode.elt.getX();
  63. retur[i+1] = currentNode.elt.getY();
  64. currentNode = currentNode.next;
  65. }
  66. return retur; //returns the linked list as an array
  67. }
  68.  
  69. //Class that represents a point that each node will hold
  70. private static class Point implements Comparable<Point> {
  71. private double x; //x-value
  72. private double y; //y-value
  73. private double value; //value for the value used to calulate the prioroity
  74.  
  75. public Point(double x, double y, double value){
  76. this.x = x;
  77. this.y = y;
  78. this.value = value;
  79. }
  80.  
  81. public double getX(){
  82. return x;
  83. }
  84. public double getY(){
  85. return y;
  86. }
  87.  
  88. @Override
  89. public int compareTo(Point p) { //only compares the value
  90. double compValue = this.value - p.value;
  91. if( compValue<0){
  92. return -1;
  93. }else if(compValue >0){
  94. return 1;
  95. }
  96. return 0;
  97. }
  98. }
  99.  
  100. protected static class NodePointComparator implements Comparator<DLList<Point>.Node> {
  101. //class to compare Nodes with points as data.
  102. @Override
  103. public int compare(DLList<Point>.Node o1, DLList<Point>.Node o2) {
  104. return (o1.elt).compareTo(o2.elt); //use points compareTO method
  105. }
  106. }
  107.  
  108. private static void setPointValue(DLList<Point>.Node nodeL, DLList<Point>.Node nodeM, DLList<Point>.Node nodeR){
  109. double value;
  110. double length1 = Math.sqrt(Math.pow((nodeL.elt.getX() - nodeM.elt.getX()),2)
  111. + Math.pow((nodeL.elt.getY() - nodeM.elt.getY()),2));
  112. //L-P
  113. double length2 = Math.sqrt(Math.pow((nodeM.elt.getX() - nodeR.elt.getX()),2)
  114. + Math.pow((nodeM.elt.getY() - nodeR.elt.getY()),2));
  115. //P-R
  116. double length3 = Math.sqrt(Math.pow((nodeL.elt.getX() - nodeR.elt.getX()),2)
  117. + Math.pow((nodeL.elt.getY() - nodeR.elt.getY()),2));
  118. //L-R
  119. value = length1 + length2 - length3;
  120. //l1, l2 och
  121. nodeM.elt.value = value;
  122. }
  123.  
  124.  
  125. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement