(41) Intersection points between circles

11252020, 03:07 PM
(This post was last modified: 03202021 08:39 PM by Gene.)
Post: #1




(41) Intersection points between circles
Hi,
if somebody else already did a program to find the intersection points of two circles I could not find it. So here is mine: Program CIP Program to determine the intersection points of two circles. Circles are defined by coordinates of central point and radius. Output is coordinates of the intercept points of the two circles. If there is no solution message is given. If both solutions are the same there is only 1 solution. Use of registers: Circle 1: Coordinates of midpoint: x: 01, y: 02 Radius: 03 Circle 2: Coordinates of midpoint: x: 04, y: 05 Radius: 06 07: Distance between the two midpoints. 08: Angle between xaxis and line between midpoints 09: Angle at midpoint of first circle of the triangle formed by midpoints and first intersection of cycles 10: For computation Output: Coordinates of intersection points: Point 1: x: 11, y: 12; Point 2: x: 13, y: 14 Flags used: 01, 02 Example: Circle 1 has the central point x=13, y=4 and the radius 6.8 Circle 2 has the central point x=6, y=10 and the radius 4 Keystrokes: XEQ Alpha CIP Alpha > CIRCLE1? 13 ENTER 4 ENTER 6.8 R/S > CIRCLE2? 6 ENTER 10 ENTER 4 R/S > 9.9987 (xvalue of 1st intersection point) X<>Y 10.1018 (yvalue of 1st intersection point) – R/S  > 6.5109 (xvalue of 2nd intersection point) X<>Y 6.0328 (yvalue of 2nd intersection point) A revised version that is shorter and does not use Flag 02 is below. Thanks to Albert Chan who showed me ways to improve the program! Code: 01 LBL „CIP“ 

