Intersection of two circles

[SierraKen]

The other night I was thinking that all of this could be used in bouncing balls away from each other. Or collecting them from gravity, etc. I'll have to play around with this.

[bplus]

The other night I was thinking that all of this could be used in bouncing balls away from each other. Or collecting them from gravity, etc. I'll have to play around with this.

Ken I was going to say you shouldn't use POINT for ball collision detection but what the heck, play around see what you come up with ;)

[SierraKen]

Yeah true bplus, it would take up way too much processing to try to detect all points of a circle ALL the time. lol

[STxAxTIC]

Okay, so my notes were a little dense so I figure I owe you some code. This is the shortest, fastest, uses-no-arc-trig-functions method that I could come up with. Seems to work in all cases in all quadrants. Click left or right mouse to change the circle positions.

Code: QB64: [Select]

1. SCREEN 12
2.  
3. C1x = 0
4. C1y = 0
5. C2x = 100
6. C2y = 100
7. r1 = 100
8. r2 = 50
9.  
10. DO
11.     DO WHILE _MOUSEINPUT
12.         IF _MOUSEBUTTON(1) THEN
13.             C2x = _MOUSEX - 320
14.             C2y = 240 - _MOUSEY
15.         END IF
16.         IF _MOUSEBUTTON(2) THEN
17.             C1x = _MOUSEX - 320
18.             C1y = 240 - _MOUSEY
19.         END IF
20.     LOOP
21.  
22.     CLS
23.     CIRCLE (320 + C1x, C1y * -1 + 240), r1, 15
24.     CIRCLE (320 + C2x, C2y * -1 + 240), r2, 7
25.  
26.     Dx = C1x - C2x
27.     Dy = C1y - C2y
28.     D2 = Dx ^ 2 + Dy ^ 2
29.     IF (D2 ^ .5 < (r1 + r2)) THEN
30.         F = (-D2 + r2 ^ 2 - r1 ^ 2) / (2 * r1)
31.         a = Dx / F
32.         b = Dy / F
33.         g = a ^ 2 + b ^ 2
34.         IF (g > 1) THEN
35.             h = SQR(g - 1)
36.             int1x = C1x + r1 * (a + b * h) / g
37.             int1y = C1y + r1 * (b - a * h) / g
38.             int2x = C1x + r1 * (a - b * h) / g
39.             int2y = C1y + r1 * (b + a * h) / g
40.             CIRCLE (320 + int1x, int1y * -1 + 240), 3, 14
41.             CIRCLE (320 + int2x, int2y * -1 + 240), 3, 12
42.         END IF
43.     END IF
44.  
45.     _DISPLAY
46.     _LIMIT 30
47. LOOP

By the way bplus: Your solution calculates the cosine of an arc-cosine and could thus be made "simpler", but we're just splitting hairs now.

[STxAxTIC]

... And this version includes both functions: the bplus-qwerky one alongside the stxaxtic one.

These get the same job done, with some curious behind-the-scenes stuff going on. First thing I notice is the bplus-qwerky function requires no boundary testing, but this is *only* because QB64 quietly rescues you from error. Giving out-of-domain input to _ARCCOS will generally lead to complex results, but QB64 passes NAN as the output, and this quietly propagates through the rest of the code without crashing. *Grumbles*... Anyway, nice short function though.

