Circle-Circle Intersection - Software Development PDF Download

Introduction

In competitive programming, it is often required to find the intersection points between two circles. This problem arises in various scenarios, such as determining the collision of two objects or calculating the common area between circles. In this article, we will explore an efficient algorithm to solve the circle-circle intersection problem and provide examples and practice problems to help you master this concept.

Problem Statement

Given two circles defined by their center coordinates (x1, y1) and (x2, y2) and their respective radii r1 and r2, our task is to find the intersection points (if any) between the two circles.

Solution

To find the intersection points between two circles, we can follow these steps:

• Calculate the distance between the centers of the circles.
• Determine if the circles are disjoint (no intersection), one circle is contained within the other, or if they intersect at two points.
• If the circles intersect at two points, calculate the coordinates of the intersection points.
• Return the intersection points.

Let's dive into each step in more detail.

Step 1: Calculate the distance between the centers of the circles

The distance between two points (x1, y1) and (x2, y2) can be calculated using the Euclidean distance formula:

distance = sqrt((x2 - x1)^2 + (y2 - y1)^2)

Step 2: Determine the type of intersection

We can determine the type of intersection between two circles based on their radii and the distance between their centers.

• Disjoint Circles: If the distance between the centers is greater than the sum of the radii, the circles are disjoint, and there is no intersection.
• One Circle Contained Within the Other: If the distance between the centers is less than the absolute difference of the radii, one circle is entirely contained within the other, and there is no intersection.
• Two Intersection Points: If neither of the above conditions is met, the circles intersect at two points.

Step 3: Calculate the coordinates of the intersection points

To calculate the coordinates of the intersection points, we can use the properties of similar triangles and trigonometry. Here's an algorithm to find the intersection points:

• Calculate the distance from the first circle's center to the line connecting the intersection points.
• Calculate the length of the line segment connecting the centers of the circles.
• Calculate the angle between the line segment connecting the centers and the x-axis.
• Calculate the distances from the centers of the circles to the intersection points using the law of sines and the angle calculated in the previous step.

Step 4: Return the intersection points

After calculating the coordinates of the intersection points, return them as the output of the algorithm.

Example

Let's consider an example to illustrate the circle-circle intersection algorithm:

Given:

• Circle 1: Center = (2, 3), Radius = 4
• Circle 2: Center = (7, 5), Radius = 3

We can follow the steps mentioned in the solution:

(i) Calculate the distance between the centers of the circles:

distance = sqrt((7 - 2)^2 + (5 - 3)^2) = sqrt(25 + 4) = sqrt(29)

(ii) Determine the type of intersection:

• The distance between the centers (sqrt(29)) is less than the sum of the radii (4 + 3). Therefore, the circles are not disjoint.
• The distance between the centers (sqrt(29)) is not less than the absolute difference of the radii (|4 - 3|). Therefore, one circle is not contained within the other.

(iii) Calculate the coordinates of the intersection points:

• To find the intersection points, we need to calculate the distances from the centers of the circles to the intersection points.

(iv) Return the intersection points:

• The coordinates of the intersection points are the solutions to the problem.

Algorithm Implementation

Here is a sample algorithm in Python to find the intersection points between two circles:

import math

def circle_circle_intersection(x1, y1, r1, x2, y2, r2):

    distance = math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

    

    if distance > r1 + r2:

        # Disjoint circles

        return []

    

    if distance < abs(r1 - r2):

        # One circle contained within the other

        return []

    

    if distance == 0 and r1 == r2:

        # Circles are coincident

        return []

    

    a = (r1**2 - r2**2 + distance**2) / (2 * distance)

    h = math.sqrt(r1**2 - a**2)

    

    x3 = x1 + a * (x2 - x1) / distance

    y3 = y1 + a * (y2 - y1) / distance

    

    x4 = x3 + h * (y2 - y1) / distance

    y4 = y3 - h * (x2 - x1) / distance

    

    x5 = x3 - h * (y2 - y1) / distance

    y5 = y3 + h * (x2 - x1) / distance

    

    return [(x4, y4), (x5, y5)]

Practice Problems

• Codeforces: Circle of Monsters
• Codeforces: Petya and White Circle
• Codeforces: Checkpoints

Solving these practice problems will help you gain a better understanding of the circle-circle intersection concept and strengthen your competitive programming skills.

Conclusion

In this article, we explored the circle-circle intersection problem and provided a detailed algorithm to find the intersection points between two circles. We also covered an example to illustrate the algorithm and suggested practice problems to further enhance your skills. By mastering the circle-circle intersection concept, you'll be better equipped to tackle similar problems in competitive programming competitions.