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;
int yPts[] = new int;

[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, B, 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;
int xPts[] = new int;
int yPts[] = new int;
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.
*/
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
*/
xMin = xPts[k];
yMin = yPts[k];
xPts[k] = xPts;
yPts[k] = yPts;
xPts = xMin;
yPts = yMin;

System.out.println("xPts value is" + xPts);
System.out.println("yPts value is" + yPts);
[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.

Two options either you gone provide code for whole program or clearly mark which section is kicking of the error

Did you try:

if (turn > 0){
return CCW;
}else if (turn < 0){
return CW;
}

return COLLINEAR;

Worth a try, and does the same thing as you were trying to do with your code above.

## All 5 Replies

Two options either you gone provide code for whole program or clearly mark which section is kicking of the error

The portions of the code that are giving me problem are in bold above, and also below.

``````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, B, 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++;
}

}
}``````

I think it has something to do with this. I am using Jgrasp to do the editing, and it runs fine there, but when I run this as a javac command line function, it gives me a return error for this function.

Does any one see any thing wrong? I have three return statements covering all possibilities.

``````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 CW;
else
return COLLINEAR;

}``````

Did you try:

if (turn > 0){
return CCW;
}else if (turn < 0){
return CW;
}

return COLLINEAR;

Worth a try, and does the same thing as you were trying to do with your code above.

This did help with the compiling with Javac, but I still get the same out of bounds exception.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.