# Help determining if Circles overlap

• 04-22-2012, 02:42 AM
quinnvanorder
Help determining if Circles overlap
I have been given a project to make a program that draws 20 circles, whose x and y coordinates, as well as radius are randomly generated, and then to color them according to if they overlap or not. I have a program that can now display my 20 random circles, but I am having issues with the collision detection

What I have done is make another program that is only the creation of the 2 dimensional array and added a 4th colum

The information stored in the table are as such
table[x][1]= x coordinate
table[x][2]= y coordinate
table[x][3]= a value of 1 or 0, 1 meaning the coordinates overlap and 0 that they do not

my code is below
Code:

```import java.util.Random; public class TwoDArray {   //-----------------------------------------------------------------   //  Creates a 2D array of integers, fills it with random   //  integer values, then prints them out.   //-----------------------------------------------------------------   public static void main (String[] args)   {        Random generator = new Random();       int[][] table = new int[20][4];       int X1, X2, X, Y1, Y2, Y, R1, R2, R, Distance;       // Load the table with values       for (int row=0; row < table.length; row++)               for (int col=1; col < table[row].length-1; col++)                       table[row][col] = generator.nextInt(500)+1;             for (int row=0; row < table.length; row++)               for (int col=0; col < table[row].length-3; col++)                       table[row][col] = generator.nextInt(20)+1;             // check for overlap             for (int row=0; row < table.length; row++)                           {        R1=table[row][0];                             X1=table[row][1];                             Y1=table[row][2];                             for (int row2=row+1; row2 < table.length; row2++)                                   {        R2=table[row2][0];                                     X2=table[row2][1];                                     Y2=table[row2][2];                                     X=X1-X2;                                     Y=Y1-Y2;                                     Distance = (int) Math.sqrt(X^2 + Y^2);                                     R=R1+R2;                                     if (Distance<= R)                                             table[row][3]=1;                                   }                                                       }                   // Print the table       for (int row=0; row < table.length; row++)       {         for (int col=0; col < table[row].length; col++)             System.out.print (table[row][col] + "\t");         System.out.println();       }   } }```
My problem is that when I run this is says that every circle but the last one overlaps every time, which I know is not true. Am I missing something when comparing values or what?

any help would be greatly appreciated.
• 04-22-2012, 03:28 AM
milovan
Re: Help determining if Circles overlap
could you print with System.out values of table[row][3] for all your circles and see what their value is?
• 04-22-2012, 03:42 AM
quinnvanorder
Re: Help determining if Circles overlap
This code does that, when run, it will print each value, for instance one run displayed the following
The last column displays the value of what it thinks in terms of overlapping, but when I use this code in my painting program not nearly this many overlap, so there is some sort of logic error in my comparing loop but I cant find it
14 186 24 1
23 191 89 1
19 104 169 1
14 22 14 1
18 154 188 1
24 100 124 1
6 156 177 1
19 198 25 1
17 186 192 1
19 139 31 1
25 119 100 1
20 7 157 1
22 182 37 1
7 71 12 1
15 193 188 1
12 107 170 1
12 163 79 1
17 77 156 1
22 108 92 1
8 93 99 0
• 04-22-2012, 04:49 AM
milovan
Re: Help determining if Circles overlap
Think a little about your overlap algorithm. In the first row loop you will compare first circle with every other circle. So imagine that first next circle is overlaping with the first one. You will asign 1 to table[row][3]. In next loop it might not overlap so what value is then asigned to table[row][3]?
• 04-22-2012, 04:53 AM
al_Marshy_1981
Re: Help determining if Circles overlap
If you have two points on x and y coordinate you use this formula to check intersection.

square root( (x1-x2) 2 + (y1-y2) 2 )
• 04-22-2012, 04:57 AM
al_Marshy_1981
Re: Help determining if Circles overlap
Those 2's outside the bracket should be powers of 2 sorry for the format
• 04-22-2012, 05:16 AM
quinnvanorder
Re: Help determining if Circles overlap
Quote:

Originally Posted by milovan
Think a little about your overlap algorithm. In the first row loop you will compare first circle with every other circle. So imagine that first next circle is overlaping with the first one. You will asign 1 to table[row][3]. In next loop it might not overlap so what value is then asigned to table[row][3]?

I am not sure I understand what you are saying, it assigns a 0 if it does not overlap

Quote:

Originally Posted by al_Marshy_1981
If you have two points on x and y coordinate you use this formula to check intersection.

square root( (x1-x2) 2 + (y1-y2) 2 )

That is the formula that I am using, I believe the error is in the logic of my comparison loop, not in the logic of the distance calculation

I have made a few changes to try to fix it, here is the newer version.. I added an else statement to deal with assigning zero it distance is not less than or equal to "r" and made my calculation more spelled out with an additional step

Code:

