Circle Intersect Line

[bplus]

Changed title to more general topic of Circle Intersect Line, see best answer

This is actually a demo to find the point on a line the shortest distance from a given point off the line.

Code: QB64: [Select]

1. _TITLE "Draw Circle Tangent to Line at Given Pt" 'B+ 2020-01-29
2. ' see Find point on line perpendicular to line at another point for how I worked this out
3. ' This merely demo's the 2 subs I will need for Geonetric Construction
4.  
5. ' let p1 = mx(1), my(1) = 1 point of the line
6. ' let p2 = mx(2), my(2) = 2nd point on line (or segment)
7. ' let p3 = mx(3), my(3) = origin to circle to make tangent to line = shortest dist to line from that point
8.  
9. ' x, y finds the line perpendicular to line formed by p1 and p2 from p3 to x, y
10.  
11. CONST xmax = 800, ymax = 600
12. SCREEN _NEWIMAGE(xmax, ymax, 32)
13. _SCREENMOVE 300, 40
14.  
15. DO
16.     CLS
17.     PRINT "2 clicks to form a line, a 3rd click for circle origin:"
18.     WHILE pi < 3 'get 3 mouse clicks
19.         _PRINTSTRING (20, 20), SPACE$(25)
20.         _PRINTSTRING (20, 20), "Need 3 clicks, have" + STR$(pi)
21.         WHILE _MOUSEINPUT: WEND
22.         IF _MOUSEBUTTON(1) AND oldMouse = 0 THEN 'new mouse down
23.             pi = pi + 1
24.             mx(pi) = _MOUSEX: my(pi) = _MOUSEY
25.             CIRCLE (mx(pi), my(pi)), 2
26.             IF pi = 2 THEN 'draw first line segment then line
27.                 drawLine mx(1), my(1), mx(2), my(2), &HFF000099
28.                 LINE (mx(1), my(1))-(mx(2), my(2))
29.             END IF
30.         END IF
31.         oldMouse = _MOUSEBUTTON(1)
32.         _DISPLAY
33.         _LIMIT 60
34.     WEND
35.     _PRINTSTRING (20, 20), SPACE$(25)
36.     circleTangentXY mx(1), my(1), mx(2), my(2), mx(3), my(3), x, y
37.     CIRCLE (x, y), 2, &HFFFFFF00 'yellow circle should be on line perpendicular to 3rd click point
38.     LINE (mx(3), my(3))-(x, y), &HFFFFFF00
39.     CIRCLE (mx(3), my(3)), SQR((mx(3) - x) ^ 2 + (my(3) - y) ^ 2), &HFFFFFF00
40.     _DISPLAY
41.     _DELAY 5
42.     pi = 0 'point index
43. LOOP UNTIL _KEYDOWN(27)
44.  
45. SUB circleTangentXY (X1, Y1, X2, Y2, xC, yC, findXperp, findYperp)
46.     'p1 and p2 form a line, with slop and y intersect y0
47.     'xC, yC is a circle origin
48.     'we find X, Y such that line x, y to xC, yC is perpendicular to p1, p2 line that is radius of tangent circle
49.     slope = (Y2 - Y1) / (X2 - X1)
50.     y0 = slope * (0 - X1) + Y1
51.     A = slope ^ 2 + 1
52.     B = 2 * (slope * y0 - slope * yC - xC)
53.     findXperp = -B / (2 * A)
54.     findYperp = slope * findXperp + y0
55. END SUB
56.  
57. SUB drawLine (x1, y1, x2, y2, K AS _UNSIGNED LONG)
58.     slope = (y2 - y1) / (x2 - x1)
59.     y0 = slope * (0 - x1) + y1
60.     LINE (0, y0)-(_WIDTH, slope * _WIDTH + y0), &HFF0000FF
61. END SUB
62.  
63.  

[STxAxTIC]

Ah, applied geometry. A personal fav.

I was able to make it fail instantly though, cause I knew what special case to look for - if your first two points are on the same vertical line, the circle doesn't show when you click for the third point. (The calculation becomes trivial in this case so who even cares though right?!)

Challenge: Do it for ellipses next!