The function I provide gets rid of all trig terms altogether (a style choice you'll often see me do), but this introduces the possibility of negative square roots, which sure don't fly. So my function is a few lines longer, plus for no particular reason I have it throw all zeros when there is no intersection.

Anyhow, here's everything side-by-side. Maybe for the sake of abundance we can have both functions, or a version of both, published to the toolbox.

Code: QB64: [Select]

1. SCREEN 12
2.  
3. C1x = 0
4. C1y = 0
5. C2x = 100
6. C2y = 100
7. r1 = 100
8. r2 = 50
9.  
10. DO
11.     DO WHILE _MOUSEINPUT
12.         IF _MOUSEBUTTON(1) THEN
13.             C2x = _MOUSEX - 320
14.             C2y = 240 - _MOUSEY
15.         END IF
16.         IF _MOUSEBUTTON(2) THEN
17.             C1x = _MOUSEX - 320
18.             C1y = 240 - _MOUSEY
19.         END IF
20.     LOOP
21.  
22.     CLS
23.     CIRCLE (320 + C1x, C1y * -1 + 240), r1, 15
24.     CIRCLE (320 + C2x, C2y * -1 + 240), r2, 7
25.  
26.     ''' Toggle between the two functions here.
27.     CALL IntersectTwoCircles(C1x, C1y, r1, C2x, C2y, r2, i1x, i1y, i2x, i2y)
28.     'CALL intersect2circs(C1x, C1y, r1, C2x, C2y, r2, i1x, i1y, i2x, i2y, p3x, p3y)
29.     '''
30.     LOCATE 1, 1: PRINT i1x, i1y, i2x, i2y
31.  
32.     IF (i1x OR i1y OR i2x OR i2y) THEN
33.         CIRCLE (320 + i1x, i1y * -1 + 240), 3, 14
34.         CIRCLE (320 + i2x, i2y * -1 + 240), 3, 12
35.     END IF
36.  
37.     _DISPLAY
38.     _LIMIT 30
39. LOOP
40.  
41. SUB IntersectTwoCircles (c1x, c1y, r1, c2x, c2y, r2, i1x, i1y, i2x, i2y)
42.     i1x = 0: i1y = 0: i2x = 0: i2y = 0
43.     Dx = c1x - c2x
44.     Dy = c1y - c2y
45.     D2 = Dx ^ 2 + Dy ^ 2
46.     IF (D2 ^ .5 < (r1 + r2)) THEN
47.         F = (-D2 + r2 ^ 2 - r1 ^ 2) / (2 * r1)
48.         a = Dx / F
49.         b = Dy / F
50.         g = a ^ 2 + b ^ 2
51.         IF (g > 1) THEN
52.             h = SQR(g - 1)
53.             i1x = c1x + r1 * (a + b * h) / g
54.             i1y = c1y + r1 * (b - a * h) / g
55.             i2x = c1x + r1 * (a - b * h) / g
56.             i2y = c1y + r1 * (b + a * h) / g
57.         END IF
58.     END IF
59. END SUB
60.  
61. SUB intersect2circs (ox1, oy1, r1, ox2, oy2, r2, ix1, iy1, ix2, iy2, p3x, p3y)
62.     d = ((ox1 - ox2) ^ 2 + (oy1 - oy2) ^ 2) ^ .5
63.     alpha = _ACOS((r1 ^ 2 + d ^ 2 - r2 ^ 2) / (2 * r1 * d))
64.     x1 = r1 * COS(alpha)
65.     l = r1 * SIN(alpha)
66.     angle = _ATAN2(oy2 - oy1, ox2 - ox1)
67.     p3x = ox1 + x1 * COS(angle)
68.     p3y = oy1 + x1 * SIN(angle)
69.     ix1 = p3x + l * COS(angle - _PI / 2)
70.     iy1 = p3y + l * SIN(angle - _PI / 2)
71.     ix2 = p3x + l * COS(angle + _PI / 2)
72.     iy2 = p3y + l * SIN(angle + _PI / 2)
73. END SUB
74.  

[bplus]

Hi STxAxTIC,

If you check back at reply #3 again you will notice my port of Paul Bourke, actually, I think I tried something else first or very similar from C or C# or C++ and had terrible time with +- confusions of h (the Qwerkey bplus adventure completely gets around that using +- pi/2, aint trig grand? Or as someone else recently said,

Ah, trigonometry!  How wonderful.

)

 In reply #3 you will notice:
#1 checks to see if an intersect actually exists before going about trying to find the points, this probably by passes problems with imaginary solutions.

#2 also does not once use that gawd-awlful trig-o-metric BS ;-))

My extension of Qwerkey's start was not intended as a completed solution but only as a proof of concept.

By the way bplus: Your solution calculates the cosine of an arc-cosine and could thus be made "simpler", but we're just splitting hairs now.

This?
x1 = r1 * COS(alpha)

