Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Find the intersections (two points) of two circles, if they intersect at all
// 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 = R*R;
var R4 = R2*R2;
var a = (r1*r1 - r2*r2) / (2 * R2);
var r2r2 = (r1*r1 - r2*r2);
var c = Math.sqrt(2 * (r1*r1 + r2*r2) / 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;
// 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]];
}
@wikiwebs

This comment has been minimized.

Copy link

@wikiwebs wikiwebs commented Jun 10, 2018

Thanks Juppy :-)

I had to convert this to VB.Net but worked sweet with only 1 minor tweak. for calculation of var c
`

    Private Function IntersectTwoCircles(x1%, y1%, r1%, x2%, y2%, r2%) As Integer()
    '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
    Dim centerdx% = x1 - x2
    Dim centerdy% = y1 - y2
    Dim R = Math.Sqrt(centerdx * centerdx + centerdy * centerdy)


    If (Not (Math.Abs(r1 - r2) <= R) And (R <= r1 + r2)) Then
        ' no intersection
        Return Nothing ' empty list of results
    End If

    'intersection(s) should exist

    Dim R_2 = R * R
    Dim R_4 = R_2 * R_2
    Dim a = (r1 * r1 - r2 * r2) / (2 * R_2)
    Dim r2r2 = (r1 * r1 - r2 * r2)

    Dim c1 As Double = 2 * (r1 * r1 + r2 * r2) / R_2 ' As Double because default is Integer
    Dim c2 As Double = r2r2   'seperate c2 calculation avoids Integer overflow 
    c2 = (c2 * c2) / R_4        'recycle c2 
    Dim c = Math.Sqrt(c1 - c2 - 1)

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

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

    '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}


End Function

`

@mandarinx

This comment has been minimized.

Copy link

@mandarinx mandarinx commented Jul 25, 2018

Thanks!

Here's a Unity3D friendly version.

using UnityEngine;

namespace C2Intersection {

    // based on the math here:
    // http://math.stackexchange.com/a/1367732
    // based on the code from:
    // https://gist.github.com/jupdike/bfe5eb23d1c395d8a0a1a4ddd94882ac
    public static class CircleCircleIntersection {

        // circleA is the center of the first circle, with radius radiusA
        // circleB is the center of the second circle, with radius radiusB
        public static int Intersect(Vector2       circleA,
                                    float         radiusA,
                                    Vector2       circleB,
                                    float         radiusB,
                                    out Vector2[] intersections) {

            float centerDx = circleA.x - circleB.x;
            float centerDy = circleB.y - circleB.y;
            float r = Mathf.Sqrt(centerDx * centerDx + centerDy * centerDy);

            // no intersection
            if (!(Mathf.Abs(radiusA - radiusB) <= r && r <= radiusA + radiusB)) {
                intersections = new Vector2[0];
                return 0;
            }

            float r2d = r * r;
            float r4d = r2d * r2d;
            float rASquared = radiusA * radiusA;
            float rBSquared = radiusB * radiusB;
            float a = (rASquared - rBSquared) / (2 * r2d);
            float r2r2 = (rASquared - rBSquared);
            float c = Mathf.Sqrt(2 * (rASquared + rBSquared) / r2d - (r2r2 * r2r2) / r4d - 1);

            float fx = (circleA.x + circleB.x) / 2 + a * (circleB.x - circleA.x);
            float gx = c * (circleB.y - circleA.y) / 2;
            float ix1 = fx + gx;
            float ix2 = fx - gx;

            float fy = (circleA.y + circleB.y) / 2 + a * (circleB.y - circleA.y);
            float gy = c * (circleA.x - circleB.x) / 2;
            float iy1 = fy + gy;
            float iy2 = fy - gy;

            // if gy == 0 and gx == 0 then the circles are tangent and there is only one solution
            if (Mathf.Abs(gx) < float.Epsilon && Mathf.Abs(gy) < float.Epsilon) {
                intersections = new [] {
                    new Vector2(ix1, iy1)
                };
                return 1;
            }

            intersections = new [] {
                new Vector2(ix1, iy1),
                new Vector2(ix2, iy2),
            };
            return 2;
        }
    }
}