... or *any* curve. Actually please beat me to it because this sounds interesting - trivial in fact if you use my technique to go from PSET to DRAW. Hm, I might have to do it now... (by now I mean later)

[bplus]

Oh Thanks STxAxTIC, division by 0 for verticals, I see.

Here is the fix:

Code: QB64: [Select]

1. _TITLE "Draw Circle Tangent to Line at Given Pt" 'B+ 2020-01-29
2. ' see Find point on line perpendicular to line at another point for how I worked this out
3. ' This merely demo's the 2 subs I will need for Geonetric Construction
4.  
5. ' let p1 = mx(1), my(1) = 1 point of the line
6. ' let p2 = mx(2), my(2) = 2nd point on line (or segment)
7. ' let p3 = mx(3), my(3) = origin to circle to make tangent to line = shortest dist to line from that point
8.  
9. ' x, y finds the line perpendicular to line formed by p1 and p2 from p3 to x, y
10.  
11. CONST xmax = 800, ymax = 600
12. SCREEN _NEWIMAGE(xmax, ymax, 32)
13. _SCREENMOVE 300, 40
14.  
15. DO
16.     CLS
17.     lc = lc + 1
18.     IF lc = 1 THEN
19.         mx(1) = 400: my(1) = 200: mx(2) = 400: my(2) = 205: mx(3) = 500: my(3) = 300
20.         drawLine mx(1), my(1), mx(2), my(2), &HFF000099
21.         circleTangentXY mx(1), my(1), mx(2), my(2), mx(3), my(3), x, y
22.         CIRCLE (x, y), 2, &HFFFFFF00 'yellow circle should be on line perpendicular to 3rd click point
23.         LINE (mx(3), my(3))-(x, y), &HFFFFFF00
24.         CIRCLE (mx(3), my(3)), SQR((mx(3) - x) ^ 2 + (my(3) - y) ^ 2), &HFFFFFF00
25.         _DISPLAY
26.         _DELAY 5
27.         CLS
28.     END IF
29.     PRINT "2 clicks to form a line, a 3rd click for circle origin:"
30.     WHILE pi < 3 'get 3 mouse clicks
31.         _PRINTSTRING (20, 20), SPACE$(25)
32.         _PRINTSTRING (20, 20), "Need 3 clicks, have" + STR$(pi)
33.         WHILE _MOUSEINPUT: WEND
34.         IF _MOUSEBUTTON(1) AND oldMouse = 0 THEN 'new mouse down
35.             pi = pi + 1
36.             mx(pi) = _MOUSEX: my(pi) = _MOUSEY
37.             CIRCLE (mx(pi), my(pi)), 2
38.             IF pi = 2 THEN 'draw first line segment then line
39.                 drawLine mx(1), my(1), mx(2), my(2), &HFF000099
40.                 LINE (mx(1), my(1))-(mx(2), my(2))
41.             END IF
42.         END IF
43.         oldMouse = _MOUSEBUTTON(1)
44.         _DISPLAY
45.         _LIMIT 60
46.     WEND
47.     _PRINTSTRING (20, 20), SPACE$(25)
48.     circleTangentXY mx(1), my(1), mx(2), my(2), mx(3), my(3), x, y
49.     CIRCLE (x, y), 2, &HFFFFFF00 'yellow circle should be on line perpendicular to 3rd click point
50.     LINE (mx(3), my(3))-(x, y), &HFFFFFF00
51.     CIRCLE (mx(3), my(3)), SQR((mx(3) - x) ^ 2 + (my(3) - y) ^ 2), &HFFFFFF00
52.     _DISPLAY
53.     _DELAY 5
54.     pi = 0 'point index
55. LOOP UNTIL _KEYDOWN(27)
56.  
57. SUB circleTangentXY (X1, Y1, X2, Y2, xC, yC, findXperp, findYperp)
58.     'p1 and p2 form a line, with slop and y intersect y0
59.     'xC, yC is a circle origin
60.     'we find X, Y such that line x, y to xC, yC is perpendicular to p1, p2 line that is radius of tangent circle
61.     IF X2 <> X1 THEN
62.         slope = (Y2 - Y1) / (X2 - X1)
63.         y0 = slope * (0 - X1) + Y1
64.         A = slope ^ 2 + 1
65.         B = 2 * (slope * y0 - slope * yC - xC)
66.         findXperp = -B / (2 * A)
67.         findYperp = slope * findXperp + y0
68.     ELSE
69.         findXperp = X1
70.         findYperp = yC
71.     END IF
72. END SUB
73.  
74. SUB drawLine (x1, y1, x2, y2, K AS _UNSIGNED LONG)
75.     IF x2 <> x1 THEN
76.         slope = (y2 - y1) / (x2 - x1)
77.         y0 = slope * (0 - x1) + y1
78.         LINE (0, y0)-(_WIDTH, slope * _WIDTH + y0), K
79.     ELSE
80.         LINE (x1, 0)-(x1, _HEIGHT), K
81.     END IF
82. END SUB
83.  
84.  

