# Thread: Help determining if Circles overlap

1. Member
Join Date
Feb 2012
Posts
31
Rep Power
0

## 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
Java 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.

2. Senior Member
Join Date
Jan 2011
Location
Posts
311
Rep Power
7

## 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?

3. Member
Join Date
Feb 2012
Posts
31
Rep Power
0

## 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
Last edited by quinnvanorder; 04-22-2012 at 03:43 AM. Reason: Spelling

4. Senior Member
Join Date
Jan 2011
Location
Posts
311
Rep Power
7

## 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]?

5. Senior Member
Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
8

## 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 )

6. Senior Member
Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
8

## Re: Help determining if Circles overlap

Those 2's outside the bracket should be powers of 2 sorry for the format

7. Member
Join Date
Feb 2012
Posts
31
Rep Power
0

## Re: Help determining if Circles overlap

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

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

Java 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
Last edited by quinnvanorder; 04-22-2012 at 05:22 AM.

8. Senior Member
Join Date
Jan 2011
Location
Posts
311
Rep Power
7

## Re: Help determining if Circles overlap

and what is result?

9. Member
Join Date
Feb 2012
Posts
31
Rep Power
0

## Re: Help determining if Circles overlap

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

10. Senior Member
Join Date
Jan 2011
Location
Posts
311
Rep Power
7

## Re: Help determining if Circles overlap

Must think a little
Last edited by milovan; 04-22-2012 at 05:44 AM.

11. Senior Member
Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
8

## Re: Help determining if Circles overlap

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.

12. Member
Join Date
Feb 2012
Posts
31
Rep Power
0

## 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.

13. Senior Member
Join Date
Feb 2010
Location
Waterford, Ireland
Posts
748
Rep Power
8

## 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.

14. Senior Member
Join Date
Jan 2011
Location
Posts
311
Rep Power
7

## Re: Help determining if Circles overlap

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..
Last edited by milovan; 04-22-2012 at 06:08 AM. Reason: correction

15. Senior Member
Join Date
Jan 2011
Location
Posts
311
Rep Power
7

## Re: Help determining if Circles overlap

Any way, as my math is also not of any use, you must get help from someone else..

16. Member
Join Date
Feb 2012
Posts
31
Rep Power
0

## Re: Help determining if Circles overlap

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?

17. Senior Member
Join Date
Jan 2011
Location
Posts
311
Rep Power
7

## Re: Help determining if Circles overlap

Yeah, you are right. Try this one:

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

18. Member
Join Date
Feb 2012
Posts
31
Rep Power
0

## Re: Help determining if Circles overlap

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

Java Code:
`Distance = (int) Math.sqrt(X*X + Y*Y);`
That fixed it! thanks so much!

19. Senior Member
Join Date
Jan 2011
Location
Posts
311
Rep Power
7

## Re: Help determining if Circles overlap

I would also suggest next changes:

Java 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(" ")
}
}
}```
Last edited by milovan; 04-22-2012 at 07:15 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•