A usage example:

using mlib;
using UnityEngine;

namespace C2Intersection {

    public class IntersectionViz : MonoBehaviour {

        [SerializeField]
        private Transform circleA;
        [SerializeField]
        private float     radiusA;
        [SerializeField]
        private Color     colorA;
        [SerializeField]
        private Transform circleB;
        [SerializeField]
        private float     radiusB;
        [SerializeField]
        private Color     colorB;

        private void OnDrawGizmos() {
            GizmoUtils.DrawCircle(circleA.position, radiusA, colorA);
            GizmoUtils.DrawCircle(circleB.position, radiusB, colorB);
            Vector2[] intersections;
            int num = CircleCircleIntersection.Intersect(circleA.position,
                                                         radiusA,
                                                         circleB.position,
                                                         radiusB,
                                                         out intersections);

            Gizmos.color = Color.cyan;
            for (int i = 0; i < num; ++i) {
                Gizmos.DrawSphere(intersections[i], 0.25f);
            }
        }
    }
}

GimoUtils.DrawCircle is a utility method for drawing circles as gizmos. It looks like this:

using UnityEngine;

namespace mlib {

    public static class GizmoUtils {

        public static void DrawCircle(Vector3 position, float radius, Color color) {
            float err = 1f;
            Gizmos.color = color;
            float theta = 0f;
            float x = radius * Mathf.Cos(theta);
            float y = radius * Mathf.Sin(theta);
            Vector3 pos = position + new Vector3(x, y, 0f);
            Vector3 lastPos = pos;
            const float TWOPI = Mathf.PI * 2;
            const float inc = 0.4f;
            for (theta = inc; theta < TWOPI; theta += inc) {
                x = radius * Mathf.Cos(theta);
                y = radius * Mathf.Sin(theta);
                Vector3 newPos = position + new Vector3(x, y, 0f);
                Gizmos.DrawLine(pos, newPos);
                pos = newPos;
            }

            Gizmos.DrawLine(pos, lastPos);
        }
    }
}
@arkonique

This comment has been minimized.

Copy link

@arkonique arkonique commented Nov 21, 2018

Here is a FORTRAN 95 version which I had to write. A subroutine based on your code, except that it returns each coordinate separately. For this, I had to include another parameter, the 'flag' which checks if the intersection exists at all. I needed each of the intersection points as separate variables so ....

