jupdike/IntersectTwoCircles.js

Thanks!

Here's a Unity3D friendly version.

Thanks a lot for this transcription! However I think there might be a mistakate on the line float centerDy = circleB.y - circleB.y;
I imagine it should be float centerDy = circleA.y - circleB.y;, no? Emphasis on circleA.y

Here's an implementation in no_std rust using nalgebra (can be easily substituted with a tuple instead) and num-traits.

#![no_std]
use nalgebra::Point2;
use num_traits::{Float, Pow};

type Point = Point2<f32>

pub fn intersection(
    point1: Point,
    radius1: f32,
    point2: Point,
    radius2: f32,
) -> Option<(Point, Point)> {
    let r1 = radius1.abs();
    let r2 = radius2.abs();

    let x1: f32 = point1.x;
    let y1: f32 = point1.y;

    let x2: f32 = point2.x;
    let y2: f32 = point2.y;

    let cdx: f32 = point1.x - point2.x;
    let cdy: f32 = point1.y - point2.y;

    let dist = (cdx * cdx + cdy * cdy).sqrt();

    if (r1 - r2).abs() > dist || dist > r1 + r2 {
        // no intersection
        return None;
    }

    let dist2 = dist * dist;
    let dist4 = dist2 * dist2;

    let a = (r1 * r1 - r2 * r2) / (2f32 * dist2);
    let r1r2 = r1 * r1 - r2 * r2;
    let c = (2f32 * (r1 * r1 + r2 * r2) / dist2 - (r1r2 * r1r2) / dist4 - 1f32).sqrt();

    let fx = (x1 + x2) / 2f32 + a * (x2 - x1);
    let gx = c * (y2 - y1) / 2f32;

    let fy = (y1 + y2) / 2f32 + a * (y2 - y1);
    let gy = c * (x1 - x2) / 2f32;

    Some((Point::new(fx + gx, fy + gy), Point::new(fx - gx, fy - gy)))
}

Swift:

import Foundation

/**
 Finds the points that intersect two circles.

 If the circles only intersect at one point, then the second point will be
 `nil`.

  Sources:
 
  [gist](https://gist.github.com/jupdike/bfe5eb23d1c395d8a0a1a4ddd94882ac)
 
  [stackexchange](https://math.stackexchange.com/a/1367732/825630)

 - Parameters:
   - center1: The center of the first circle.
   - radius1: The radius of the first circle. Must be positive.
   - center2: The center of the second circle.
   - radius2: The radius of the second circle. Must be positive.
 */
func intersectingPointsOfCircles(
    center1: CGPoint,
    radius1: CGFloat,
    center2: CGPoint,
    radius2: CGFloat
) -> (CGPoint, CGPoint?)? {
    
    if center1 == center2 {
        // If the centers are the same and the radii are the same, then the
        // circles intersect at an infinite number of points, so return `nil`.
        //
        // If the centers are the same, but the radii are different, then there
        // can't be any intersecting points, so also return `nil`.
        return nil
    }

    let centerDx = center1.x - center2.x
    let centerDy = center1.y - center2.y
    
    /// The distance between the centers of the circles
    let d = sqrt(pow(centerDx, 2) + pow(centerDy, 2))

    if abs(radius1 - radius2) > d || d > radius1 + radius2 {
        return nil
    }
    
    let d2 = d * d
    let d4 = d2 * d2
    let a = (radius1 * radius1 - radius2 * radius2) / (2 * d2)
    let r2r2 = (radius1 * radius1 - radius2 * radius2)
    let c = sqrt(
        2 * (radius1 * radius1 + radius2 * radius2) /
        d2 - (r2r2 * r2r2) / d4 - 1
    )
    
    let fx = (center1.x + center2.x) / 2 + a * (center2.x - center1.x)
    let gx = c * (center2.y - center1.y) / 2
    let ix1 = fx + gx
    let ix2 = fx - gx
    
    let fy = (center1.y + center2.y) / 2 + a * (center2.y - center1.y)
    let gy = c * (center1.x - center2.x) / 2
    let iy1 = fy + gy
    let iy2 = fy - gy

    // if gy == 0 and gx == 0, then the circles are tangent and there
    // is only one solution

    let intersectingPoint1 = CGPoint(x: ix1, y: iy1)
    let intersectingPoint2 = CGPoint(x: ix2, y: iy2)
    
    if intersectingPoint1 == intersectingPoint2 {
        return (intersectingPoint1, nil)
    }
    return (intersectingPoint1, intersectingPoint2)
    
}