I see I forgot to set color at K also.

[OldMoses]

Nice. I think I'll file this one away as a possible basis for an orbital insertion routine.

[bplus]

In my haste to do the Triangle Dissection, I did not finish the complete code version of Circle Intersect Line with 3 possible outcomes:
1. no intersect with radius
2. intersect Circle tangent to Line, 1 point
3. intersect 2 places on radius, 2 points located

Here is the more complete coverage of cases:

Code: QB64: [Select]

1. _TITLE "Circle Intersect Line" ' b+ 2020-01-31 develop
2. ' Find point on line perpendicular to line at another point" 'B+ 2019-12-15
3. ' further for a Line and Circle Intersect, making full use of the information from the link below.
4.  
5. CONST xmax = 800, ymax = 600
6. SCREEN _NEWIMAGE(xmax, ymax, 32)
7. _SCREENMOVE 300, 40
8.  
9. DO
10.     CLS
11.     IF testTangent = 0 THEN 'test plug in set of border conditions not easy to click
12.         PRINT "First set here is a plug in test set for vertical lines."
13.         mx(1) = 200: my(1) = 100: mx(2) = 200: my(2) = 400 'line  x = 200
14.         mx(3) = 400: my(3) = 300: mx(4) = 150: my(4) = 300 ' circle origin (center 400, 300) then radius test 200 tangent, 150 more than tangent, 250 short
15.         FOR i = 1 TO 4
16.             CIRCLE (mx(i), my(i)), 2
17.         NEXT
18.         IF mx(1) <> mx(2) THEN
19.             slopeYintersect mx(1), my(1), mx(2), my(2), m, Y0 ' Y0 otherwise know as y Intersect
20.             LINE (0, Y0)-(xmax, m * xmax + Y0), &HFF0000FF
21.             LINE (mx(1), my(1))-(mx(2), my(2))
22.         ELSE
23.             LINE (mx(1), 0)-(mx(1), ymax), &HFF0000FF
24.             LINE (mx(1), my(1))-(mx(2), my(2))
25.         END IF
26.         testTangent = 1
27.     ELSE
28.         PRINT "First 2 clicks will form a line, 3rd the circle origin and 4th the circle radius:"
29.         WHILE pi < 4 'get 4 mouse clicks
30.             _PRINTSTRING (20, 20), SPACE$(20)
31.             _PRINTSTRING (20, 20), "Need 4 clicks, have" + STR$(pi)
32.             WHILE _MOUSEINPUT: WEND
33.             IF _MOUSEBUTTON(1) AND oldMouse = 0 THEN 'new mouse down
34.                 pi = pi + 1
35.                 mx(pi) = _MOUSEX: my(pi) = _MOUSEY
36.                 CIRCLE (mx(pi), my(pi)), 2
37.                 IF pi = 2 THEN 'draw first line segment then line
38.                     IF mx(1) <> mx(2) THEN
39.                         slopeYintersect mx(1), my(1), mx(2), my(2), m, Y0 ' Y0 otherwise know as y Intersect
40.                         LINE (0, Y0)-(xmax, m * xmax + Y0), &HFF0000FF
41.                         LINE (mx(1), my(1))-(mx(2), my(2))
42.                     ELSE
43.                         LINE (mx(1), 0)-(mx(1), ymax), &HFF0000FF
44.                         LINE (mx(1), my(1))-(mx(2), my(2))
45.                     END IF
46.                 END IF
47.             END IF
48.             oldMouse = _MOUSEBUTTON(1)
49.             _DISPLAY
50.             _LIMIT 60
51.         WEND
52.     END IF
53.     p = mx(3): q = my(3)
54.     r = SQR((mx(3) - mx(4)) ^ 2 + (my(3) - my(4)) ^ 2)
55.     CIRCLE (p, q), r, &HFFFF0000
56.     IF mx(1) = mx(2) THEN 'line is vertical so if r =
57.         IF r = ABS(mx(1) - mx(3)) THEN ' one point tangent intersect
58.             PRINT "Tangent point is "; TS$(mx(1)); ", "; TS$(my(3))
59.             CIRCLE (mx(1), my(3)), 2, &HFFFFFF00
60.             CIRCLE (mx(1), my(3)), 4, &HFFFFFF00
61.         ELSEIF r < ABS(mx(1) - mx(3)) THEN 'no intersect
62.             PRINT "No intersect, radius too small."
63.         ELSE '2 point intersect
64.             ydist = SQR(r ^ 2 - (mx(1) - mx(3)) ^ 2)
65.             y1 = my(3) + ydist
66.             y2 = my(3) - ydist
67.             PRINT "2 Point intersect (x1, y1) = "; TS$(mx(1)); ", "; TS$(y1); "  (x2, y2) = "; TS$(mx(1)); ", "; TS$(y2)
68.             CIRCLE (mx(1), y1), 2, &HFFFFFF00 'marking intersect points yellow
69.             CIRCLE (mx(1), y2), 2, &HFFFFFF00
70.             CIRCLE (mx(1), y1), 4, &HFFFFFF00 'marking intersect points yellow
71.             CIRCLE (mx(1), y2), 4, &HFFFFFF00
72.  
73.         END IF
74.     ELSE
75.         'OK the calculations!
76.         'from inserting eq ofline into eq of circle where line intersects circle see reference
77.         ' https://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
78.         A = m ^ 2 + 1
79.         B = 2 * (m * Y0 - m * q - p)
80.         C = q ^ 2 - r ^ 2 + p ^ 2 - 2 * Y0 * q + Y0 ^ 2
81.         D = B ^ 2 - 4 * A * C 'telling part of Quadratic formula = 0 then circle is tangent  or > 0 then 2 intersect points
82.         IF D < 0 THEN ' no intersection
83.             PRINT "m, y0 "; TS$(m); ", "; TS$(Y0)
84.             PRINT "(p, q) "; TS$(p); ", "; TS$(q)
85.             PRINT "A: "; TS$(A)
86.             PRINT "B: "; TS$(B)
87.             PRINT "C: "; TS$(C)
88.             PRINT "D: "; TS$(D); " negative so no intersect."
89.         ELSEIF D = 0 THEN ' one point tangent
90.             x1 = (-B + SQR(D)) / (2 * A)
91.             y1 = m * x1 + Y0
92.             PRINT "Tangent Point Intersect (x1, y1) = "; TS$(x1); ", "; TS$(y1)
93.             CIRCLE (x1, y1), 2, &HFFFFFF00 'yellow circle should be on line perprendicular to 3rd click point
94.             CIRCLE (x1, y1), 4, &HFFFFFF00 'yellow circle should be on line perprendicular to 3rd click point
95.         ELSE
96.             '2 points
97.             x1 = (-B + SQR(D)) / (2 * A): y1 = m * x1 + Y0
98.             x2 = (-B - SQR(D)) / (2 * A): y2 = m * x2 + Y0
99.             PRINT "2 Point intersect (x1, y1) = "; TS$(x1); ", "; TS$(y1); "  (x2, y2) = "; TS$(x2); ", "; TS$(y2)
100.             CIRCLE (x1, y1), 2, &HFFFFFF00 'marking intersect points yellow
101.             CIRCLE (x2, y2), 2, &HFFFFFF00
102.             CIRCLE (x1, y1), 4, &HFFFFFF00 'marking intersect points yellow
103.             CIRCLE (x2, y2), 4, &HFFFFFF00
104.         END IF
105.     END IF
106.     _DISPLAY
107.     INPUT "press enter to continue, any + enter to quit "; q$
108.     IF LEN(q$) THEN SYSTEM
109.     pi = 0 'point index
110. LOOP UNTIL _KEYDOWN(27)
111.  
112. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) ' fix for when x1 = x2
113.     slope = (Y2 - Y1) / (X2 - X1)
114.     Yintercept = slope * (0 - X1) + Y1
115. END SUB
116.  
117. FUNCTION TS$ (n)
118.     TS$ = _TRIM$(STR$(n))
119. END FUNCTION
120.  
121.  

