### Author Topic: Circle Intersect Line  (Read 941 times)

0 Members and 1 Guest are viewing this topic.

This topic contains a post which is marked as Best Answer. Press here if you would like to see it.

#### bplus

• Forum Resident
• Posts: 6858
• b = b + ...
##### Circle Intersect Line
« on: January 29, 2020, 09:25:33 PM »
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.     PRINT "2 clicks to form a line, a 3rd click for circle origin:"
16.     WHILE pi < 3 'get 3 mouse clicks
17.         _PRINTSTRING (20, 20), SPACE\$(25)
18.         _PRINTSTRING (20, 20), "Need 3 clicks, have" + STR\$(pi)
19.         IF _MOUSEBUTTON(1) AND oldMouse = 0 THEN 'new mouse down
20.             pi = pi + 1
21.             mx(pi) = _MOUSEX: my(pi) = _MOUSEY
22.             CIRCLE (mx(pi), my(pi)), 2
23.             IF pi = 2 THEN 'draw first line segment then line
24.                 drawLine mx(1), my(1), mx(2), my(2), &HFF000099
25.                 LINE (mx(1), my(1))-(mx(2), my(2))
26.         oldMouse = _MOUSEBUTTON(1)
27.         _LIMIT 60
28.     _PRINTSTRING (20, 20), SPACE\$(25)
29.     circleTangentXY mx(1), my(1), mx(2), my(2), mx(3), my(3), x, y
30.     CIRCLE (x, y), 2, &HFFFFFF00 'yellow circle should be on line perpendicular to 3rd click point
31.     LINE (mx(3), my(3))-(x, y), &HFFFFFF00
32.     CIRCLE (mx(3), my(3)), SQR((mx(3) - x) ^ 2 + (my(3) - y) ^ 2), &HFFFFFF00
33.     pi = 0 'point index
34.
35. SUB circleTangentXY (X1, Y1, X2, Y2, xC, yC, findXperp, findYperp)
36.     'p1 and p2 form a line, with slop and y intersect y0
37.     'xC, yC is a circle origin
38.     'we find X, Y such that line x, y to xC, yC is perpendicular to p1, p2 line that is radius of tangent circle
39.     slope = (Y2 - Y1) / (X2 - X1)
40.     y0 = slope * (0 - X1) + Y1
41.     A = slope ^ 2 + 1
42.     B = 2 * (slope * y0 - slope * yC - xC)
43.     findXperp = -B / (2 * A)
44.     findYperp = slope * findXperp + y0
45.
46. SUB drawLine (x1, y1, x2, y2, K AS _UNSIGNED LONG)
47.     slope = (y2 - y1) / (x2 - x1)
48.     y0 = slope * (0 - x1) + y1
49.     LINE (0, y0)-(_WIDTH, slope * _WIDTH + y0), &HFF0000FF
50.
51.
« Last Edit: February 01, 2020, 11:00:14 AM by bplus »

#### STxAxTIC

• Library Staff
• Forum Resident
• Posts: 1062
• TOXIC
##### Re: Draw circle tangent to line at given point origin
« Reply #1 on: January 29, 2020, 09:52:04 PM »
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)
« Last Edit: January 29, 2020, 11:00:04 PM by STxAxTIC »
TOXIC

#### bplus