```import java.util.Random; public class TwoDArray {   //-----------------------------------------------------------------   //  Creates a 2D array of integers, fills it with random   //  integer values, then prints them out.   //-----------------------------------------------------------------   public static void main (String[] args)   {        Random generator = new Random();       int[][] table = new int[20][4];       int X1, X2, X, Y1, Y2, Y, R1, R2, R, Distance, Temp;       // Load the table with values       for (int row=0; row < table.length; row++)               for (int col=1; col < table[row].length-1; col++)                       table[row][col] = generator.nextInt(500)+1;             for (int row=0; row < table.length; row++)               for (int col=0; col < table[row].length-3; col++)                       table[row][col] = generator.nextInt(20)+1;             // check for overlap             for (int row=0; row < table.length; row++)                           {        R1=table[row][0];                             X1=table[row][1];                             Y1=table[row][2];                             for (int row2=row+1; row2 < table.length; row2++)                                   {        R2=table[row2][0];                                     X2=table[row2][1];                                     Y2=table[row2][2];                                     X=Math.abs(X1-X2);                                     Y=Math.abs(Y1-Y2);                                     Temp = (X^2 + Y^2);                                     Distance = (int) Math.sqrt(Temp);                                     R=R1+R2;                                     //System.out.println("X1: "+X1+" X2: "+X2+"\nY1: " + Y1 + " Y2: "+Y2+"\nX: "+X+" Y: "+Y+"\nDistance: "+Distance+ " " + R+"\ntemp: "+Temp);                                     if (Distance<= R)                                             table[row][3]=1;                                     else                                             table[row][3]=0;                                   }                             System.out.println(" ");                           }                   // Print the table       for (int row=0; row < table.length; row++)       {         for (int col=0; col < table[row].length; col++)             System.out.print (table[row][col] + "\t");         System.out.println();       }   } }```
The commented out System out line I was using to see what it was getting at each step of the calculations
• 04-22-2012, 05:22 AM
milovan
Re: Help determining if Circles overlap
and what is result?
• 04-22-2012, 05:27 AM
quinnvanorder
Re: Help determining if Circles overlap
Quote:

Originally Posted by milovan
and what is result?

My modifications resulted in no change in output. As last time it thinks all but the last one overlap
16 315 363 1
8 258 99 1
4 42 454 1
3 353 438 1
12 366 56 1
8 130 437 1
18 304 270 1
19 459 218 1
14 40 349 1
19 190 149 1
10 98 167 1
4 362 203 1
10 432 400 1
5 269 102 1
8 168 187 1
6 373 234 1
4 14 193 1
14 130 217 1
18 124 202 1
16 413 142 0
• 04-22-2012, 05:40 AM
milovan
Re: Help determining if Circles overlap
Must think a little
• 04-22-2012, 05:45 AM
al_Marshy_1981
Re: Help determining if Circles overlap
Quote:

Originally Posted by milovan
Take closer look what al_Marshy_1981 said in post #5

His formula is sound that was my fault. He dies it in lines of code instead of one. I didn't and should have noticed this.
• 04-22-2012, 05:51 AM
quinnvanorder
Re: Help determining if Circles overlap
I have noticed something else weird, occasionally it will have one or two other zeros, but not nearly enough. When I put this code into my circle class, it colors a lot of circles that are not overlapping as if they were, so although a zero sneaks through occasionally, something is still wrong.
• 04-22-2012, 05:59 AM
al_Marshy_1981
Re: Help determining if Circles overlap
Well this is over my mathematical head. And I know very little. Fubarable or josah might know. So I'd wait around for them.
• 04-22-2012, 06:03 AM
milovan
Re: Help determining if Circles overlap
Quote:

I have noticed something else weird, occasionally it will have one or two other zeros
It is due to two things, one is that your for loops are going through all array. It means if at some point table[row][3] is set to 0 it is still looping so next loop might correct it to 1 again.
But the main problem is with your Distance. It is only showing sqrt of needed length. But my english is not good enough to give you precise explanation..
Correcting main problem will hopefully correct the first one..
• 04-22-2012, 06:18 AM
milovan
Re: Help determining if Circles overlap
Any way, as my math is also not of any use, you must get help from someone else..
• 04-22-2012, 06:19 AM
quinnvanorder
Re: Help determining if Circles overlap
Quote:

Originally Posted by milovan
It is due to two things, one is that your for loops are going through all array. It means if at some point table[row][3] is set to 0 it is still looping so next loop might correct it to 1 again.
But the main problem is with your Distance. It is only showing sqrt of needed length. But my english is not good enough to give you precise explanation..
Correcting main problem will hopefully correct the first one..

But I am trying to get it to compare each value to each other value, so that if it overlaps with any other point, it marks it as a 1. Is this not what is supposed to be happening?
• 04-22-2012, 06:23 AM
milovan
Re: Help determining if Circles overlap
Yeah, you are right. Try this one:

Code:

`Distance = (int) Math.sqrt(X*X + Y*Y);`
• 04-22-2012, 06:32 AM
quinnvanorder
Re: Help determining if Circles overlap
Quote:

Originally Posted by milovan
Yeah, you are right. Try this one:

Code:

`Distance = (int) Math.sqrt(X*X + Y*Y);`

That fixed it! thanks so much!
• 04-22-2012, 06:58 AM
milovan
Re: Help determining if Circles overlap
I would also suggest next changes:

Code:

```for (int row=0; row < table.length; row++){      R1=table[row][0];                    X1=table[row][1];                    Y1=table[row][2];                        for (int row2=0; row2<table.length; row2++){ // corrected row2=row+1 so the result will be total     // number of overlaps and not just first appearance         if(row != row2){  // do not check for same circle, otherways it will always overlap it self             R2=table[row2][0];                                X2=table[row2][1];                                Y2=table[row2][2];                            X=Math.abs(X1-X2);                        Y=Math.abs(Y1-Y2);                        Temp = (X*X + Y*Y);                      Distance = (int) Math.sqrt(Temp);                        R=R1+R2;                          if (Distance<= R){                                        table[row][3]=1;                 break; // when overlaped, break the loop, otherways it will continue for loop and will                 // change table[row][3] to 0             }             else{                                        table[row][3]=0;             }                            System.out.println(" ")       }     } }```