Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- static void computeConvexHull(int pointCount, double[] xVal, double[] yVal) {
- // Ok, this is the interesting stuff.
- // According to the hand-outs, we know what m, c and y are.
- //
- // m = (y1 - y2) / (x1 - x2)
- // x = c
- // c = y1 - m(x1) IF x1 != x2 ELSE c = x1
- // y = mx + c
- //
- // We know that m, c, x and y can be doubles.
- // We get x when looping through the points.
- // So, we only need to declare m, c and y here.
- double m, c, y;
- for(int i = (pointCount-1); i >= 1; i--) {
- // i is counting backwards!
- for(int j = 0; j < i; j++) {
- // j is going forwards!
- // We do not want them to be the same!
- // CONTINUE means we skip the current iteration,
- // and go on to the next index in the array.
- if(i == j) continue;
- // Declare above and below! This is important.
- int above = 0, below = 0;
- // Ok, this is where we work out M and C!
- // m = (y1 - y2) / (x1 - x2)
- m = (yVal[i] - yVal[j]) / (xVal[i] - xVal[j]);
- // c = y1 - m(x1) IF x1 != x2 ELSE c = x1
- // Remember! With the ternary operator, it is as follows:
- // var = <condition> ? <true value> : <false value>;
- // Rearranged as an IF...ELSE it would be:
- // if(<condition>) { var = <true value>; } else { var = <false value>; }
- c = (xVal[i] == xVal[j]) ? xVal[i] : yVal[i] - (m * xVal[i]);
- // So, now we should be able to determine the edge created by points i and j.
- // Next we need to determine how many points appear above and below the edge.
- for(int k = 0; k < pointCount; k++) {
- // Another for loop! What joy!
- // Here, we don't want point k to be the same as either of the points in use.
- // So we continue, if it is.
- if(k == i || k == j) continue;
- // From here on out, it is simple logic!
- if(c == xVal[i]) {
- if(xVal[k] > c)
- above++; // We have a point above the line!
- if(xVal[k] < c)
- below++; // We have a point below the line!
- } else {
- // We only ever need to work out Y if we get this far!
- // We could swap the if and the else, but then we would be
- // working out Y when we don't really have to.
- // SO! Y = mx + c!
- y = (m * xVal[k]) + c;
- // Is our current y value above or below the line?
- if(yVal[k] > y)
- above++;
- if(yVal[k] < y)
- below++;
- }
- }
- // Here we have an EXCLUSIVE OR!
- // We only want there to be points above OR below the line!
- // Never both! If both, then the edge is not in the polygon!
- if((above > 0 && below == 0) || (above == 0 && below > 0))
- System.out.println(">> The edge ((" + xVal[i] + ", " + yVal[i] + "), (" + xVal[j] + ", " + yVal[j] + ")) is on the convex hull.");
- // Nothing really needs to be done after that...
- }
- // Just let the loops exit...
- }
- // And then the method...
- }
Add Comment
Please, Sign In to add comment