Should be this:
x1 = r1 * (r1 ^ 2 + d ^ 2 - r2 ^ 2) / (2 * r1 * d)
x1 = (r1 ^ 2 + d ^ 2 - r2 ^ 2) / (2 * d)

Well OK it does work when substituted in... I think we still have to do SIN calc for l though.

What I don't like about your solution, Mr Static, is that you don't have coordinates for x, y intersects you have offsets that you have to translate back to coordinates of screen your using to use the results. I found that out trying to use your test code to check the Qwerkey bplus solution with same demo code, so your calling it intersect x, y (i1x, i1y) is misdirecting names of variables but maybe splitting hairs again about the way you setup your demos. :)

Update: OK, sorry, works fine in my demo code, so (i1x, i1y) are well named:

Code: QB64: [Select]

1. SCREEN 12 'intersect2circs test Qwerkey's and b+ derivation 2019-12-12
2.  
3. C1x = 150
4. C1y = 200
5. C2x = 300
6. C2y = 200
7. r1 = 130
8. r2 = 100
9.  
10. IntersectTwoCircles C1x, C1y, r1, C2x, C2y, r2, int1x, int1y, int2x, int2y
11. CIRCLE (C1x, C1y), r1, 15
12. CIRCLE (C2x, C2y), r2, 15
13. CIRCLE (int1x, int1y), 2, 14
14. CIRCLE (int2x, int2y), 2, 14
15. CIRCLE (p3x, p3y), 2, 14
16. LINE (int1x, int1y)-(int2x, int2y), 9
17.  
18. SUB IntersectTwoCircles (c1x, c1y, r1, c2x, c2y, r2, i1x, i1y, i2x, i2y)
19.     i1x = 0: i1y = 0: i2x = 0: i2y = 0
20.     Dx = c1x - c2x
21.     Dy = c1y - c2y
22.     D2 = Dx ^ 2 + Dy ^ 2
23.     IF (D2 ^ .5 < (r1 + r2)) THEN
24.         F = (-D2 + r2 ^ 2 - r1 ^ 2) / (2 * r1)
25.         a = Dx / F
26.         b = Dy / F
27.         g = a ^ 2 + b ^ 2
28.         IF (g > 1) THEN
29.             h = SQR(g - 1)
30.             i1x = c1x + r1 * (a + b * h) / g
31.             i1y = c1y + r1 * (b - a * h) / g
32.             i2x = c1x + r1 * (a - b * h) / g
33.             i2y = c1y + r1 * (b + a * h) / g
34.         END IF
35.     END IF
36. END SUB
37.  

[AndyA]

I came across the 'Intersection of Two Circles' algo by Paul Bourke in late 2010 to early 2011. Here's a link to the actual proof of the math used.
http://paulbourke.net/geometry/circlesphere/  scroll down to approximately 1/3 down the page.

I converted the C code by Tim Voght to Blitz Basic.
( C code here:  http://paulbourke.net/geometry/circlesphere/tvoght.c )


The Blitz Basic I posted can be found here : https://socoder.net/?Snippet=26103

Either listing looks a lot like the codes posted here.

[ edit ] Another interesting page on his site is: http://paulbourke.net/geometry/pointlineplane/ I used the
C code for Line segments intersect algo to use in Blitz Basic  [/ edit ]

[STxAxTIC]

Cool, thanks for the links. I like that Paul Bourke. A man after my own heart, or vice versa.

It's interesting that the various codes by various people (not excluding myself) even use some of the same letters for intermediate variables. I noticed this phenomenon back when we were writing filled circle/ellipse code. Sometimes a good answer is not just *an* answer, it is *the* answer.

[AndyA]

When all solutions converge to the same type of code, it is the *the* answer.

That the beauty of mathematics, it boils everything down to the essence of the task.

Paul Bourke's site is one I've been haunting for years. The guy is a prolific coder and writer, of many areas of mathematical interest.

Another fun site is the Geometry Junkyard  https://www.ics.uci.edu/~eppstein/junkyard/. Many links are broken, but still a neat place for ideas.

[bplus]

Nice link Andy, thanks!