PHP version

public function intersectTwoCircles($x1, $y1, $r1, $x2, $y2, $r2)
    {
        $centerdx = $x1 - $x2;
        $centerdy = $y1 - $y2;

        $R = sqrt($centerdx * $centerdx + $centerdy * $centerdy);

        if (!(
            abs($r1 - $r2) <= $R && 
            $R <= $r1 + $r2
        )) { // no intersection
            return []; // empty list of results
        }
        // intersection(s) should exist

        $R2 = $R * $R;
        $R4 = $R2 * $R2;
        $a = ($r1 * $r1 - $r2 * $r2) / (2 * $R2);
        $r2r2 = ($r1 * $r1 - $r2 * $r2);
        $c = sqrt(2 * ($r1 * $r1 + $r2 * $r2) / $R2 - ($r2r2 * $r2r2) / $R4 - 1);

        $fx = ($x1 + $x2) / 2 + $a * ($x2 - $x1);
        $gx = $c * ($y2 - $y1) / 2;
        $ix1 = $fx + $gx;
        $ix2 = $fx - $gx;

        $fy = ($y1 + $y2) / 2 + $a * ($y2 - $y1);
        $gy = $c * ($x1 - $x2) / 2;
        $iy1 = $fy + $gy;
        $iy2 = $fy - $gy;

        // note if gy == 0 and gx == 0 then the circles are tangent and there is only one solution
        // but that one solution will just be duplicated as the code is currently written
        return [[$ix1, $iy1], [$ix2, $iy2]];
    }

Python 3.11.2

import math
"""
x1,y1 is the center of the first circle, with radius r1
x2,y2 is the center of the second ricle, with radius r2
"""
def intersectTwoCircles(x1, y1, r1, x2, y2, r2):
    centerdx = x1 - x2
    centerdy = y1 - y2
    R = math.sqrt(centerdx**2 + centerdy**2)
    if not (abs(r1 - r2) <= R and R <= r1 + r2):
        """ No intersections """
        return []

    """ intersection(s) should exist """
    R2 = R**2
    R4 = R2**2
    a = (r1**2 - r2**2) / (2 * R2)
    r2r2 = r1**2 - r2**2
    c = math.sqrt(2 * (r1**2 + r2**2) / R2 - (r2r2**2) / R4 -1)

    fx = (x1 + x2) / 2 + a * (x2 - x1)
    gx = c * (y2 - y1) / 2
    ix1 = fx + gx
    ix2 = fx - gx

    fy = (y1 + y2) / 2 + a * (y2 - y1)
    gy = c * (x1 - x2) / 2
    iy1 = fy + gy
    iy2 = fy - gy

    return [[ix1, iy1], [ix2, iy2]]

Here is an example using turtletoy which is based on Java Script
see: https://turtletoy.net/turtle/c60ea8510d

// Locate the intersection(s) of 2 circles
// thanks to jupdike/IntersectTwoCircles.js
// https://gist.github.com/jupdike/bfe5eb23d1c395d8a0a1a4ddd94882ac

// You can find the Turtle API reference here: https://turtletoy.net/syntax
Canvas.setpenopacity(1);

const radius = 40; // min=5 max=100 step=1
const X1 = -14; // min=-100 max=100 step=1
const Y1 = -12; // min=-100 max=100 step=1
const X2 = 28; // min=-100 max=100 step=1
const Y2 = 23; // min=-100 max=100 step=1

// Global code will be evaluated once.
const turtle = new Turtle();

centeredCircle(X1, Y1, radius, 360);
centeredCircle(X2, Y2, radius, 360);

array_name = intersectTwoCircles(X1, Y1,radius, X2, Y2 ,radius)