11252020, 06:16 PM
(This post was last modified: 11302020 09:58 PM by Albert Chan.)
Post: #2




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 = (p2p1):abs() lua> d  centertocenter distance 9.219544457292887 r1r2 ≤ 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 lua> h = area(r1,r2,d) * 2 / d  height of triangle lua> d1 = sqrt((r1+h)*(r1h))  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 = (p2p1) / d lua> p1 + v1*(d1+h*I) 6.51094321225877+6.032767080968563*I lua> p1 + v1*(d1h*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 = NaNNaN*I ⇒ 2 circles do not intersect. lua> v2 = (1/2 + (r1+r2)*(r1r2)/(2*d*d)) + 2*area(r1,r2,d) / (d*d) * I lua> p1 + (p2p1)*v2 6.510943212258768+6.032767080968563*I lua> p1 + (p2p1)*v2:conj() 9.99870384656476+10.101821154325554*I Intersection points might be closer to midpoint of p1, p2. We may use that as refercence. Code: function intersection(p1, r1, p2, r2) lua> intersection(p1, r1, p2, r2) 6.510943212258769+6.032767080968563*I 9.99870384656476+10.101821154325554*I 

11252020, 06:48 PM
Post: #3




RE: Intersection points between circles
Hi Albert,
thank you very much. As a statistician up to now I had not to handle complex numbers. So  frankly spoken  I have some difficulties to understand your solution. But more and more I have the feeling that I should dig in complex numbers. There seem to be a lot of things that can be solved more elegant and easier than by solving it only with real numbers. 

11262020, 12:22 AM
Post: #4




RE: Intersection points between circles
Another way is to solve for x, then get h (half chord length) XCAS> circle1 := x^2 + y^2  r1^2 = 0 XCAS> circle2 := (xd)^2 + y^2  r2^2 = 0 XCAS> chord := simplify(circle1  circle2); // equation for chord \((2d)x + (r_2^2  r_1^2  d^2)=0\\⇒ x = \large{d\over2} + {r_1^2  r_2^2 \over 2d}\) XCAS> p1, r1 := 13 + 4*i, 6.8 XCAS> p2, r2 := 6 + 10*i, 4.0 XCAS> d := abs(p1p2) → √85 ≈ 9.21954445729 XCAS> d1 := d/2 + (r1+r2)*(r1r2)/(2*d) → 6.24976648976 XCAS> h := sqrt((r1+d1)*(r1d1)) → 2.67963035203 Rotate/translate d1±h*i, back to intersection coordinates. XCAS> v1 := (p2p1)/d; → (7+6*i)/√85 = sign(p2p1) XCAS> p1 + v1*(d1+h*i) → 6.51094321226 + 6.03276708097*i XCAS> p1 + v1*(d1h*i) → 9.99870384656 + 10.1018211543*i 

11302020, 02:19 PM
Post: #5




RE: Intersection points between circles
We can also get x directly, from Law of Cosine. Let R_{2} = angle corresponded to side r_{2} (the blue side) \(r_2^2 = d^2 + r_1^2  2\;d\;r_1 \cos(R_2) = d^2 + r_1^2  2\;d\;x \\ ⇒ x = \large{d\over2} + {r_1^2  r_2^2 \over 2d}\) Let Δ = area of the triangle, vertices = (0,0), (x,h), (d,0) \(Δ = \large{d\;h\over2}\) \(⇒ h = \large{2Δ \over d}\) 

11302020, 05:19 PM
(This post was last modified: 12012020 04:28 PM by rawi.)
Post: #6




RE: Intersection points between circles
Hi Albert,
thank you very much for the interesting discussion. The solution that is used in my program indeed uses as well the Law of Cosine. The difference between your solution and mine is that I use directly the coordinates given. You first transfer it to an easier problem by setting one midpoint to (0;0) and the other to (d;0), but then you have it to transfer back. I am not yet sure which solution is easier. Unfortunately I do not know how to insert a image that is not on a website. So I try to describe it without a picture. Let (x1,y1) be the coordinates of the first midpoint (x2,y2) be the coordinates of the second midpoint r1 be the radius of the first circle r2 be the radius of the second circle First the distance between midpoints is computed (steps 1630): z=((x1x2)^2+(y1y2)^2)^0.5 Then we compute the angle between line between midpoints and paralell to xaxis (steps3138): alpha = arcsin((y2y1)/z) The triangle made by the midpoints and the first intersection have the sides z, r1 and r2. Therefore we can compute the angle between line between midpoints and line from midpoint of first circle to first intersection point by using the Law of Cosine (steps 3954): beta = arccos((z²+r1²r2²)/(2*z*r1)) Now we must take into account, whether x2<x1 or x2>=x1 and analogue with y1 and y2. We set sg1 = 1 if x2>=x1 and sg1 = 1 if x2<x1 and likewise sg2 = 1 fi y2 >= y1 and sg2 = 1 if y2 < y1. This is done by using flag 01 and flag 02. Then we can compute the coordinates of the two intersection points (sx1, sy1) (steps 5573) and (sx2, sy2) (steps 7595): sx1 = x1 + r1*(cos(alpha+beta))*sg1 sy1 = y1 + r1*(sin(alpha+beta))*sg2 sx2 = x1 + r1*(cos(alphabeta))*sg1 sy2 = y1 + r1*(sin(alphabeta))*sg2 This is the solution given. I hope this makes it a little more transparent. Best Raimund 

11302020, 08:51 PM
Post: #7




RE: Intersection points between circles  
11302020, 09:03 PM
Post: #8




RE: Intersection points between circles
(11302020 05:19 PM)rawi Wrote: Then we compute the angle between line between midpoints and paralell to xaxis (steps3138): What we wanted is the angle between vector ((x1,y1) to (x2,y2)), and the xaxis. We should have: pi ≤ alpha ≤ +pi Using arcsin, we have pi/2 ≤ alpha ≤ pi/2. sg1/sg2 correction will not fix this. Correction should be: alpha = arcsin((y2y1)/z); if x2 < x1 then alpha = pi  alpha end Or, alpha = arccos((x2x1)/z); if y2 < y1 then alpha = alpha end Code: function intersection(p1, r1, p2, r2) lua> I = require'complex'.I lua> p1, r1 = 13+4*I, 6.8 lua> p2, r2 = 6+10*I, 4.0 lua> lua> intersection(p1,r1, p2,r2) 6.510943212258769+6.032767080968563*I 9.998703846564759+10.101821154325552*I lua> intersection(p2,r2, p1,r1) 9.99870384656476+10.101821154325554*I 6.51094321225877+6.032767080968563*I Quote:The difference between your solution and mine is that I use directly the coordinates given. You first transfer it to an easier problem by setting one midpoint to (0;0) and the other to (d;0), but then you have it to transfer back. I am not yet sure which solution is easier. Your code do the polar form side, mine the rectangular side. Both ways are equivalent. circles intersections = p1 + r1 * exp((a±b)*I) = p1 + exp(a*I) * (r1*exp(±b*I)) exp(a*I) = (p2p1) / d r1*exp(±b*I) = d1 ± h*I 

12012020, 12:17 AM
(This post was last modified: 12012020 12:23 AM by Albert Chan.)
Post: #9




RE: Intersection points between circles
(11302020 05:19 PM)rawi Wrote: alpha = arcsin((y2y1)/z) If x2 ≥ x1, we have the correct angle. No correction is needed. If x2 < x1, calculated alpha should really be pi  alpha cos((pi  alpha) ± beta) = cos(pi  (alpha ∓ beta)) = cos(alpha ∓ beta) * 1 sin((pi  alpha) ± beta) = sin(pi  (alpha ∓ beta)) = sin(alpha ∓ beta) → sy does not require correction. Code: function intersection(p1,r1, p2, r2) lua> I = require'complex'.I lua> p1, r1 = 13+4*I, 6.8 lua> p2, r2 = 6+10*I, 4.0 lua> lua> intersection(p1,r1,p2,r2) 9.99870384656476+10.101821154325554*I 6.510943212258768+6.032767080968563*I lua> intersection(p2,r2,p1,r1) 9.99870384656476+10.101821154325554*I 6.51094321225877+6.032767080968563*I 

12012020, 09:25 AM
Post: #10




RE: Intersection points between circles
Hi Albert,
You wrote: Quote:We should have: pi ≤ alpha ≤ +pi I forgot to mention that I take the absolute figure for computing alpha. I compute alpha = abs(arcsin((y2y1)/z)) (see line 37 of program listing). So I limit it to the interval from 0 to pi/2. You wrote: Quote:sy does not require correction. The results tell me that the correction is needed. Take the following example: x1 = 1, y1= 3, r1 = 4; x2 = 6, y2 = 2, r2 = 5 If computed it with correction I get: sx1 = 1,3106; sy1=0.2651; sx2= 2,8380; sy2 = 1.8732 which is correct If I keep the circles, but use the former circle 2 as circle 1 and vice versa I get: sx1 = 2,8380; sy1= 1.8732; sx2 = 1.3106; sy2 = 0.2651 So the numbers of the intersection points are exchanged, but they still are correct. If I compute without correction of sy (I delete lines 83, 84, 61, 62 of the program) I get: For x1=1, y1=3, r1 = 4, x2 = 6, y2 = 2, r2 = 5 the same results as before. But if I change the number of circles, i.e. x1=6, y1=2, r1=5, x2=1, y2=3, r2=4 I get x1 = 2.8380, y1=5.8380, x2=1,3106, y2=3,7349 which is not correct for the ycoordinates. Perhaps by limiting alpha from 0 to pi/2 and doing the correction both for sx and sy I get correct results? I tested the program with numerous examples and it always delivered correct results. Best Raimund 

12012020, 11:59 AM
Post: #11




RE: Intersection points between circles
(12012020 09:25 AM)rawi Wrote: I forgot to mention that I take the absolute figure for computing alpha. I compute Try it again, but remove the ABS applied to alpha. It is this extra ABS that made the program complicated, requiring sg2 correction to undo. Quote:Perhaps by limiting alpha from 0 to pi/2 and doing the correction both for sx and sy I get correct results? Yes, it does. Here is the proof that sg2 correction undo ABS. If y2y1 ≥ 0, ABS does nothing to alpha, and we had already shown it work in previous post. If y2y1 < 0, we have 2 possibilities: x2x1 ≥ 0: calculated alpha should really be alpha: cos(alpha ± beta) = cos(alpha pi ∓ beta) * 1 sin(alpha ± beta) = sin(alpha pi ∓ beta) * 1 x2x1 < 0: calculated alpha should really be (pi  alpha): cos((pi  alpha) ± beta) = cos(pi  (alpha ± beta)) = cos(alpha ± beta) * 1 sin((pi  alpha) ± beta) = sin(pi  (alpha ± beta)) = sin(alpha ± beta) * 1 

12012020, 02:04 PM
(This post was last modified: 12012020 04:29 PM by rawi.)
Post: #12




RE: Intersection points between circles
Hi Albert,
I tried it and you are totally right. Thanks for pointing that out to me. Here is the improved method description: Let (x1, y1) be the coordinates of midpoint of circle 1 and (x2, y2) be the coordinates of midpoint of circle 2 and r1 resp. r2 be the radii. Let z be the distance between the midpoints: z=((x1x2)²+(y1y2)²)^0.5 The angle alpha between the line between the midpoints and the parallel to the xaxis through (x1, y1) using the sinusfunction is: alpha = arcsin((y2y1)/z) Beta can be computed by using the Law of Cosine: beta = arccos((z²+r1²r2²)/(2*z*r1)) We must take into account, whether x2<x1 or x2>=x1. We set sg = 1 if x2>=x1 and sg1 = 1 if x2<x1 Then the coordinates of the two intersection points are: sx1 = x1 + r1*(cos(alpha+beta))*sg sy1 = y1 + r1*(sin(alpha+beta)) sx2 = x1 + r1*(cos(alphabeta))*sg sy2 = y1 + r1*(sin(alphabeta)) And here is the improved code, which is shorter and easier than the previous one: Code: 01 LBL „CIP“ 

12102020, 01:34 PM
Post: #13




RE: Intersection points between circles
(12012020 02:04 PM)rawi Wrote: sx1 = x1 + r1*(cos(alpha+beta))*sg To reduce errors, it may be better if we pick circle1 with the smaller radius, r1 ≤ r2. With circle1 having smaller radius, beta could be huge. (up to pi) We could use complement of beta instead: gamma = arcsin((z²+r1²r2²)/(2*z*r1)) = pi/2  beta With gamma, the coordinates are: sx1 = x1 + r1 * sin(gammaalpha) * sg sy1 = y1 + r1 * cos(gammaalpha) sx2 = x1 + r1 * sin(gamma+alpha) * sg sy2 = y1 − r1 * cos(gamma+alpha) Prove: If x ≥ 0, sg = 1 cos(alpha ± beta) = cos(beta ± alpha) = sin(gamma ∓ alpha) * 1 sin(alpha ± beta) = ±sin(beta ± alpha) = ±cos(gamma ∓ alpha) If x <0, sg = 1, alpha should really be pi  alpha cos(pialpha ∓ beta) = cos(alpha ± beta) * 1 sin(pialpha ∓ beta) = sin(alpha ± beta) 

« Next Oldest  Next Newest »

User(s) browsing this thread: