Intersection of two circles

[STxAxTIC]

From our lovely Discord chat:

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

[Qwerkey]

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.

[STxAxTIC]

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.

[bplus]

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.  

[Pete]

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

[STxAxTIC]

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

[SierraKen]

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.  

 

[STxAxTIC]

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.

[Zeppelin]

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

[SMcNeill]

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. 

[bplus]

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.  

[OldMoses]

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.

[SierraKen]

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.

[Pete]

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

 

[STxAxTIC]

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?