subroutine intersect2circles(x1,y1,r1,x2,y2,r2,ix1,iy1,ix2,iy2,flag)
	implicit none
	real(8),intent(in) :: x1,y1,r1,x2,y2,r2
	real(8),intent(out) :: ix1,iy1,ix2,iy2
	integer,intent(out) :: flag
	real(8) centerdx,centerdy,R,Rsq,Rquad,a,r2r2,c,fx,gx,fy,gy
	flag=0 ! This checks whether there is an intersection or not, since we cannot return empty variables in fortran as far as I know
	centerdx=x1-x2
	centerdy=y1-y2
	R=sqrt(centerdx**2+centerdy**2)
	if (.not.(abs(r1-r2)<=R.and.R<=r1+r2)) then
		print*, "No intersection, setting intersection points to 0,0, and setting flag to 1"
		ix1=0
		iy1=0
		ix2=0
		iy2=0
		flag=1
		return
	endif
	Rsq=R*R
	Rquad=Rsq*Rsq
	a=(r1**2-r2**2)/(2*Rsq)
	r2r2=(r1**2-r2**2)
	c=sqrt(2*(r1**2+r2**2)/Rsq - (r2r2**2)/Rquad -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
end subroutine intersect2circles
@josephftaylor

This comment has been minimized.

Copy link

@josephftaylor josephftaylor commented Feb 19, 2019

Hi,

Is someone able to comment the purposes of each variable? I've commented what I understand, but I would like to undestand the rest. For example, why do we have R2 and R4, is it just to neaten up the code or is there another reason. Why are fx and gx calculated in the ways they are?

Many thanks

  var centerdx = x1 - x2; // distance between x points of both circles
  var centerdy = y1 - y2; // distance between y points of both circles
  var R = Math.sqrt(centerdx * centerdx + centerdy * centerdy); // distance between centres of circles

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

  var fx = (x1+x2) / 2 + a * (x2 - x1);
  var gx = c * (y2 - y1) / 2;
  var ix1 = fx + gx; // 1st intersect x-coordinate
  var ix2 = fx - gx; // 2nd intersect x-coordinate

  var fy = (y1+y2) / 2 + a * (y2 - y1);
  var gy = c * (x1 - x2) / 2;
  var iy1 = fy + gy; // 1st intersect y-coordinate
  var iy2 = fy - gy; // 2nd intersect y-coordinate
@EdelweissPirate

This comment has been minimized.

Copy link

@EdelweissPirate EdelweissPirate commented Jul 6, 2020

Hi,

Is someone able to comment the purposes of each variable? I've commented what I understand, but I would like to undestand the rest. For example, why do we have R2 and R4, is it just to neaten up the code or is there another reason. Why are fx and gx calculated in the ways they are?

Many thanks

  var centerdx = x1 - x2; // distance between x points of both circles
  var centerdy = y1 - y2; // distance between y points of both circles
  var R = Math.sqrt(centerdx * centerdx + centerdy * centerdy); // distance between centres of circles

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

  var fx = (x1+x2) / 2 + a * (x2 - x1);
  var gx = c * (y2 - y1) / 2;
  var ix1 = fx + gx; // 1st intersect x-coordinate
  var ix2 = fx - gx; // 2nd intersect x-coordinate

  var fy = (y1+y2) / 2 + a * (y2 - y1);
  var gy = c * (x1 - x2) / 2;
  var iy1 = fy + gy; // 1st intersect y-coordinate
  var iy2 = fy - gy; // 2nd intersect y-coordinate

Hi man - Im not too great on maths either but the R2 and R4 are meant to represent R squared and R cubed.

No clue what the rest means I'm afraid!

@jupdike

This comment has been minimized.

Copy link
Owner Author

@jupdike jupdike commented Jul 8, 2020

r2 is r squared and r4 is r2 squared, or fourth power (not cubed). This saves computation. Same with fx and gx and fy and gy. They are just places to put values to be reused, for performance. 'c' is a big constant that takes a lot of computation, so is only computed once. It has been so long since I put this code here I don't really remember what the meaning of each line is, but if you care about it, you can check the Math StackExchange link for the original math and the actual formula which I translated into code: http://math.stackexchange.com/a/1367732

@emiguelt

This comment has been minimized.

Copy link

@emiguelt emiguelt commented Oct 9, 2020

Thanks, very helpful, I translated it to Kotlin:

// x1,y1 is the center of the first circle, with radius r1
// x2,y2 is the center of the second ricle, with radius r2
fun intersectTwoCircles( x1: Double,y1: Double,r1: Double, x2: Double,y2: Double,r2: Double):List<Pair<Double, Double>> {
    val centerdx = x1 - x2;
    val centerdy = y1 - y2;
    val R = Math.sqrt(centerdx * centerdx + centerdy * centerdy);
    if (!(Math.abs(r1 - r2) <= R && R <= r1 + r2)) { // no intersection
        return emptyList(); // empty list of results
    }
    // intersection(s) should exist

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

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

    val fy = (y1+y2) / 2 + a * (y2 - y1);
    val gy = c * (x1 - x2) / 2;
    val iy1 = fy + gy;
    val 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 listOf(ix1 to iy1, ix2 to iy2)
}
@EdelweissPirate

This comment has been minimized.

Copy link

@EdelweissPirate EdelweissPirate commented Oct 9, 2020

r2 is r squared and r4 is r2 squared, or fourth power (not cubed). This saves computation. Same with fx and gx and fy and gy. They are just places to put values to be reused, for performance. 'c' is a big constant that takes a lot of computation, so is only computed once. It has been so long since I put this code here I don't really remember what the meaning of each line is, but if you care about it, you can check the Math StackExchange link for the original math and the actual formula which I translated into code: http://math.stackexchange.com/a/1367732

Hi man - late reply but thanks for the correction. Cubed would have been to the power of 8, of course! And thank you for the rest of the explanation

@jupdike

This comment has been minimized.

Copy link
Owner Author

@jupdike jupdike commented Oct 9, 2020

Cubed is to the power of 3, for anyone who sees this thread. I'm glad the explanation was at all helpful. Code I wrote a long time ago!

@Kienyew

This comment has been minimized.

Copy link

@Kienyew Kienyew commented Dec 19, 2020

If someone need some dirty legal python expression (might also be legal in other languages) of all the intersection points, here is this (sorry):

ix1 = (-r1**2*x1 + r1**2*x2 + r2**2*x1 - r2**2*x2 + x1**3 - x1**2*x2 - x1*x2**2 + x1*y1**2 - 2*x1*y1*y2 + x1*y2**2 + x2**3 + x2*y1**2 - 2*x2*y1*y2 + x2*y2**2 + sqrt((-r1**2 + 2*r1*r2 - r2**2 + x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)*(r1**2 + 2*r1*r2 + r2**2 - x1**2 + 2*x1*x2 - x2**2 - y1**2 + 2*y1*y2 - y2**2))*(-y1 + y2))/(2*(x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2))

ix2 = (-r1**2*x1 + r1**2*x2 + r2**2*x1 - r2**2*x2 + x1**3 - x1**2*x2 - x1*x2**2 + x1*y1**2 - 2*x1*y1*y2 + x1*y2**2 + x2**3 + x2*y1**2 - 2*x2*y1*y2 + x2*y2**2 + sqrt((-r1**2 + 2*r1*r2 - r2**2 + x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)*(r1**2 + 2*r1*r2 + r2**2 - x1**2 + 2*x1*x2 - x2**2 - y1**2 + 2*y1*y2 - y2**2))*(y1 - y2))/(2*(x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2))

iy1 = (-r1**2 + r2**2 + y1**2 - y2**2 + (-x1 + (-r1**2*x1 + r1**2*x2 + r2**2*x1 - r2**2*x2 + x1**3 - x1**2*x2 - x1*x2**2 + x1*y1**2 - 2*x1*y1*y2 + x1*y2**2 + x2**3 + x2*y1**2 - 2*x2*y1*y2 + x2*y2**2 + sqrt((-r1**2 + 2*r1*r2 - r2**2 + x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)*(r1**2 + 2*r1*r2 + r2**2 - x1**2 + 2*x1*x2 - x2**2 - y1**2 + 2*y1*y2 - y2**2))*(-y1 + y2))/(2*(x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)))**2 - (-x2 + (-r1**2*x1 + r1**2*x2 + r2**2*x1 - r2**2*x2 + x1**3 - x1**2*x2 - x1*x2**2 + x1*y1**2 - 2*x1*y1*y2 + x1*y2**2 + x2**3 + x2*y1**2 - 2*x2*y1*y2 + x2*y2**2 + sqrt((-r1**2 + 2*r1*r2 - r2**2 + x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)*(r1**2 + 2*r1*r2 + r2**2 - x1**2 + 2*x1*x2 - x2**2 - y1**2 + 2*y1*y2 - y2**2))*(-y1 + y2))/(2*(x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)))**2)/(2*(y1 - y2))

iy2 = (-r1**2 + r2**2 + y1**2 - y2**2 + (-x1 + (-r1**2*x1 + r1**2*x2 + r2**2*x1 - r2**2*x2 + x1**3 - x1**2*x2 - x1*x2**2 + x1*y1**2 - 2*x1*y1*y2 + x1*y2**2 + x2**3 + x2*y1**2 - 2*x2*y1*y2 + x2*y2**2 + sqrt((-r1**2 + 2*r1*r2 - r2**2 + x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)*(r1**2 + 2*r1*r2 + r2**2 - x1**2 + 2*x1*x2 - x2**2 - y1**2 + 2*y1*y2 - y2**2))*(y1 - y2))/(2*(x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)))**2 - (-x2 + (-r1**2*x1 + r1**2*x2 + r2**2*x1 - r2**2*x2 + x1**3 - x1**2*x2 - x1*x2**2 + x1*y1**2 - 2*x1*y1*y2 + x1*y2**2 + x2**3 + x2*y1**2 - 2*x2*y1*y2 + x2*y2**2 + sqrt((-r1**2 + 2*r1*r2 - r2**2 + x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)*(r1**2 + 2*r1*r2 + r2**2 - x1**2 + 2*x1*x2 - x2**2 - y1**2 + 2*y1*y2 - y2**2))*(y1 - y2))/(2*(x1**2 - 2*x1*x2 + x2**2 + y1**2 - 2*y1*y2 + y2**2)))**2)/(2*(y1 - y2))
@coffeeicecubes

This comment has been minimized.

Copy link

@coffeeicecubes coffeeicecubes commented Jan 11, 2021

Python

def intersect(x1, y1, r1, x2, y2, r2):
    centerdx = x1 - x2
    centerdy = y1 - y2
    R = sqrt(centerdx * centerdx + centerdy * centerdy)
    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`
@kubolko

This comment has been minimized.

Copy link

@kubolko kubolko commented Feb 14, 2021

Here is the code in Swift 5:
`
import Cocoa

struct circle{
let x: Double
let y: Double
let radius: Double
}
struct point{
let x: Double
let y: Double
}

func getCooridantes(circle1 : circle, circle2: circle) -> [point]{

let centerdx : Double = circle1.x - circle2.x
let centerdy : Double = circle1.y - circle1.y
let R = sqrt(centerdx * centerdx + centerdy * centerdy)

if (!(abs(circle1.radius - circle2.radius) <= R && R <= circle1.radius + circle2.radius)){
   
    return [point(x: 0, y: 0)]
}

let R2 = R*R;
let R4 = R2*R2;
let a = (circle1.radius * circle1.radius - circle2.radius * circle2.radius) / (2 * R2);
let r2r2 = (circle1.radius * circle1.radius - circle2.radius * circle2.radius);
let c = sqrt(2 * (circle1.radius * circle1.radius + circle2.radius * circle2.radius) / R2 - (r2r2 * r2r2) / R4 - 1);

let fx = (circle1.x+circle2.x) / 2 + a * (circle2.x - circle1.x);
let gx = c * (circle2.y - circle1.y) / 2;
let ix1 = fx + gx;
let ix2 = fx - gx;

let fy = (circle1.y + circle2.y) / 2 + a * (circle2.y - circle1.y);
let gy = c * (circle1.x - circle2.x) / 2;
let iy1 = fy + gy;
let iy2 = fy - gy;
print(ix1 ,iy1)
print(ix2, iy2)

// 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 [point(x: ix1, y: iy1), point(x: ix2, y: iy2)]

}

let circle1test = circle(x: 0, y: 0, radius: 10)
let circle2test = circle(x: 10, y: 0, radius: 3)
getCooridantes(circle1: circle1test, circle2: circle2test)
`

@pgrenon1

This comment has been minimized.

Copy link

@pgrenon1 pgrenon1 commented Jul 29, 2021

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment