-
-
Save jupdike/bfe5eb23d1c395d8a0a1a4ddd94882ac to your computer and use it in GitHub Desktop.
| // 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]]; | |
| } |
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!
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
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)
}
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
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!
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))
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`
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)
`
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}]
}
A simple TypeScript adaptation:
interface Point {
x: number;
y: number;
}
interface Circle {
cx: number;
cy: number;
r: number;
}
const intersectCircleCircle = (c1: Circle, c2: Circle): Point[] => {
const { cx: x1, cy: y1, r: r1 } = c1;
const { cx: x2, cy: y2, r: r2 } = c2;
const centerdx = x1 - x2;
const centerdy = y1 - y2;
const 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
const R2 = R * R;
const R4 = R2 * R2;
const a = (r1 * r1 - r2 * r2) / (2 * R2);
const r2r2 = r1 * r1 - r2 * r2;
const c = Math.sqrt((2 * (r1 * r1 + r2 * r2)) / R2 - (r2r2 * r2r2) / R4 - 1);
const fx = (x1 + x2) / 2 + a * (x2 - x1);
const gx = (c * (y2 - y1)) / 2;
const ix1 = fx + gx;
const ix2 = fx - gx;
const fy = (y1 + y2) / 2 + a * (y2 - y1);
const gy = (c * (x1 - x2)) / 2;
const iy1 = fy + gy;
const 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 [
{ x: ix1, y: iy1 },
{ x: ix2, y: iy2 },
];
};
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