Thank you for your help earlier, I am just about there.
I got the below code to work as I wanted below. Basically it imports the int's from a file (earlier help thank you) , then I find the min, then I sort by polar angle (all counter clock wise turns).
When i did this with the already sorted array it worked as expected.
1 1
2 2
3 3
But when I introduce a set that needed to be sorted I got an out of bounds error. (I also had some before I got it sorted out bounds error before I got the already sorted one to work)
5 4
6 2
4 1
(I was still able to find the lowest Y value, so my two arrays all though annoying, I understand them much better at this time)
removed import stuff for easier reading.
public class Graham {
final static int CCW = 1;
final static int COLLINEAR = 0;
final static int CW = -1;
int xPts[] = new int[3];
int yPts[] = new int[3];
[B] private static int turnDir(int x1, int y1, int x2, int y2, int x3, int y3) {
int turn;
turn = (x1 * y2) - (y1 * x2) + (y1 * x3) - (x1 * y3) + (x2 * y3) - (x3 * y2);
if (turn > 0)
return CCW;
else
if (turn == 0)
return COLLINEAR;
else
// (turn < 0)
return CW;
}
// Merge Sort
private static void mergeSort(int A[], int B[], int p, int s) {
if (p < s) {
int mid = ((p+s)/2);
mergeSort(A, B, p, mid);
mergeSort(A, B, mid+1, s);
merge(A, B, p, mid, s);
}
}
private static void merge(int A[], int B[], int p, int q, int s) {
int i,j,k;
int a = (q-p)+1;
int b = s-q;
int Lx[] = new int[a+1];
int Ly[] = new int[b+1];
int Rx[] = new int[a+1];
int Ry[] = new int[b+1];;
for(i=1; i<=a; i++){
Lx[i] = A[(p+i)-1];
Ly[i] = B[(p+i)-1];
}
for(j=1; i<=b; i++){
Rx[j] = A[q+j];
Ry[j] = B[q+j];
}
//Lx[a+1] = -1;
//Ly[a+1] = -1;
//Rx[b+1] = -1;
//Ry[b+1] = -1;
i = 1;
j = 1;
int side = turnDir(A[0], B[0], Lx[i], Ly[i], Rx[j], Ry[j]);
for(k=p; k<=s; k++) {
if (side == CCW) {
A[k] = Lx[i];
B[k] = Ly[i];
i++;
}
else
if (side == CW) {
A[k] = Rx[j];
B[k] = Ry[j];
j++;
}
}
}[/B]
public static void main( String [ ] args ) throws IOException {
int cur = 0; // current number of points
int temp[] = new int[8];
int xPts[] = new int[4];
int yPts[] = new int[4];
int p = 0;
int c = xPts.length;
int d = c-1;
String fileName ="C:/case2.txt"; //myfile
//Scanner scanner = new Scanner(fileName);
Scanner scanner = new Scanner(new File(fileName));
while((scanner.hasNextInt()) && (cur<temp.length)) {
int x = scanner.nextInt();
temp[cur] = x;
cur++;
}
int j;
int loc = 0;
for(j=0;j<temp.length;j++) {
if(j == 0)
{xPts[loc] = temp[j];}
else if(j == 1){
yPts[loc] = temp[j];
loc++;
}
else if(j % 2 == 0)
{ xPts[loc] = temp[j]; }
else if(j % 2 == 1){
yPts[loc] = temp[j];
loc++;
}
}
// Find Convex Hull
if (d > 2)
{
/*
* find the lowest points, make it to be x/yPts[0].
*/
int xMin = 0;
int yMin = 0;
int k = 0;
for (int i = 1; i < d; i++)
{
if (yPts[i] < yPts[k])
{ k = i; }
else
if (yPts[i] == yPts[k]) {
//tie breaker
if (xPts[i] > xPts[k])
k = i;
}
}
/*
* swap the two points, make lowest point equal yPts[0]
*/
xMin = xPts[k];
yMin = yPts[k];
xPts[k] = xPts[0];
yPts[k] = yPts[0];
xPts[0] = xMin;
yPts[0] = yMin;
System.out.println("xPts[0] value is" + xPts[0]);
System.out.println("yPts[0] value is" + yPts[0]);
[B]
mergeSort(yPts, xPts, p, d);[/B]
int w;
for (w=0;w<d;w++){
System.out.println("xPts[" + w + "] value is" + xPts[w]);
System.out.println("yPts[" + w + "] value is" + yPts[w]);
}
}
}
}Thanks
PS Going to continue to finish the rest up with the base case working. then will go back and see what I am missing and hopefully discuss this further.