• Forum Resident
• Posts: 6858
• b = b + ...
##### Re: Draw circle tangent to line at given point origin
« Reply #2 on: January 29, 2020, 11:16:18 PM »
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.     lc = lc + 1
16.     IF lc = 1 THEN
17.         mx(1) = 400: my(1) = 200: mx(2) = 400: my(2) = 205: mx(3) = 500: my(3) = 300
18.         drawLine mx(1), my(1), mx(2), my(2), &HFF000099
19.         circleTangentXY mx(1), my(1), mx(2), my(2), mx(3), my(3), x, y
20.         CIRCLE (x, y), 2, &HFFFFFF00 'yellow circle should be on line perpendicular to 3rd click point
21.         LINE (mx(3), my(3))-(x, y), &HFFFFFF00
22.         CIRCLE (mx(3), my(3)), SQR((mx(3) - x) ^ 2 + (my(3) - y) ^ 2), &HFFFFFF00
23.     PRINT "2 clicks to form a line, a 3rd click for circle origin:"
24.     WHILE pi < 3 'get 3 mouse clicks
25.         _PRINTSTRING (20, 20), SPACE\$(25)
26.         _PRINTSTRING (20, 20), "Need 3 clicks, have" + STR\$(pi)
27.         IF _MOUSEBUTTON(1) AND oldMouse = 0 THEN 'new mouse down
28.             pi = pi + 1
29.             mx(pi) = _MOUSEX: my(pi) = _MOUSEY
30.             CIRCLE (mx(pi), my(pi)), 2
31.             IF pi = 2 THEN 'draw first line segment then line
32.                 drawLine mx(1), my(1), mx(2), my(2), &HFF000099
33.                 LINE (mx(1), my(1))-(mx(2), my(2))
34.         oldMouse = _MOUSEBUTTON(1)
35.         _LIMIT 60
36.     _PRINTSTRING (20, 20), SPACE\$(25)
37.     circleTangentXY mx(1), my(1), mx(2), my(2), mx(3), my(3), x, y
38.     CIRCLE (x, y), 2, &HFFFFFF00 'yellow circle should be on line perpendicular to 3rd click point
39.     LINE (mx(3), my(3))-(x, y), &HFFFFFF00
40.     CIRCLE (mx(3), my(3)), SQR((mx(3) - x) ^ 2 + (my(3) - y) ^ 2), &HFFFFFF00
41.     pi = 0 'point index
42.
43. SUB circleTangentXY (X1, Y1, X2, Y2, xC, yC, findXperp, findYperp)
44.     'p1 and p2 form a line, with slop and y intersect y0
45.     'xC, yC is a circle origin
46.     'we find X, Y such that line x, y to xC, yC is perpendicular to p1, p2 line that is radius of tangent circle
47.     IF X2 <> X1 THEN
48.         slope = (Y2 - Y1) / (X2 - X1)
49.         y0 = slope * (0 - X1) + Y1
50.         A = slope ^ 2 + 1
51.         B = 2 * (slope * y0 - slope * yC - xC)
52.         findXperp = -B / (2 * A)
53.         findYperp = slope * findXperp + y0
54.         findXperp = X1
55.         findYperp = yC
56.
57. SUB drawLine (x1, y1, x2, y2, K AS _UNSIGNED LONG)
58.     IF x2 <> x1 THEN
59.         slope = (y2 - y1) / (x2 - x1)
60.         y0 = slope * (0 - x1) + y1
61.         LINE (0, y0)-(_WIDTH, slope * _WIDTH + y0), K
62.         LINE (x1, 0)-(x1, _HEIGHT), K
63.
64.

I see I forgot to set color at K also.
« Last Edit: January 29, 2020, 11:18:00 PM by bplus »

#### OldMoses

• Seasoned Forum Regular
• Posts: 486
##### Re: Draw circle tangent to line at given point origin
« Reply #3 on: January 30, 2020, 01:04:48 PM »
Nice. I think I'll file this one away as a possible basis for an orbital insertion routine.
Andy

#### bplus

