-
-
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]]; | |
} |
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 },
];
};
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))
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
`
Godot script
func intersect_two_circles(x1: float, y1: float, r1: float, x2: float, y2: float, r2: float) -> Array:
var centerdx = x1 - x2
var centerdy = y1 - y2
var R = sqrt(centerdx * centerdx + centerdy * centerdy)
if not (abs(r1 - r2) <= R and R <= r1 + r2):
return [] # Tidak ada titik perpotongan
# Perhitungan titik potong
var R2 = R * R
var R4 = R2 * R2
var a = (r1 * r1 - r2 * r2) / (2 * R2)
var r2r2 = (r1 * r1 - r2 * r2)
var c = 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
# Mengembalikan titik-titik perpotongan
return [[ix1, iy1], [ix2, iy2]]
Python visual
import math
import matplotlib.pyplot as plt
def intersect_two_circles(x1, y1, r1, x2, y2, r2):
centerdx = x1 - x2
centerdy = y1 - y2
R = math.sqrt(centerdx2 + centerdy2)
if not (abs(r1 - r2) <= R <= r1 + r2):
return [] # Tidak ada titik perpotongan
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, ix2 = fx + gx, fx - gx
fy = (y1 + y2) / 2 + a * (y2 - y1)
gy = c * (x1 - x2) / 2
iy1, iy2 = fy + gy, fy - gy
return [(ix1, iy1), (ix2, iy2)]
Contoh posisi dan radius lingkaran
x1, y1, r1 = 0, 0, 5
x2, y2, r2 = 4, 0, 3
Hitung titik potong
intersection_points = intersect_two_circles(x1, y1, r1, x2, y2, r2)
Visualisasi
fig, ax = plt.subplots()
circle1 = plt.Circle((x1, y1), r1, color='blue', fill=False)
circle2 = plt.Circle((x2, y2), r2, color='red', fill=False)
ax.add_patch(circle1)
ax.add_patch(circle2)
Plot titik potong
for (ix, iy) in intersection_points:
plt.plot(ix, iy, 'go', label=f'({ix:.2f}, {iy:.2f})')
Konfigurasi plot
plt.xlim(-10, 10)
plt.ylim(-10, 10)
plt.axhline(0, color='grey', linestyle='--')
plt.axvline(0, color='grey', linestyle='--')
plt.legend()
plt.gca().set_aspect('equal', adjustable='box')
plt.title('Intersection of Two Circles')
plt.show()
javascript, vercion basada en godot con vector
var Vector2 = function(x, y) {
this.x = x || 0;
this.y = y || 0;
}
function puntoMedio(v1,v2){
return new Vector2(v1.x+v2.x/2,v1.y+v2.y/2)
}
function V2Rest(v1,v2){
return new Vector2(v1.x-v2.x,v1.y-v2.y);
}
function V2By(v1,v2){
return new Vector2(v1.x*v2.x,v1.y*v2.y);
}
function V2Plus(v1,v2){
return new Vector2(v1.x+v2.x,v1.y+v2.y);
}
function V2ByOne(v1,oneNumber){
return new Vector2(v1.x*oneNumber,v1.y*oneNumber);
}
function V2DivOne(v1,oneNumber){
oneNumber = parseFloat(oneNumber);
return new Vector2(v1.x/oneNumber,v1.y/oneNumber);
}
function V2PlusOne(v1,oneNumber){
return new Vector2(v1.x+oneNumber,v1.y+oneNumber);
}
function distancia2D(Vector_a,Vector_b){
if (Vector_a.x-Vector_b.x==0){
return Math.abs(Vector_a.y-Vector_b.y) ;
}
if (Vector_a.y-Vector_b.y==0){
return Math.abs(Vector_a.x-Vector_b.x) ;
}
return teoremaPitagoras_C(Math.abs(Vector_a.x-Vector_b.x),(Vector_a.y-Vector_b.y));
}
function teoremaPitagoras_C(a,b){
return Math.sqrt (Math.pow(a,2.00)+Math.pow(b,2.00));
}
function orthogonal(vector_2){
return new Vector2(vector_2.y,vector_2.x*-1);
}
function circle_intersect_cirle(Vector_a,r1,Vector_b,r2){
var d=distancia2D(Vector_a,Vector_b);
if (d==0){
return [new Vector2(0.00,0.00),new Vector2(0.00,0.00)];
}
var ab = V2Rest(Vector_b,Vector_a);
var r1n2=Math.pow((r1/d),2);
var r2n2=Math.pow((r2/d),2);
var rx=(r1n2-r2n2+1)/2.0;
var c=V2Plus(V2ByOne(ab,rx),Vector_a);
var h2=r1n2-Math.pow(rx,2);
if (h2<0){
return [new Vector2(0.00,0.00),new Vector2(0.00,0.00)];
}
var h=Math.sqrt(h2)*d;
var perp=V2ByOne(V2DivOne(orthogonal(ab),d),h);
return [new Vector2(V2Plus(perp,c)),new Vector2(V2Plus(V2ByOne(perp,-1),c))];
}
Swift: