(41) Intersection points between circles

[Albert Chan]

Hi, rawi

We can get the 2 circles intersection points, without trig. functions.

lua> I = require'complex'.I
lua> p1, r1 = 13+4*I, 6.8
lua> p2, r2 = 6+10*I, 4.0
lua> d = (p2-p1):abs()
lua> d -- center-to-center distance
9.219544457292887

|r1-r2| ≤ d ≤ |r1+r2|, thus 2 circles do intersect somewhere.

My code, from Area of Triangle post

Code:

function area(a,b,c)                -- area of triangle: side a,b,c
    if a > b then a, b = b, a end
    if a > c then a, c = c, a end   -- a = shortest side, b-c guaranteed exact
    b, c = b-c, b*c
    b = (a+b)*(a-b)/4
    return sqrt(b*(c-b)), b/c       -- area, sin(A/2)^2
end

lua> h = area(r1,r2,d) * 2 / d -- height of triangle
lua> d1 = sqrt((r1+h)*(r1-h)) -- base of triangle
lua> d1, h
6.249766489755484      2.6796303520316775

If p1=(0,0), p2=(d,0), then intersected points at (d1, ±h)
Note: we setup with r1 ≥ r2, to force d1 ≥ d/2 > 0, see post #4

-- Complex multiply and addition for rotatation and translation, to get intersection points:

lua> v1 = (p2-p1) / d
lua> p1 + v1*(d1+h*I)
6.51094321225877+6.032767080968563*I
lua> p1 + v1*(d1-h*I)
9.99870384656476+10.101821154325554*I

---

Update: we can remove r1 ≥ r2 requirement, by combine this post and post #4
It might also be faster, since real part of v2 does not use square root.

Note: Lua math.sqrt(x) return -NaN if x < 0, is exactly what we wanted.
With "bad" triangle, area = -NaN ⇒ v2 = -NaN-NaN*I ⇒ 2 circles do not intersect.

lua> v2 = (1/2 + (r1+r2)*(r1-r2)/(2*d*d)) + 2*area(r1,r2,d) / (d*d) * I
lua> p1 + (p2-p1)*v2
6.510943212258768+6.032767080968563*I
lua> p1 + (p2-p1)*v2:conj()
9.99870384656476+10.101821154325554*I

Intersection points might be closer to mid-point of p1, p2. We may use that as refercence.

Code:

function intersection(p1, r1, p2, r2)
    local d = (p2-p1):abs()
    local v2 = ((r1+r2)*(r1-r2) + 4*area(r1,r2,d)*I) / (d*d)
    p1, p2 = (p1+p2)/2, (p2-p1)/2   -- mid-point as reference    
    return p1 + p2*v2, p1 + p2*v2:conj()
end

lua> intersection(p1, r1, p2, r2)
6.510943212258769+6.032767080968563*I      9.99870384656476+10.101821154325554*I