(41) Intersection points between circles
11-25-2020, 06:16 PM (This post was last modified: 11-30-2020 09:58 PM by Albert Chan.)
Post: #2
 Albert Chan Senior Member Posts: 2,230 Joined: Jul 2018
RE: Intersection points between circles
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
 « Next Oldest | Next Newest »

 Messages In This Thread (41) Intersection points between circles - rawi - 11-25-2020, 03:07 PM RE: Intersection points between circles - Albert Chan - 11-25-2020 06:16 PM RE: Intersection points between circles - rawi - 11-25-2020, 06:48 PM RE: Intersection points between circles - Albert Chan - 11-26-2020, 12:22 AM RE: Intersection points between circles - Albert Chan - 11-30-2020, 02:19 PM RE: Intersection points between circles - rawi - 11-30-2020, 05:19 PM RE: Intersection points between circles - Albert Chan - 11-30-2020, 09:03 PM RE: Intersection points between circles - Albert Chan - 12-01-2020, 12:17 AM RE: Intersection points between circles - SlideRule - 11-30-2020, 08:51 PM RE: Intersection points between circles - rawi - 12-01-2020, 09:25 AM RE: Intersection points between circles - Albert Chan - 12-01-2020, 11:59 AM RE: Intersection points between circles - rawi - 12-01-2020, 02:04 PM RE: Intersection points between circles - Albert Chan - 12-10-2020, 01:34 PM