[bplus]

OK the vertical line case has been added to above code and tested with a plug in set but still want to wrap this up into a SUB for a toolbox routine. Thank you math.stackexchange for having formulas worked out and correct.

[bplus]

@STxAxTIC

Oh man! Had I known you were interested in Circle Intersect Line for samples I would have added this update I did to "fix" Hypnotic Polygon Orbits https://www.qb64.org/forum/index.php?topic=2234.0

From last Best Answer (reply #4), I did this, to put code into sub for useful tool:

Code: QB64: [Select]

1. _TITLE "Sub PointOnLinePerp2Point" 'b+ 2020-02-25 from
2. ' Find point on line perpendicular to line at another point" 'B+ 2019-12-15
3. ' let p1 = mx(1), my(1) = 1 point of the line
4. ' let p2 = mx(2), my(2) = 2nd point on line (or segment)
5. ' let p3 = mx(3), my(3)
6. 'See circle tangent to line for best sub routines worked out here
7.  
8. CONST xmax = 800, ymax = 600
9. SCREEN _NEWIMAGE(xmax, ymax, 32)
10. _SCREENMOVE 300, 40
11.  
12. DO
13.     CLS
14.     WHILE pi < 3 'get 3 mouse clicks
15.         _PRINTSTRING (5, 5), SPACE$(20)
16.         _PRINTSTRING (5, 5), "Need 3 clicks, have" + STR$(pi)
17.         WHILE _MOUSEINPUT: WEND
18.         IF _MOUSEBUTTON(1) AND oldMouse = 0 THEN 'new mouse down
19.             pi = pi + 1
20.             mx(pi) = _MOUSEX: my(pi) = _MOUSEY
21.             CIRCLE (mx(pi), my(pi)), 2
22.             IF pi = 2 THEN 'draw first line segment then line
23.                 slopeYintersect mx(1), my(1), mx(2), my(2), m, Y0 ' Y0 otherwise know as y Intersect
24.                 LINE (0, Y0)-(xmax, m * xmax + Y0), &HFF0000FF
25.                 LINE (mx(1), my(1))-(mx(2), my(2))
26.             END IF
27.         END IF
28.         oldMouse = _MOUSEBUTTON(1)
29.         _DISPLAY
30.         _LIMIT 60
31.     WEND
32.  
33.     'p = mx(3): q = my(3) ': r = 800 ' SQR(xmax ^ 2 + ymax ^ 2) ' this is varaiables for max circle that can be clicked on screen r is rediculously big
34.     ''from inserting eq of line into eq of circle where line intersects circle
35.     '' https://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
36.     'A = m ^ 2 + 1
37.     'B = 2 * (m * Y0 - m * q - p)
38.     ''C = q ^ 2 - r ^ 2 + p ^ 2 - 2 * Y0 * q + Y0 ^ 2   <<< don't need
39.     ''because r is rediculously large the line must intersect at two points likely beyond the screen limits
40.     ''but the middle of those two points is exactly the point we want
41.     ''D = B ^ 2 - 4 * A * C
42.     'IF D < 0 THEN
43.     '    LOCATE 5, 1
44.     '    PRINT "m, y0"; m; ","; Y0
45.     '    PRINT "(p, q)"; p; ","; q
46.     '    PRINT "A:"; A
47.     '    PRINT "B:"; B
48.     '    'PRINT "C:"; C
49.     '    'PRINT "D:"; D
50.  
51.     '    BEEP
52.     'ELSE
53.     '    'here is our point!
54.     '    x = -B / (2 * A)
55.     '    y = m * x + Y0
56.     '    PRINT "answer (x, y) = "; x, y
57.     '    CIRCLE (x, y), 2, &HFFFFFF00 'yellow circle should be on line perprendicular to 3rd click point
58.     '    LINE (p, q)-(x, y), &HFFFFFF00
59.     'END IF
60.  
61.  
62.     'test new sub
63.     PointOnLinePerp2Point mx(1), my(1), mx(2), my(2), mx(3), my(3), Rx, Ry
64.     PRINT "answer (x, y) = "; Rx, Ry
65.     CIRCLE (Rx, Ry), 2, &HFFFFFF00 'yellow circle should be on line perprendicular to 3rd click point
66.     LINE (mx(3), my(3))-(Rx, Ry), &HFFFFFF00
67.  
68.     _DISPLAY
69.     INPUT "press enter to continue, any + enter to quit "; q$
70.     IF LEN(q$) THEN SYSTEM
71.     pi = 0 'point index
72. LOOP UNTIL _KEYDOWN(27)
73.  
74. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) ' fix for when x1 = x2
75.     IF X1 = X2 THEN
76.         slope = X1
77.         Yintercept = Y2
78.     ELSE
79.         slope = (Y2 - Y1) / (X2 - X1)
80.         Yintercept = slope * (0 - X1) + Y1
81.     END IF
82. END SUB
83.  
84. SUB PointOnLinePerp2Point (Lx1, Ly1, Lx2, Ly2, Px, Py, Rx, Ry)
85.     '
86.     'this sub needs  SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) ' fix for when x1 = x2
87.     '
88.     'Lx1, Ly1, Lx2, Ly2     the two points that make a line
89.     'Px, Py is point off the line
90.     'Rx, Ry Return Point is the Point on the line perpendicular to Px, Py
91.     slopeYintersect Lx1, Ly1, Lx2, Ly2, m, Y0
92.     A = m ^ 2 + 1
93.     B = 2 * (m * Y0 - m * Py - Px)
94.     Rx = -B / (2 * A)
95.     Ry = m * Rx + Y0
96. END SUB
97.  
98.  

