Data Structuresand Algorithms Good OldJava AdvancedInterview Topics Cloud andDatabases Web Designand Development Must-knowTools Good ToKnow

## Count number of circle intersections

Problem: Given an array of integers where array[i] represents the radius of a circle at point (0,i)
Find the number of intersections of all the circles formed by the above array.

Example: If given array is [2,1,3], then 3 circles would be formed whose end-points would be: [-2,2], [0,2] and [-1,5] Solution:
An O(n2) solution can be done very simply using the following properties:
(Assuming R1 > R2):
1. Two circles do not intersect if their centers are more than R1 + R2 distance apart.
2. Two circles intersect once if their centers are exactly R1 + R2 distance apart.
3. Two circles intersect twice if their centers are less than R1 + R2 distance apart.
4. Two circles intersect once if their centers are exactly R1 - R2 distance apart.
5. Two circles do not intersect if their centers are less than R1 - R2 distance apart.

Using the above properties, compare each circle with rest of the circles and count the number of intersections.

### A possible solution to think about

1. Find the end-points corresponding to each circle.
2. Mark start points with a flag.
3. Sort the end-points.
4. Loop over the end-points.
1. Count the number of start-points (denoting open intervals till now).
Increment openCount by 1 if start point is encountered, else decrement by 1.
2. Whenever a start-point is encountered, increment intersectionCount by openCount.
Code:
```
import java.util.*;

public class CircleIntersections
{

// class to store one end of a circle.
// flag 'isStart' tells whether the point is start-point or end-point
public static class EndPoint
{
public int point;
public boolean isStart;

public EndPoint(int point, boolean isStart)
{
this.point = point;
this.isStart = isStart;
}
}

// comparator for class end-point
public static class EndPointCmp implements Comparator<EndPoint>
{
@Override
public int compare(EndPoint o1, EndPoint o2)
{
return o1.point - o2.point;
}

}

// Main method to find the number of intersections
public static void main(String[] args)
{
int numCircles = 5;

int[] arr = getRandomCircles(numCircles);

EndPoint[] points = getCircleEndPoints(numCircles, arr);

Arrays.sort(points, new EndPointCmp());

int startPoints   = 0;
int intersections = 0;
for (int i=0; i<points.length; i++)
{
if (points[i].isStart)
{
// Whenever a new circle start point comes in, it intersects all open circles
intersections += startPoints;
startPoints++;
}
else
{
// Very Important: A circle end point need not be counted an intersection
startPoints--;
}
}

System.out.println ("Intersections = " + intersections);
}

// Each circle generates two end-points: start and end
// So return array size is twice the size of input array
static EndPoint[] getCircleEndPoints(int numCircles, int[] arr)
{
EndPoint points[] = new EndPoint[2*numCircles];

for (int i=0; i<numCircles; i++)
{
points[2*i]   = new EndPoint (i - arr[i], true);
points[2*i+1] = new EndPoint (i + arr[i], false);

System.out.println ("center=" + i + ", radius=" + arr[i] + " Ends: (" + points[2*i].point + " to " + points[2*i +1].point + ")");
}
return points;
}

// Helper method to get some random circles
static int[] getRandomCircles(int numCircles)
{
int arr[] = new int[numCircles];

for (int i=0; i<numCircles; i++)
arr[i] = 1+(int)(Math.random()*numCircles*0.5);

return arr;
}
}

```

Sample executions:

```
3 circles:
center=0, radius=2 Ends: (-2 to 2)
center=1, radius=2 Ends: (-1 to 3)
center=2, radius=2 Ends: (0 to 4)
Intersections = 3

4 circles:
center=0, radius=2 Ends: (-2 to 2)
center=1, radius=2 Ends: (-1 to 3)
center=2, radius=1 Ends: (1 to 3)
center=3, radius=1 Ends: (2 to 4)
Intersections = 5

5 circles:
center=0, radius=1 Ends: (-1 to 1)
center=1, radius=2 Ends: (-1 to 3)
center=2, radius=1 Ends: (1 to 3)
center=3, radius=2 Ends: (1 to 5)
center=4, radius=1 Ends: (3 to 5)
Intersections = 5

```

Like us on Facebook to remain in touch
with the latest in technology and tutorials!

Got a thought to share or found a
bug in the code?
We'd love to hear from you:

 Name: Email: (Your email is not shared with anybody) Comment: