Make delicious recipes!

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:

Facebook comments:

Site Owner: Sachin Goyal