The two subs from this added in to here
https://www.qb64.org/forum/index.php?topic=2234.msg114838#msg114838

is what fixed the orbits to the polygon lines! (after changing their rates of orbit to 12ths of each other)

IMHO this IS a 2nd useful result of this geometric construction that can be applied in other programs:

Code: QB64: [Select]

1. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) ' fix for when x1 = x2
2.     IF X1 = X2 THEN
3.         slope = X1
4.         Yintercept = Y2
5.     ELSE
6.         slope = (Y2 - Y1) / (X2 - X1)
7.         Yintercept = slope * (0 - X1) + Y1
8.     END IF
9. END SUB
10.  
11. SUB PointOnLinePerp2Point (Lx1, Ly1, Lx2, Ly2, Px, Py, Rx, Ry)
12.     '
13.     'this sub needs  SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) ' fix for when x1 = x2
14.     '
15.     'Lx1, Ly1, Lx2, Ly2     the two points that make a line
16.     'Px, Py is point off the line
17.     'Rx, Ry Return Point is the Point on the line perpendicular to Px, Py
18.     slopeYintersect Lx1, Ly1, Lx2, Ly2, m, Y0
19.     A = m ^ 2 + 1
20.     B = 2 * (m * Y0 - m * Py - Px)
21.     Rx = -B / (2 * A)
22.     Ry = m * Rx + Y0
23. END SUB
24.  

And it looks like STxAxTIC already has a sub returning the points of intersect with a line for a circle ellipse.
https://www.qb64.org/forum/index.php?topic=2302.msg115268#msg115268

[STxAxTIC]

Oh cool bplus! For a second I was iffy because it can be seen as redundant to the elliptical case, but your code was so unique I posted both. In that same spirit, feel free to make a new thread with the fix and stuff.