// thanks to jupdike/IntersectTwoCircles.js
// https://gist.github.com/jupdike/bfe5eb23d1c395d8a0a1a4ddd94882ac
// based on the math here:
// http://math.stackexchange.com/a/1367732

// x1,y1 is the center of the first circle, with radius r1
// x2,y2 is the center of the second ricle, with radius r2
function intersectTwoCircles(x1,y1,r1, x2,y2,r2) {

var centerdx = x1 - x2;
var centerdy = y1 - y2;
var R = Math.sqrt(centerdx * centerdx + centerdy * centerdy);
if (!(Math.abs(r1 - r2) <= R && R <= r1 + r2)) { // no intersection
return []; // empty list of results
}
// intersection(s) should exist

var R2 = RR;
var R4 = R2R2;
var a = (r1r1 - r2r2) / (2 * R2);
var r2r2 = (r1r1 - r2r2);
var c = Math.sqrt(2 * (r1r1 + r2r2) / R2 - (r2r2 * r2r2) / R4 - 1);

var fx = (x1+x2) / 2 + a * (x2 - x1);
var gx = c * (y2 - y1) / 2;
var ix1 = fx + gx;
var ix2 = fx - gx;

var fy = (y1+y2) / 2 + a * (y2 - y1);
var gy = c * (x1 - x2) / 2;
var iy1 = fy + gy;
var iy2 = fy - gy;

centeredCircle(ix1, iy1, 2, 360); // highlight intersection point 1
centeredCircle(ix2, iy2, 2, 360); // highlight intersection point 1

// note if gy == 0 and gx == 0 then the circles are tangent and there is only one solution
// but that one solution will just be duplicated as the code is currently written
return [ix1, iy1, ix2, iy2];
}

// thanks to Reinder for this function
// Draws a circle centered a specific x,y location
// and returns the turtle to the original angle after it completes the circle.
function centeredCircle(x,y, radius, ext) {
turtle.penup();
turtle.goto(x,y);
turtle.backward(radius);
turtle.left(90);
turtle.pendown(); turtle.circle(radius, ext);
turtle.right(90); turtle.penup(); turtle.forward(radius); turtle.pendown();
}

Comparing with the math, shouldn't the denominator in line 17 be 2 * R instead of 2 * R2?
(I know this is an old thread, but still clarifying for those who use this as reference)

Never mind, I got confused by the similar notation of the math and the code! 2 * R2 is correct for a

Thanks for posting! Here's a compatible Rust version!

struct Point2 {
    x: f64,
    y: f64,
}

struct Circle2 {
    center: Point2,
    radius: f64,
}


pub fn circle_intersection(&self, circle_a: &Circle2, circle_b: &Circle2) -> Vec<Point2> {
    let center_a = circle_a.center;
    let center_b = circle_b.center;
    let r_a = circle_a.radius;
    let r_b = circle_b.radius;

    let center_dx = center_b.x - center_a.x;
    let center_dy = center_b.y - center_a.y;
    let center_dist = center_dx.hypot(center_dy);

    if !(center_dist <= r_a + r_b && center_dist >= r_a - r_b) {
        return vec![];
    }

    let r_2 = center_dist * center_dist;
    let r_4 = r_2 * r_2;
    let a = (r_a * r_a - r_b * r_b) / (2.0 * r_2);
    let r_2_r_2 = r_a * r_a - r_b * r_b;
    let c = (2.0 * (r_a * r_a + r_b * r_b) / r_2 - r_2_r_2 * r_2_r_2 / r_4 - 1.0).sqrt();

    let fx = (center_a.x + center_b.x) / 2.0 + a * (center_b.x - center_a.x);
    let gx = c * (center_b.y - center_a.y) / 2.0;
    let ix1 = fx + gx;
    let ix2 = fx - gx;

    let fy = (center_a.y + center_b.y) / 2.0 + a * (center_b.y - center_a.y);
    let gy = c * (center_a.x - center_b.x) / 2.0;
    let iy1 = fy + gy;
    let iy2 = fy - gy;

    vec![Point2 { x: ix1, y: iy1 }, Point2 { x: ix2, y: iy2}]
}