Guest User

Untitled

a guest
Jul 19th, 2018
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.98 KB | None | 0 0
  1. static void computeConvexHull(int pointCount, double[] xVal, double[] yVal) {
  2.  
  3. // Ok, this is the interesting stuff.
  4. // According to the hand-outs, we know what m, c and y are.
  5. //
  6. // m = (y1 - y2) / (x1 - x2)
  7. // x = c
  8. // c = y1 - m(x1) IF x1 != x2 ELSE c = x1
  9. // y = mx + c
  10. //
  11. // We know that m, c, x and y can be doubles.
  12. // We get x when looping through the points.
  13. // So, we only need to declare m, c and y here.
  14. double m, c, y;
  15.  
  16. for(int i = (pointCount-1); i >= 1; i--) {
  17. // i is counting backwards!
  18. for(int j = 0; j < i; j++) {
  19.  
  20. // j is going forwards!
  21. // We do not want them to be the same!
  22. // CONTINUE means we skip the current iteration,
  23. // and go on to the next index in the array.
  24.  
  25. if(i == j) continue;
  26. // Declare above and below! This is important.
  27. int above = 0, below = 0;
  28.  
  29. // Ok, this is where we work out M and C!
  30. // m = (y1 - y2) / (x1 - x2)
  31. m = (yVal[i] - yVal[j]) / (xVal[i] - xVal[j]);
  32.  
  33. // c = y1 - m(x1) IF x1 != x2 ELSE c = x1
  34. // Remember! With the ternary operator, it is as follows:
  35. // var = <condition> ? <true value> : <false value>;
  36. // Rearranged as an IF...ELSE it would be:
  37. // if(<condition>) { var = <true value>; } else { var = <false value>; }
  38. c = (xVal[i] == xVal[j]) ? xVal[i] : yVal[i] - (m * xVal[i]);
  39.  
  40. // So, now we should be able to determine the edge created by points i and j.
  41. // Next we need to determine how many points appear above and below the edge.
  42.  
  43. for(int k = 0; k < pointCount; k++) {
  44. // Another for loop! What joy!
  45. // Here, we don't want point k to be the same as either of the points in use.
  46. // So we continue, if it is.
  47. if(k == i || k == j) continue;
  48.  
  49. // From here on out, it is simple logic!
  50.  
  51. if(c == xVal[i]) {
  52. if(xVal[k] > c)
  53. above++; // We have a point above the line!
  54. if(xVal[k] < c)
  55. below++; // We have a point below the line!
  56. } else {
  57. // We only ever need to work out Y if we get this far!
  58. // We could swap the if and the else, but then we would be
  59. // working out Y when we don't really have to.
  60. // SO! Y = mx + c!
  61. y = (m * xVal[k]) + c;
  62.  
  63. // Is our current y value above or below the line?
  64.  
  65. if(yVal[k] > y)
  66. above++;
  67. if(yVal[k] < y)
  68. below++;
  69. }
  70. }
  71.  
  72. // Here we have an EXCLUSIVE OR!
  73. // We only want there to be points above OR below the line!
  74. // Never both! If both, then the edge is not in the polygon!
  75.  
  76. if((above > 0 && below == 0) || (above == 0 && below > 0))
  77. System.out.println(">> The edge ((" + xVal[i] + ", " + yVal[i] + "), (" + xVal[j] + ", " + yVal[j] + ")) is on the convex hull.");
  78.  
  79. // Nothing really needs to be done after that...
  80.  
  81. }
  82.  
  83. // Just let the loops exit...
  84.  
  85. }
  86.  
  87. // And then the method...
  88.  
  89. }
Add Comment
Please, Sign In to add comment