• Forum Resident
• Posts: 6858
• b = b + ...
##### Re: Circle Intersect Line
« Reply #4 on: February 01, 2020, 10:58:46 AM »
In my haste to do the Triangle Dissection, I did not finish the complete code version of Circle Intersect Line with 3 possible outcomes:
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.     IF testTangent = 0 THEN 'test plug in set of border conditions not easy to click
10.         PRINT "First set here is a plug in test set for vertical lines."
11.         mx(1) = 200: my(1) = 100: mx(2) = 200: my(2) = 400 'line  x = 200
12.         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
13.         FOR i = 1 TO 4
14.             CIRCLE (mx(i), my(i)), 2
15.         IF mx(1) <> mx(2) THEN
16.             slopeYintersect mx(1), my(1), mx(2), my(2), m, Y0 ' Y0 otherwise know as y Intersect
17.             LINE (0, Y0)-(xmax, m * xmax + Y0), &HFF0000FF
18.             LINE (mx(1), my(1))-(mx(2), my(2))
19.             LINE (mx(1), 0)-(mx(1), ymax), &HFF0000FF
20.             LINE (mx(1), my(1))-(mx(2), my(2))
21.         testTangent = 1
22.         PRINT "First 2 clicks will form a line, 3rd the circle origin and 4th the circle radius:"
23.         WHILE pi < 4 'get 4 mouse clicks
24.             _PRINTSTRING (20, 20), SPACE\$(20)
25.             _PRINTSTRING (20, 20), "Need 4 clicks, have" + STR\$(pi)
26.             IF _MOUSEBUTTON(1) AND oldMouse = 0 THEN 'new mouse down
27.                 pi = pi + 1
28.                 mx(pi) = _MOUSEX: my(pi) = _MOUSEY
29.                 CIRCLE (mx(pi), my(pi)), 2
30.                 IF pi = 2 THEN 'draw first line segment then line
31.                     IF mx(1) <> mx(2) THEN
32.                         slopeYintersect mx(1), my(1), mx(2), my(2), m, Y0 ' Y0 otherwise know as y Intersect
33.                         LINE (0, Y0)-(xmax, m * xmax + Y0), &HFF0000FF
34.                         LINE (mx(1), my(1))-(mx(2), my(2))
35.                         LINE (mx(1), 0)-(mx(1), ymax), &HFF0000FF
36.                         LINE (mx(1), my(1))-(mx(2), my(2))
37.             oldMouse = _MOUSEBUTTON(1)
38.             _LIMIT 60
39.     p = mx(3): q = my(3)
40.     r = SQR((mx(3) - mx(4)) ^ 2 + (my(3) - my(4)) ^ 2)
41.     CIRCLE (p, q), r, &HFFFF0000
42.     IF mx(1) = mx(2) THEN 'line is vertical so if r =
43.         IF r = ABS(mx(1) - mx(3)) THEN ' one point tangent intersect
44.             PRINT "Tangent point is "; TS\$(mx(1)); ", "; TS\$(my(3))
45.             CIRCLE (mx(1), my(3)), 2, &HFFFFFF00
46.             CIRCLE (mx(1), my(3)), 4, &HFFFFFF00
47.         ELSEIF r < ABS(mx(1) - mx(3)) THEN 'no intersect
48.             PRINT "No intersect, radius too small."
49.         ELSE '2 point intersect
50.             ydist = SQR(r ^ 2 - (mx(1) - mx(3)) ^ 2)
51.             y1 = my(3) + ydist
52.             y2 = my(3) - ydist
53.             PRINT "2 Point intersect (x1, y1) = "; TS\$(mx(1)); ", "; TS\$(y1); "  (x2, y2) = "; TS\$(mx(1)); ", "; TS\$(y2)
54.             CIRCLE (mx(1), y1), 2, &HFFFFFF00 'marking intersect points yellow
55.             CIRCLE (mx(1), y2), 2, &HFFFFFF00
56.             CIRCLE (mx(1), y1), 4, &HFFFFFF00 'marking intersect points yellow
57.             CIRCLE (mx(1), y2), 4, &HFFFFFF00
58.
59.         'OK the calculations!
60.         'from inserting eq ofline into eq of circle where line intersects circle see reference
61.         ' https://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
62.         A = m ^ 2 + 1
63.         B = 2 * (m * Y0 - m * q - p)
64.         C = q ^ 2 - r ^ 2 + p ^ 2 - 2 * Y0 * q + Y0 ^ 2
65.         D = B ^ 2 - 4 * A * C 'telling part of Quadratic formula = 0 then circle is tangent  or > 0 then 2 intersect points
66.         IF D < 0 THEN ' no intersection
67.             PRINT "m, y0 "; TS\$(m); ", "; TS\$(Y0)
68.             PRINT "(p, q) "; TS\$(p); ", "; TS\$(q)
69.             PRINT "A: "; TS\$(A)
70.             PRINT "B: "; TS\$(B)
71.             PRINT "C: "; TS\$(C)
72.             PRINT "D: "; TS\$(D); " negative so no intersect."
73.         ELSEIF D = 0 THEN ' one point tangent
74.             x1 = (-B + SQR(D)) / (2 * A)
75.             y1 = m * x1 + Y0
76.             PRINT "Tangent Point Intersect (x1, y1) = "; TS\$(x1); ", "; TS\$(y1)
77.             CIRCLE (x1, y1), 2, &HFFFFFF00 'yellow circle should be on line perprendicular to 3rd click point
78.             CIRCLE (x1, y1), 4, &HFFFFFF00 'yellow circle should be on line perprendicular to 3rd click point
79.             '2 points
80.             x1 = (-B + SQR(D)) / (2 * A): y1 = m * x1 + Y0
81.             x2 = (-B - SQR(D)) / (2 * A): y2 = m * x2 + Y0
82.             PRINT "2 Point intersect (x1, y1) = "; TS\$(x1); ", "; TS\$(y1); "  (x2, y2) = "; TS\$(x2); ", "; TS\$(y2)
83.             CIRCLE (x1, y1), 2, &HFFFFFF00 'marking intersect points yellow
84.             CIRCLE (x2, y2), 2, &HFFFFFF00
85.             CIRCLE (x1, y1), 4, &HFFFFFF00 'marking intersect points yellow
86.             CIRCLE (x2, y2), 4, &HFFFFFF00
87.     INPUT "press enter to continue, any + enter to quit "; q\$
88.     IF LEN(q\$) THEN SYSTEM
89.     pi = 0 'point index
90.
91. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) ' fix for when x1 = x2
92.     slope = (Y2 - Y1) / (X2 - X1)
93.     Yintercept = slope * (0 - X1) + Y1
94.
95. FUNCTION TS\$ (n)
96.     TS\$ = _TRIM\$(STR\$(n))
97.
98.
« Last Edit: February 01, 2020, 03:16:17 PM by bplus »

#### bplus

