QB64.org Forum

Active Forums => Programs => Topic started by: STxAxTIC on December 11, 2019, 06:30:49 am

Title: Intersection of two circles
Post by: STxAxTIC on December 11, 2019, 06:30:49 am

From our lovely Discord chat:

Quote

Zeppelin
I know this comes under complex math, but does anyone know how to calculate the 2 points at which 2 circles intersect

I’m trying to calculate the intersecting points not distance. SMc sent a helpful link, but StxAxTic it would be great if you could explain it further

The link from Mathworld is http://mathworld.wolfram.com/Circle-CircleIntersection.html (http://mathworld.wolfram.com/Circle-CircleIntersection.html), but this derivation is severely lacking because it doesn't handle circles in arbitrary positions. Then I realized my old solution had the same problem, so I derived the general case in the last two hours. The notes are three pages long and are a giant ball of vectors / trig. I'll spare the details now, and get down to the distilled result: sample code (a little streamlining and this will go in the toolbox):

Code: QB64: [Select]

1. SCREEN 12
2.  
3. C1x = -10
4. C1y = -5
5. C2x = 20
6. C2y = 30
7. r1 = 40
8. r2 = 50
9.  
10. Dx = C1x - C2x
11. Dy = C1y - C2y
12.  
13. E = (Dx ^ 2 + Dy ^ 2 + r2 ^ 2 - r1 ^ 2) / (2 * r2)
14. F = (-Dx ^ 2 - Dy ^ 2 + r2 ^ 2 - r1 ^ 2) / (2 * r1)
15.  
16. a = Dx / E
17. b = Dy / E
18. c = Dx / F
19. d = Dy / F
20.  
21. cosbetap = (a + b * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
22. sinbetap = (b + a * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
23. cosbetam = (a - b * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
24. sinbetam = (b - a * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
25.  
26. cosalphap = (c + d * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
27. sinalphap = (d + c * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
28. cosalpham = (c - d * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
29. sinalpham = (d - c * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
30.  
31. int1x = C1x + r1 * cosalphap
32. int1y = C1y + r1 * sinalpham
33.  
34. int2x = C2x + r2 * cosbetap
35. int2y = C2y + r2 * sinbetam
36.  
37. CIRCLE (320 + C1x, C1y * -1 + 240), r1, 15
38. CIRCLE (320 + C2x, C2y * -1 + 240), r2, 15
39. CIRCLE (320 + int1x, int1y * -1 + 240), 3, 14
40. CIRCLE (320 + int2x, int2y * -1 + 240), 3, 14
41.  

... Whoever can derive the equations in there gets a prize from the Librarian.

Title: Re: Intersection of two circles
Post by: Qwerkey on December 11, 2019, 06:50:13 am

Oh, that's an interesting problem.  I may have a go at it.  They share a common sector and that will be my approach.  On first inspection, it looks as if things are slight different if one of the circle's centre lies entirely inside the other circle as opposed to the two centres being outside the other.

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 11, 2019, 08:19:24 am

Hi Qwerk,

I calculated more terms than the demo needs, presumably to cover cases not tested. There are plus and minus solutions to the same equation so you have to choose which ones to toss.

Title: Re: Intersection of two circles
Post by: bplus on December 11, 2019, 11:52:39 am

Looks familiar: https://www.qb64.org/forum/index.php?topic=1485.0

The above link is full blown demo of this:

Code: QB64: [Select]

1.  
2. SUB intersect2Circles (x1, y1, r1, x2, y2, r2, ix1, iy1, ix2, iy2)
3.     'x1, y1 origin of circle 1 with radius r1
4.     'x2, y2 origin of circle 2 with radius r2
5.     'ix1, iy1 is the first point of intersect
6.     'ix2, iy2 is the 2nd point of intersect
7.     'if ix1 = ix2 = iy1 = iy2 = 0 then no points returned
8.  
9.     DIM d, a, h, Px, pY
10.     d = distance(x1, y1, x2, y2) 'distance between two origins
11.     IF r1 + r2 < d THEN
12.         'PRINT "The circles are too far apart to intersect.": END
13.         'some signal ???    if ix1 = ix2 = iy1 = iy2 = 0 then no points returned
14.         ix1 = 0: ix2 = 0: iy1 = 0: iy2 = 0
15.         EXIT SUB
16.     END IF
17.     IF (d < r1 AND r2 + d < r1) OR (d < r2 AND r1 + d < r2) THEN 'one circle is inside the other = no intersect
18.         ix1 = 0: ix2 = 0: iy1 = 0: iy2 = 0
19.         EXIT SUB
20.         'IF ABS(r1 - r2) > 3 THEN
21.         '    PRINT "No intersect, same center (or nearly so) and different radii (or seemingly so).": END
22.         'ELSE
23.         '    PRINT "Infinite intersect, the circles are the same (or nearly so).": END
24.         'END IF
25.  
26.     END IF
27.     'results
28.     a = (r1 ^ 2 - r2 ^ 2 + d ^ 2) / (2 * d)
29.     Px = x1 + a * (x2 - x1) / d
30.     pY = y1 + a * (y2 - y1) / d
31.     h = (r1 ^ 2 - a ^ 2) ^ .5
32.     ix1 = INT(Px - h * (y2 - y1) / d)
33.     iy1 = INT(pY + h * (x2 - x1) / d)
34.     'circle x1,y1,2,1 filled
35.     'PRINT: PRINT "Intersect pt1: "; x1; ", "; y1
36.     ix2 = INT(Px + h * (y2 - y1) / d)
37.     iy2 = INT(pY - h * (x2 - x1) / d)
38.     'circle x2,y2,2,1 filled
39.     'PRINT: PRINT "Intersect pt2: "; x2; ", "; y2
40.     'line x1,y1,x2,y2
41. END SUB
42.  

Title: Re: Intersection of two circles
Post by: Pete on December 11, 2019, 11:57:30 am

That's a great program Bill, if I ever need to make nipples on a tipped over headless snowman. My mother used to tell me. "No! The carrot doesn't go there, but I digress.

Well, my hat's off to you again... and damn, there goes my Donald Trump comb-over, but still, very impressive. Can you tell me when I change the radius, to something like r1 = 140 and r2 = 150, it only gives me one point of intersection?

Pete

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 11, 2019, 12:35:16 pm

Thanks for the hat tilt Pete, long time no see (kinda)!

Say, nice eye bplus. I never noticed your post. I guess you have a leg up in getting the librarians prize, all you need to do is provide the derivation of your code instead of mine. Tee hehe

Title: Re: Intersection of two circles
Post by: SierraKen on December 11, 2019, 01:20:17 pm

Static, I don't know your challenge answer because I'm not that great in math. But I did spruce up your program and let the user plug in coordinates first and 2 radius numbers for 2 circles. Then it makes a graph and shows the circles and tells you the coordinate numbers where they intersect. It mostly works, except I did find a problem with this. Whenever they intersect at a 0 coordinate, for some reason it only states the first x and y intersection and not the second one. I have no idea why this happens, can any of you give me help on this? But like I said, it mostly works. To easily find where my problem is, plug in these numbers: X1 = 50, Y1 = 50, Radius = 50, X2 = 75, Y2 = 75, Radius = 75. Or you can just use any 3 numbers the same for the first circle and 3 numbers the same for the second circle that will still intersect. Like I said, it's an interactive program so no need to change the code to plot the points, unless you know how to fix the problem, thanks. Static, this still an incredible program.

Here is what I did with it:

Code: QB64: [Select]

1. _TITLE "Circles Intersections Finder - by STxAxTIC and Ken G."
2. SCREEN 12
3. Go:
4. CLS
5. INPUT "X1 = ", C1x
6. INPUT "Y1 = ", C1y
7. INPUT "Radius = ", r1
8. INPUT "X2 = ", c2X
9. INPUT "Y2 = ", c2Y
10. INPUT "Radius = ", r2
11. CLS
12. FOR yy = 0 TO 600 STEP 10
13.     LINE (320, yy)-(320, yy + 5), _RGB32(255, 255, 255)
14. NEXT yy
15. FOR xx = 0 TO 800 STEP 10
16.     LINE (xx, 240)-(xx + 5, 240), _RGB32(255, 255, 255)
17. NEXT xx
18.  
19. 'C1x = 0
20. 'C1y = -10
21. 'c2X = 10
22. 'c2Y = 30
23. 'r1 = 40
24. 'r2 = 50
25.  
26. Dx = C1x - c2X
27. Dy = C1y - c2Y
28.  
29. E = (Dx ^ 2 + Dy ^ 2 + r2 ^ 2 - r1 ^ 2) / (2 * r2)
30. F = (-Dx ^ 2 - Dy ^ 2 + r2 ^ 2 - r1 ^ 2) / (2 * r1)
31.  
32. a = Dx / E
33. b = Dy / E
34. c = Dx / F
35. d = Dy / F
36. ON ERROR GOTO nointersection:
37. cosbetap = (a + b * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
38. sinbetap = (b + a * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
39. cosbetam = (a - b * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
40. sinbetam = (b - a * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
41.  
42. cosalphap = (c + d * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
43. sinalphap = (d + c * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
44. cosalpham = (c - d * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
45. sinalpham = (d - c * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
46.  
47. int1x = C1x + r1 * cosalphap
48. int1y = C1y + r1 * sinalpham
49.  
50. int2x = c2X + r2 * cosbetap
51. int2y = c2Y + r2 * sinbetam
52.  
53. CIRCLE (320 + C1x, C1y * -1 + 240), r1, 15
54. CIRCLE (320 + c2X, c2Y * -1 + 240), r2, 15
55. CIRCLE (320 + int1x, int1y * -1 + 240), 3, 14
56. CIRCLE (320 + int2x, int2y * -1 + 240), 3, 14
57. LOCATE 1, 1
58. PRINT "Intersects at: ";
59. PRINT "("; int1x; ","; int1y; ") and ("; int2x; ","; int2y; ")"
60. PRINT
61. PRINT "Again (Y/N):";
62. again:
63. ag$ = INKEY$
64. IF ag$ = "y" OR ag$ = "Y" THEN GOTO Go:
65. IF ag$ = "n" OR ag$ = "N" THEN END
66. GOTO again:
67. nointersection:
68. CIRCLE (320 + C1x, C1y * -1 + 240), r1, 15
69. CIRCLE (320 + c2X, c2Y * -1 + 240), r2, 15
70. LOCATE 1, 1
71. INPUT "No intersection, press Enter to try again.", ag2$
72. GOTO Go:
73.  

 

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 11, 2019, 02:07:09 pm

Thanks for having a look Ken.

You guys are definitely finding the edge cases and causes for modest IF statements to be edited in. This was expected, namely cause trig functions do funny things at quarter-pi intervals, and there are multi rooted quadratic solutions in there. Next time I'm at my desk I will finish this up. Thanks again all.

Title: Re: Intersection of two circles
Post by: Zeppelin on December 11, 2019, 04:24:45 pm

Hey everyone,

Heres a WIP voronoi function.

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2. RANDOMIZE TIMER
3.  
4. cirs = 25
5.  
6. DIM cirX(cirs)
7. DIM cirY(cirs)
8.  
9. rad = 25
10. FOR n = 1 TO cirs
11.     cirX(n) = INT(RND * _WIDTH - 1) + 1
12.     cirY(n) = INT(RND * _HEIGHT - 1) + 1
13.     CIRCLE (cirX(n), cirY(n)), 2
14.     PAINT (cirX(n), cirY(n)), _RGB(255, 255, 255)
15.     CIRCLE (cirX(n), cirY(n)), rad
16. NEXT n
17.  
18. DO
19.     CLS
20.  
21.     FOR x = 1 TO cirs
22.         FOR n = 1 TO cirs
23.             dist = SQR(((cirX(x) - (cirX(n))) ^ 2) + ((cirY(x) - cirY(n)) ^ 2))
24.             IF dist <= rad * 2 THEN
25.                 Dx = cirX(n) - cirX(x)
26.                 Dy = cirY(n) - cirY(x)
27.  
28.                 E = (Dx ^ 2 + Dy ^ 2 + r2 ^ 2 - r1 ^ 2) / (2 * rad)
29.                 F = (-Dx ^ 2 - Dy ^ 2 + r2 ^ 2 - r1 ^ 2) / (2 * rad)
30.  
31.                 a = Dx / E
32.                 b = Dy / E
33.                 c = Dx / F
34.                 d = Dy / F
35.  
36.                 cosbetap = (a + b * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
37.                 sinbetap = (b + a * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
38.                 cosbetam = (a - b * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
39.                 sinbetam = (b - a * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
40.  
41.                 cosalphap = (c + d * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
42.                 sinalphap = (d + c * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
43.                 cosalpham = (c - d * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
44.                 sinalpham = (d - c * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
45.  
46.                 ipX = cirX(n) + rad * cosalphap
47.                 ipY = cirY(n) + rad * sinalpham
48.  
49.                 ipX2 = cirX(x) + rad * cosbetap
50.                 ipY2 = cirY(x) + rad * sinbetam
51.  
52.  
53.                 LINE (ipX, ipY)-(ipX2, ipY2), _RGB(0, 0, 255)
54.             END IF
55.  
56.         NEXT n
57.     NEXT x
58.  
59.     rad = rad + 1
60.     _DELAY (0.1)
61.  
62. LOOP UNTIL rad = 500
63.  
64. PRINT "DONE"
65. DO
66. LOOP UNTIL INKEY$ <> ""
67.  

Zep

Title: Re: Intersection of two circles
Post by: SMcNeill on December 11, 2019, 04:36:34 pm

Here's a version to play around with which doesn't use any math at all:

Code: QB64: [Select]

1. DIM RedX AS INTEGER, RedY AS INTEGER, RedSize AS INTEGER
2. DIM GreenX AS INTEGER, GreenY AS INTEGER, GreenSize AS INTEGER
3. REDIM SHARED OverlapX(10), OverlapY(10)
4. RedX = 200: RedY = 300: RedSize = 100
5. GreenX = 500: GreenY = 300: GreenSize = 100
6.  
7.  
8. SCREEN _NEWIMAGE(800, 600, 32)
9.  
10. DO
11.     _LIMIT 30
12.     CLS , 0
13.     DrawRed RedX, RedY, RedSize
14.     DrawGreen GreenX, GreenY, GreenSize
15.  
16.     MW = 0
17.     WHILE _MOUSEINPUT: MW = MW + _MOUSEWHEEL: WEND
18.     Mx = _MOUSEX: My = _MOUSEY: MB1 = _MOUSEBUTTON(1): MB2 = _MOUSEBUTTON(2)
19.     IF MB2 AND NOT OM THEN toggle = NOT toggle
20.     IF toggle THEN
21.         C$ = "Red"
22.         IF MB1 THEN RedX = Mx: RedY = My
23.         RedSize = RedSize + MW
24.     ELSE
25.         C$ = "Green"
26.         IF MB1 THEN GreenX = Mx: GreenY = My
27.         GreenSize = GreenSize + MW
28.     END IF
29.  
30.     LOCATE 1, 1: PRINT "Moving Circle: "; C$
31.     LOCATE 2, 1: PRINT "Overlap: ";
32.     CalculateOverlap
33.     FOR i = 1 TO UBOUND(OverlapX)
34.         PRINT "("; OverlapX(i); ","; OverlapY(i); ")";
35.     NEXT
36.     _DISPLAY
37.     OM = MB2
38. LOOP
39.  
40.  
41.  
42.  
43.  
44.  
45. $CHECKING:OFF
46. SUB CalculateOverlap
47.     REDIM OverlapX(10), OverlapY(10)
48.     DIM m AS _MEM: m = _MEMIMAGE(0)
49.     FOR x = 0 TO _WIDTH - 1
50.         FOR y = 0 TO _HEIGHT - 1
51.             IF _MEMGET(m, m.OFFSET + ((y * _WIDTH) + x) * 4, _UNSIGNED LONG) = &HFFFFFF00 THEN
52.                 _TITLE "Overlap!"
53.                 count = count + 1
54.                 OverlapX(count) = x
55.                 OverlapY(count) = y
56.                 IF count > 9 THEN EXIT FOR
57.             END IF
58.         NEXT
59.         IF count > 9 THEN EXIT FOR
60.     NEXT
61.     REDIM _PRESERVE OverlapX(count), OverlapY(count)
62. END SUB
63.  
64.  
65.  
66. SUB DrawRed (x, y, size)
67.     DIM Red AS LONG, m AS _MEM, m1 AS _MEM, o AS _OFFSET
68.     Red = _NEWIMAGE(_WIDTH, _HEIGHT, 32): m = _MEMIMAGE(Red)
69.  
70.     D = _DEST: _DEST Red
71.     CLS , 0
72.     CIRCLE (x, y), size, &HFFFF0000
73.     m1 = _MEMIMAGE(D)
74.     o = 2 'blue, green, red, alpha, so 0, 1, 2, 3.... 2 is the starting offset
75.     DO UNTIL o > m.SIZE
76.         IF _MEMGET(m, m.OFFSET + o, _UNSIGNED _BYTE) = 255 THEN
77.             _MEMPUT m1, m1.OFFSET + o + 1, 255 AS _UNSIGNED _BYTE 'dont forget to put the alpha
78.             _MEMPUT m1, m1.OFFSET + o, 255 AS _UNSIGNED _BYTE
79.         END IF
80.         o = o + 4
81.     LOOP
82.  
83.     _DEST D
84.     _MEMFREE m
85.     _MEMFREE m1
86.     _FREEIMAGE Red
87. END SUB
88.  
89. SUB DrawGreen (x, y, size)
90.     DIM Green AS LONG, m AS _MEM, m1 AS _MEM, o AS _OFFSET
91.     Green = _NEWIMAGE(_WIDTH, _HEIGHT, 32): m = _MEMIMAGE(Green)
92.  
93.     D = _DEST: _DEST Green
94.     CLS , 0
95.     CIRCLE (x, y), size, &HFF00FF00
96.     m1 = _MEMIMAGE(D)
97.     o = 1 'blue, green, red, alpha, so 0, 1, 2, 3.... 1 is the starting offset
98.     DO UNTIL o > m.SIZE
99.         IF _MEMGET(m, m.OFFSET + o, _UNSIGNED _BYTE) = 255 THEN
100.             _MEMPUT m1, m1.OFFSET + o + 2, 255 AS _UNSIGNED _BYTE 'dont forget to put the alpha
101.             _MEMPUT m1, m1.OFFSET + o, 255 AS _UNSIGNED _BYTE
102.         END IF
103.         o = o + 4
104.     LOOP
105.  
106.     _DEST D
107.     _MEMFREE m
108.     _MEMFREE m1
109.     _FREEIMAGE Green
110. END SUB
111. $CHECKING:ON

Right mouse toggles between the red and green circle.
Hold the left button down to move a circle.
Use the mouse scroll to change circle size. 

Title: Re: Intersection of two circles
Post by: bplus on December 11, 2019, 05:29:36 pm

Quote from: Zeppelin on December 11, 2019, 04:24:45 pm

Hey everyone,

Heres a WIP voronoi function.

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2. RANDOMIZE TIMER
3.  
4. cirs = 25
5.  
6. DIM cirX(cirs)
7. DIM cirY(cirs)
8.  
9. rad = 25
10. FOR n = 1 TO cirs
11.     cirX(n) = INT(RND * _WIDTH - 1) + 1
12.     cirY(n) = INT(RND * _HEIGHT - 1) + 1
13.     CIRCLE (cirX(n), cirY(n)), 2
14.     PAINT (cirX(n), cirY(n)), _RGB(255, 255, 255)
15.     CIRCLE (cirX(n), cirY(n)), rad
16. NEXT n
17.  
18. DO
19.     CLS
20.  
21.     FOR x = 1 TO cirs
22.         FOR n = 1 TO cirs
23.             dist = SQR(((cirX(x) - (cirX(n))) ^ 2) + ((cirY(x) - cirY(n)) ^ 2))
24.             IF dist <= rad * 2 THEN
25.                 Dx = cirX(n) - cirX(x)
26.                 Dy = cirY(n) - cirY(x)
27.  
28.                 E = (Dx ^ 2 + Dy ^ 2 + r2 ^ 2 - r1 ^ 2) / (2 * rad)
29.                 F = (-Dx ^ 2 - Dy ^ 2 + r2 ^ 2 - r1 ^ 2) / (2 * rad)
30.  
31.                 a = Dx / E
32.                 b = Dy / E
33.                 c = Dx / F
34.                 d = Dy / F
35.  
36.                 cosbetap = (a + b * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
37.                 sinbetap = (b + a * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
38.                 cosbetam = (a - b * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
39.                 sinbetam = (b - a * SQR(a ^ 2 + b ^ 2 - 1)) / (a ^ 2 + b ^ 2)
40.  
41.                 cosalphap = (c + d * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
42.                 sinalphap = (d + c * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
43.                 cosalpham = (c - d * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
44.                 sinalpham = (d - c * SQR(c ^ 2 + d ^ 2 - 1)) / (c ^ 2 + d ^ 2)
45.  
46.                 ipX = cirX(n) + rad * cosalphap
47.                 ipY = cirY(n) + rad * sinalpham
48.  
49.                 ipX2 = cirX(x) + rad * cosbetap
50.                 ipY2 = cirY(x) + rad * sinbetam
51.  
52.  
53.                 LINE (ipX, ipY)-(ipX2, ipY2), _RGB(0, 0, 255)
54.             END IF
55.  
56.         NEXT n
57.     NEXT x
58.  
59.     rad = rad + 1
60.     _DELAY (0.1)
61.  
62. LOOP UNTIL rad = 500
63.  
64. PRINT "DONE"
65. DO
66. LOOP UNTIL INKEY$ <> ""
67.  

Zep

Ho Zep,
 
What's Voronoi have to do with circle Intersects?

Here is quick Voronoi Demo:

Code: QB64: [Select]

1. _TITLE "Voronoi Demo" 'b+ 2019-12-11
2. CONST xymax = 700, nPoints = 25
3. TYPE pType
4.     x AS SINGLE
5.     y AS SINGLE
6.     c AS _UNSIGNED LONG
7. END TYPE
8. SCREEN _NEWIMAGE(xymax, xymax, 32)
9. _SCREENMOVE 300, 20
10. RANDOMIZE TIMER
11. DIM pts(1 TO nPoints) AS pType
12. FOR i = 1 TO nPoints
13.     pts(i).x = xymax * RND
14.     pts(i).y = xymax * RND
15.     pts(i).c = _RGB32(155 * RND + 100, -(RND < .5) * 255 * RND, -(RND < .5) * 255 * RND)
16. NEXT
17. FOR i = 1 TO nPoints
18.     CIRCLE (pts(i).x, pts(i).y), 5, pts(i).c
19. NEXT
20. _DELAY .5
21. FOR y = 0 TO xymax
22.     FOR x = 0 TO xymax
23.         minD = 49000
24.         FOR p = 1 TO nPoints
25.             d = ((pts(p).x - x) ^ 2 + (pts(p).y - y) ^ 2) ^ .5
26.             IF d < minD THEN minD = d: saveP = p
27.         NEXT
28.         PSET (x, y), pts(saveP).c
29.     NEXT
30. NEXT
31.  

Title: Re: Intersection of two circles
Post by: OldMoses on December 11, 2019, 05:50:42 pm

I was going to say that code looks a bit like the ray tracing stuff I was shoe horning into my space flight ap, and when when you mentioned quadratics, that cinched it. Interesting stuff.

Title: Re: Intersection of two circles
Post by: SierraKen on December 11, 2019, 06:08:53 pm

Pretty neat SMcNeill. I see there could be more than 2 intersections which could be the problem on Static's and mine. It might just be giving the first 2 and then ending without having the ability to give more. It would need a big overhaul in the code to be able to do that I think so I'm just going to let Static look at his. And I also could be wrong. But it would make sense I think.

Title: Re: Intersection of two circles
Post by: Pete on December 11, 2019, 06:41:39 pm

Actually if I had to tackle this, I'd do so like Steve did. Let the computer figure it out. I'm so far out of trig, and I never even took calc. I suppose it is because of what I learned in my high school probability class... which is I probably would never need the stuff.

Pete

Mr. Computer to Steve: Please Mr. Hands, give me an algorithm!

Mr. Hands to Mr. Computer. What's that Mr. Computer, you want me to upload Mr. Sluggo?

Oh no Mr. Hands, not Mr. Sluggo. He'll be mean to me...

Well Mr. Bill's invention, then shut up and loop!!!!!!

 

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 11, 2019, 10:00:58 pm

Any method that can be reduced or duplicated by printing the two circles on two pages and holding the pages up to the light to look for intersections is... cute, but I hope we don't need to explain the fallibility of these methods. At this point I have a choice: (i) either spruce up the sample code so it works nicely in all quadrants, or (ii) write up the derivation so then anyone can do it properly. Choices choices... where's my bong?

Title: Re: Intersection of two circles
Post by: Pete on December 11, 2019, 10:18:46 pm

I should clarify, by Mr. Bill's invention, I was referencing Bill Gates, as the inventor of the computer. You probably got that, but just to be sure. Yeah, yeah, yeah, it's a stretch, he only bought an operating system, but Wosniack's first name isn't Bill. Anyway, SNL 1970's skits aside, so what are the practical implications? Generally, I live by two rules and a saying. The rules are, Rule #1 don't do anything without having an idea. Rule #2, makes sure the idea is a good one, and the saying: "Just because you can doesn't mean you should." So if this is a boat load of un-fun work, I hope it proves useful. I mean a lot of math is impressive onto itself, but when it can be used for practical purposes, it's priceless.

Pete

Title: Re: Intersection of two circles
Post by: SierraKen on December 11, 2019, 11:12:34 pm

No pressure Static, whatever you want to do of course. I was just playing around with it.

Title: Re: Intersection of two circles
Post by: bplus on December 11, 2019, 11:19:21 pm

Quote from: STxAxTIC on December 11, 2019, 10:00:58 pm

Any method that can be reduced or duplicated by printing the two circles on two pages and holding the pages up to the light to look for intersections is... cute, but I hope we don't need to explain the fallibility of these methods. At this point I have a choice: (i) either spruce up the sample code so it works nicely in all quadrants, or (ii) write up the derivation so then anyone can do it properly. Choices choices... where's my bong?

Just use bplus tried and true code taken from some C algo thing or prove it fails at some point.  It is only Analytic Geometry, pre-Calculus stuff for goodness sake. Wait... I should have notes somewhere from July 3....,

update: oh that's the translation from SmallBASIC, dang this is going to take some digging...

Title: Re: Intersection of two circles
Post by: bplus on December 11, 2019, 11:53:12 pm

From 2015-09-12 2 pages of SmallBASIC code notes say Stackoverflow:

Yes this looks like my notes: https://stackoverflow.com/questions/3349125/circle-circle-intersection-points

First answer (of 5) written by Paul Bourke.

Title: Re: Intersection of two circles
Post by: Qwerkey on December 12, 2019, 05:16:58 am

So, I've had an independent go at it (even though, I'm sure, bplus has got the maths completely covered).

In the diagram (intersecting circles.jpg), we need to find the positions of C and D.

So, we need to consider triangles ABC and ABD.  I'm using just the centres outside each other condition in this case.

Firstly, the triangle ABD is just a reflection of ABC about the line AB, so only do ABC.  Secondly, the whole thing can be treated as if AB is the x- axis, and then do the (trivial) rotational translation conversion - STxAxTIC & bplus will know this and can easily be found in Wiki.

So consider the triangle ABC at the bottom of the diagram.  The distance between A and B = x1 + x2, and the distance from line AB to C is y.  We need to calculate x1 (and x2) and y.  We know AB, R1 and R2.

So, there is a formula to get triangle angles if all three sides are known.  See the (triangle angles.jpg) document, from Wiki (see the URL).

Thus, in our case alpha = arccos((R1^2+(x1+x2)^2-R2^2)/2*R1*(x1+x2))

When we know alpha, we know x1 and y, and therefore the position of C.

Using the angle theta and the rotational translation we can then get the actual position of C and similarly D.

Ah, trigonometry!  How wonderful.


Quod erat demonstrandum.  I claim my Librarian's Prize.  First prize is a 5 minute lecture on US politics given by Pete.  The booby prize is his hour-long lecture.

https://en.wikipedia.org/wiki/Solution_of_triangles#Three_sides_given_(spherical_SSS) (https://en.wikipedia.org/wiki/Solution_of_triangles#Three_sides_given_(spherical_SSS))

Title: Re: Intersection of two circles
Post by: Pete on December 12, 2019, 02:11:13 pm

Quote from: Qwerkey on December 12, 2019, 05:16:58 am

...I claim my Librarian's Prize.  First prize is a 5 minute lecture on US politics given by Pete.  The booby prize is his hour-long lecture.
https://en.wikipedia.org/wiki/Solution_of_triangles#Three_sides_given_(spherical_SSS) (https://en.wikipedia.org/wiki/Solution_of_triangles#Three_sides_given_(spherical_SSS))

Oh come on Richard, the contest isn't over yet, and that prize tiering isn't at all fair! I mean sure, if Bill wins, he'd of course enjoy my 5-min lecture on U.S. politics, but we all know Bill likes boobies a whole lot more! Way to rig the contest!!!

Pete :D

Title: Re: Intersection of two circles
Post by: SierraKen on December 12, 2019, 04:28:21 pm

OK because well, I put myself up to it, I decided to try this whole thing from scratch myself using the POINT command and my circle code. After working on it all morning and some afternoon, I think I got it down. It might not be perfect, but it's as good as I can do it. What it does is, first it draws the 2 circles you want at the beginning. Then it draws the first one again only this time it looks for the a slight variance in white which is the second one. Using POINT it then displays the coordinate and keeps going until the whole first circle is finished. Because this code breaks the coordinates up more and more the bigger the circle is, I added some IF/THEN statements to make the width lesser the bigger the circles are. Please try it and tell me what you think. I'm sure it's not 100% perfect, but it passes all the tests so far. :) Of course, mathematically 2 circles are only supposed to have up to 2 points of intersection, but like SMcNeill did, it just displays the coords it overlaps. So it can be anywhere from no intersection (which that is detected as well) to maybe 20 intersections or something like that. I draw little red circles around where the intersections are and list the intersection coordinates.

Edit: I added a couple lines of code so the user can't make the 2 circles too similar so only around up to 27 intersections can happen.

Code: QB64: [Select]

1. SCREEN _NEWIMAGE(800, 600, 32)
2. _TITLE "Circles Intersections Detector by Ken G."
3. begin:
4. _LIMIT 100
5. t = 0
6. i = 0
7. CLS
8. begin2:
9. INPUT "X1 (-300 to 300) = ", x1
10. IF x1 < -300 OR x1 > 300 THEN PRINT "Out of range, try again.": GOTO begin2:
11. INPUT "Y1 (-300 to 300) = ", y1
12. IF x1 < -300 OR x1 > 300 THEN PRINT "Out of range, try again.": GOTO begin2:
13. INPUT "Radius 1 (Up to 300) = ", r1
14. IF r1 = 0 OR r1 < 0 THEN PRINT "Radius cannot be 0 or below.": GOTO begin2:
15. INPUT "X2 (-300 to 300) = ", x2
16. IF x2 < -300 OR x2 > 300 THEN PRINT "Out of range, try again.": GOTO begin2:
17. INPUT "Y2 (-300 to 300) = ", y2
18. IF x2 < -300 OR x2 > 300 THEN PRINT "Out of range, try again.": GOTO begin2:
19. INPUT "Radius 2 (Up to 300) = ", r2
20. IF r2 = 0 OR r2 < 0 THEN PRINT "Radius cannot be 0 or below.": GOTO begin2:
21. IF r1 > 300 OR r2 > 300 THEN PRINT "Radius cannot be larger than 300.": GOTO begin2:
22. IF x1 > x2 - 8 AND x1 < x2 + 8 AND y1 > y2 - 8 AND y1 < y2 + 8 AND r1 > r2 - 8 AND r1 < r2 + 8 THEN PRINT "Your 2 circles are too similar, try again.": GOTO begin2:
23.  
24.  
25. x1 = x1 + 400
26. y1 = y1 * -1 + 300
27. x2 = x2 + 400
28. y2 = y2 * -1 + 300
29.  
30. 'Set width between circle points.
31. IF r1 < 100 THEN sc1 = 1
32. IF r1 < 200 AND r1 > 99 THEN sc1 = .5
33. IF r1 < 301 AND r1 > 199 THEN sc1 = .25
34. IF r2 < 100 THEN sc2 = 1
35. IF r2 < 200 AND r2 > 99 THEN sc2 = .5
36. IF r2 < 301 AND r2 > 199 THEN sc2 = .25
37.  
38.  
39. CLS
40. FOR yy = 0 TO 600 STEP 10
41.     LINE (400, yy)-(400, yy + 5), _RGB32(255, 255, 255)
42. NEXT yy
43. FOR xx = 0 TO 800 STEP 10
44.     LINE (xx, 300)-(xx + 5, 300), _RGB32(255, 255, 255)
45. NEXT xx
46.  
47. 'Make first circle and on second GOTO when t=1, check POINT color.
48. one:
49. _LIMIT 100
50. seconds = seconds + sc1
51. s = (60 - seconds) * 6 + 180
52. x = INT(SIN(s / 180 * 3.141592) * r1) + x1
53. y = INT(COS(s / 180 * 3.141592) * r1) + y1
54. FOR z = -1 TO 1
55.     IF t = 1 AND POINT(x + z, y + z) = _RGB32(255, 254, 255) THEN
56.         FOR sz = 1 TO 5 STEP .5
57.             CIRCLE (x, y), sz, _RGB32(255, 0, 0)
58.         NEXT sz
59.         PRINT "("; x - 400; ","; y * -1 + 300; ")"
60.         i = 1
61.     END IF
62. NEXT z
63. FOR sz = .25 TO 2 STEP .25
64.     CIRCLE (x, y), sz, _RGB32(255, 255, 255)
65. NEXT sz
66. IF seconds > 60 THEN
67.     seconds = 0
68.     GOTO two:
69. END IF
70. GOTO one:
71. 'Make second circle.
72. two:
73. _LIMIT 100
74. IF t = 1 THEN GOTO nex:
75. seconds = seconds + sc2
76. s2 = (60 - seconds) * 6 + 180
77. x3 = INT(SIN(s2 / 180 * 3.141592) * r2) + x2
78. y3 = INT(COS(s2 / 180 * 3.141592) * r2) + y2
79. FOR sz = .25 TO 2 STEP .25
80.     CIRCLE (x3, y3), sz, _RGB32(255, 254, 255)
81. NEXT sz
82. IF seconds > 60 THEN
83.     seconds = 0
84.     GOTO three:
85. END IF
86. GOTO two:
87. three:
88. t = t + 1
89. IF t = 2 THEN GOTO nex:
90. GOTO one:
91.  
92. nex:
93. IF i = 0 THEN PRINT "No Intersections": PRINT
94. PRINT "Again (Y/N)?"
95. again:
96. ag$ = INKEY$
97. IF ag$ = "y" OR ag$ = "Y" THEN GOTO begin:
98. IF ag$ = "n" OR ag$ = "N" THEN END
99. GOTO again:
100.  

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 12, 2019, 06:14:14 pm

Hey all, finally gonna be able to give this more time tonight. Soon...

@bplus
Looks like you nailed this problem long ago, as I expect this should have been well-solved by *someone* out there. Leave it to stackoverflow, right? The equations in your sub versus my code look very similar (as they should in the end) so I was originally curious how you got it, thanks for following up. The solution you point to ends up being a tad simpler than mine, but then again I like to apply methods that don't need to be limited to circles, so the derivation was a longer walk.

@Querkey
Nice picture, nice explanation - I kindof followed it whilst on the road, I'll give it a second look. What I'm seeing is that most everyone solves this the same way, practically with the same picture.

As for the so-called prize, I'm not sure what to do. bplus certainly had the code sooner than anyone, explored this the earliest, in relative terms. Querkey on the other hand, posted his derivation right in the forums... but nobody derived the equations in my code right before my eyes yet...

Title: Re: Intersection of two circles
Post by: bplus on December 12, 2019, 07:41:19 pm

Ha I think Qwerkey should get some kind of prize should he finish what he started, so far he has gotten us the "a" value and then kind of skipped over the rest. To get a prize one should write some code that produces some results that can be verified or laughed at :D

(Ken and Steve can pick up their prizes right now, Pete your on...)

Can he lay out the a distance along the two origins of circles then draw 2 perpendiculars the length of l in his diagram? (Wait has he solved for l as well as a?) Might not be as simple as Paul Bourke's but pretty easy to follow.

Here is a hint: the angle of the 2nd origin to the first is

angle = _ATAN2(oy2 - oy1, ox2-ox1)

Then point 3 between origins where the perpendiculars hang out the l's is
p3x = ox1 + a*cos(angle)
p3y = oy1 + a*sin(angle)

and so the intersect points should be:
i1x = p3x + l*cos(angle - pi/2)
i1y = p3y + l*sin(angle - pi/2)

i2x = p3x + l*cos(angle + pi/2)
i2y = p3y + l*sin(angle + pi/2)

if there is an intersection which might be good to check before doing all that math for side a ;-))
(PS assuming Qwerkey's side or length "a" is correct.)

Oh wait Qwerkey only has alpha solved, still need x1 (what I was calling side a, from the diagram I am familiar with.)

OK so if his alpha is right we can get x1 and l or y with alpha and R1 as he says algebra on sin and cos definitions.

 cos(alpha) = x1/R1 so x1 = R1*cos(alpha)
 sin(apha) = y/R1 so y or l = R1*sin(alpha)

OK now to check all this with real code.

Title: Re: Intersection of two circles
Post by: bplus on December 12, 2019, 08:38:23 pm

Hey what do you know!

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. intersect2circs C1x, C1y, r1, C2x, C2y, r2, int1x, int1y, int2x, int2y, p3x, p3y
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 intersect2circs (ox1, oy1, r1, ox2, oy2, r2, ix1, iy1, ix2, iy2, p3x, p3y)
19.  
20.     'if there is an intersection which might be good to check before doing all that math for side a ;-))
21.  
22.     d = ((ox1 - ox2) ^ 2 + (oy1 - oy2) ^ 2) ^ .5 'distance between the 2 origins = x1 + x2 in Qwerkey's diagram
23.  
24.     'alpha = _ACOS((r1 ^ 2 + (x1 + x2) ^ 2 - r2 ^ 2) / 2 * r1 * (x1 + x2))
25.     alpha = _ACOS((r1 ^ 2 + d ^ 2 - r2 ^ 2) / (2 * r1 * d)) '<<< need () around whole denominator
26.     '(PS assuming Qwerkey's side or length "a" is correct.)
27.     'It does look right now
28.  
29.     'solve  x1 and l of Qwerkey's diagram
30.     'cos(alpha) = x1/R1 so
31.     x1 = r1 * COS(alpha)
32.     'sin(apha) = y/R1 so y or
33.     l = r1 * SIN(alpha)
34.  
35.     'this is the angle of the 2nd circle origin to the first where alpha resides, on this line is point 3 from which perpendiculars go to intersect points
36.     angle = _ATAN2(oy2 - oy1, ox2 - ox1)
37.  
38.     'Then point 3 between origins where the perpendiculars hang out the l's is
39.     p3x = ox1 + x1 * COS(angle)
40.     p3y = oy1 + x1 * SIN(angle)
41.  
42.     'and so the intersect points should be:
43.     ix1 = p3x + l * COS(angle - _PI / 2)
44.     iy1 = p3y + l * SIN(angle - _PI / 2)
45.  
46.     ix2 = p3x + l * COS(angle + _PI / 2)
47.     iy2 = p3y + l * SIN(angle + _PI / 2)
48.  
49.  
50.  
51. END SUB
52.  
53.  

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 12, 2019, 08:49:12 pm

Bravo, bplus and Qwerkey.

I absolutely neglected acos and atan in my solution. Yours will inevitably be the best and simplest for two circles. I should make it tougher next time.

How about two ellipses?

Title: Re: Intersection of two circles
Post by: SMcNeill on December 12, 2019, 09:01:15 pm

Quote from: STxAxTIC on December 12, 2019, 08:49:12 pm

Bravo, bplus and Qwerkey.

I absolutely neglected acos and atan in my solution. Yours will inevitably be the best and simplest for two circles. I should make it tougher next time.

How about two ellipses?

My solution will still work; even if you want to detect intersections of polygons, lines, curves, or scribbles.  ;D

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 12, 2019, 09:03:52 pm

Veeeeery funny Steve! I mean, it's not wrong for shapes that render to the screen. But off-screen? Or even fractals... fascinating... This question has too many fun directions.

Title: Re: Intersection of two circles
Post by: bplus on December 12, 2019, 09:14:13 pm

Yeah Steve's method will work with anything even solids overlaps, maybe paint an image in the overlap ;)

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 12, 2019, 09:30:41 pm

Alright, here is what my notes look like as a problem at the end of my Vectors document. This notation is a little dense, but needs no geometry, no pictures. We let vectors do the talking here.

Title: Re: Intersection of two circles
Post by: SierraKen on December 12, 2019, 11:33:47 pm

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.

Title: Re: Intersection of two circles
Post by: bplus on December 13, 2019, 12:10:23 am

Quote from: SierraKen on December 12, 2019, 11:33:47 pm

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 ;)

Title: Re: Intersection of two circles
Post by: SierraKen on December 13, 2019, 02:10:43 am

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

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 13, 2019, 07:02:54 am

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.

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 13, 2019, 09:23:26 am

... 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.  

Title: Re: Intersection of two circles
Post by: bplus on December 13, 2019, 11:59:22 am

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,

Quote

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.

Quote

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.  

Title: Re: Intersection of two circles
Post by: AndyA on December 13, 2019, 10:14:47 pm

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/ (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 (http://paulbourke.net/geometry/circlesphere/tvoght.c) )


The Blitz Basic I posted can be found here : https://socoder.net/?Snippet=26103 (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/ (http://paulbourke.net/geometry/pointlineplane/) I used the
C code for Line segments intersect algo to use in Blitz Basic  [/ edit ]

Title: Re: Intersection of two circles
Post by: STxAxTIC on December 13, 2019, 11:48:29 pm

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.

Title: Re: Intersection of two circles
Post by: AndyA on December 14, 2019, 11:43:44 am

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/ (https://www.ics.uci.edu/~eppstein/junkyard/). Many links are broken, but still a neat place for ideas.

Title: Re: Intersection of two circles
Post by: bplus on December 14, 2019, 12:35:41 pm

Nice link Andy, thanks!

Text Only | Text with Attachments