• Forum Resident
• Posts: 6858
• b = b + ...
##### Re: Circle Intersect Line
« Reply #5 on: February 01, 2020, 03:19:46 PM »
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.

Marked as best answer by bplus on March 06, 2020, 04:04:17 PM

#### bplus

• Forum Resident
• Posts: 6858
• b = b + ...
##### Re: Circle Intersect Line
« Reply #6 on: March 06, 2020, 02:00:10 PM »
@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.     WHILE pi < 3 'get 3 mouse clicks
13.         _PRINTSTRING (5, 5), SPACE\$(20)
14.         _PRINTSTRING (5, 5), "Need 3 clicks, have" + STR\$(pi)
15.         IF _MOUSEBUTTON(1) AND oldMouse = 0 THEN 'new mouse down
16.             pi = pi + 1
17.             mx(pi) = _MOUSEX: my(pi) = _MOUSEY
18.             CIRCLE (mx(pi), my(pi)), 2
19.             IF pi = 2 THEN 'draw first line segment then line
20.                 slopeYintersect mx(1), my(1), mx(2), my(2), m, Y0 ' Y0 otherwise know as y Intersect
21.                 LINE (0, Y0)-(xmax, m * xmax + Y0), &HFF0000FF
22.                 LINE (mx(1), my(1))-(mx(2), my(2))
23.         oldMouse = _MOUSEBUTTON(1)
24.         _LIMIT 60
25.
26.     '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
27.     ''from inserting eq of line into eq of circle where line intersects circle
28.     '' https://math.stackexchange.com/questions/228841/how-do-i-calculate-the-intersections-of-a-straight-line-and-a-circle
29.     'A = m ^ 2 + 1
30.     'B = 2 * (m * Y0 - m * q - p)
31.     ''C = q ^ 2 - r ^ 2 + p ^ 2 - 2 * Y0 * q + Y0 ^ 2   <<< don't need
32.     ''because r is rediculously large the line must intersect at two points likely beyond the screen limits
33.     ''but the middle of those two points is exactly the point we want
34.     ''D = B ^ 2 - 4 * A * C
35.     'IF D < 0 THEN
36.     '    LOCATE 5, 1
37.     '    PRINT "m, y0"; m; ","; Y0
38.     '    PRINT "(p, q)"; p; ","; q
39.     '    PRINT "A:"; A
40.     '    PRINT "B:"; B
41.     '    'PRINT "C:"; C
42.     '    'PRINT "D:"; D
43.
44.     '    BEEP
45.     'ELSE
46.     '    'here is our point!
47.     '    x = -B / (2 * A)
48.     '    y = m * x + Y0
49.     '    PRINT "answer (x, y) = "; x, y
50.     '    CIRCLE (x, y), 2, &HFFFFFF00 'yellow circle should be on line perprendicular to 3rd click point
51.     '    LINE (p, q)-(x, y), &HFFFFFF00
52.     'END IF
53.
54.
55.     'test new sub
56.     PointOnLinePerp2Point mx(1), my(1), mx(2), my(2), mx(3), my(3), Rx, Ry
57.     PRINT "answer (x, y) = "; Rx, Ry
58.     CIRCLE (Rx, Ry), 2, &HFFFFFF00 'yellow circle should be on line perprendicular to 3rd click point
59.     LINE (mx(3), my(3))-(Rx, Ry), &HFFFFFF00
60.
61.     INPUT "press enter to continue, any + enter to quit "; q\$
62.     IF LEN(q\$) THEN SYSTEM
63.     pi = 0 'point index
64.
65. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) ' fix for when x1 = x2
66.     IF X1 = X2 THEN
67.         slope = X1
68.         Yintercept = Y2
69.         slope = (Y2 - Y1) / (X2 - X1)
70.         Yintercept = slope * (0 - X1) + Y1
71.
72. SUB PointOnLinePerp2Point (Lx1, Ly1, Lx2, Ly2, Px, Py, Rx, Ry)
73.     '
74.     'this sub needs  SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) ' fix for when x1 = x2
75.     '
76.     'Lx1, Ly1, Lx2, Ly2     the two points that make a line
77.     'Px, Py is point off the line
78.     'Rx, Ry Return Point is the Point on the line perpendicular to Px, Py
79.     slopeYintersect Lx1, Ly1, Lx2, Ly2, m, Y0
80.     A = m ^ 2 + 1
81.     B = 2 * (m * Y0 - m * Py - Px)
82.     Rx = -B / (2 * A)
83.     Ry = m * Rx + Y0
84.
85.

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

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
« Last Edit: March 06, 2020, 04:28:33 PM by bplus »

#### STxAxTIC

• Library Staff
• Forum Resident
• Posts: 1062
• TOXIC
##### Re: Circle Intersect Line
« Reply #7 on: March 06, 2020, 02:05:30 PM »
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.
TOXIC