Intersect of 2 lines carried a step further

[bplus]

I saw this challenge at Rosetta Code and solved here:

Code: QB64: [Select]

1. _TITLE "lineIntersectLine" 'b+ 2020-03-14 Rosetta Code
2. '  http://rosettacode.org/wiki/Find_the_intersection_of_two_lines
3. ' This code also tells when there is no intersect between lines handling special case of vertical lines.
4.  
5. PRINT "Test normal intersect:"
6. PRINT " Line on (4, 0) and (6, 10) intersect line on (0, 3) and (10, 7)"
7. intersect = lineIntersectLine(4, 0, 6, 10, 0, 3, 10, 7, answX, answY) ' answer should be (5 , 5)
8. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
9. PRINT
10. PRINT "Test intersect line with 1st line vertical:"
11. PRINT " Line on (10, 0) and (10, 20) intersect line on (0, 20) and (20, 10)"
12. intersect = lineIntersectLine%(10, 0, 10, 20, 0, 20, 20, 10, answX, answY) 'intersect should be (10 , 15)
13. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
14. PRINT
15. PRINT "Test intersect with 2nd line vertical:"
16. PRINT " Line on (0, 20) and (20, 10) intersect line on (10, 0) and (10, 5)"
17. intersect = lineIntersectLine%(0, 20, 20, 10, 10, 0, 10, 5, answX, answY) 'intersect should be (10 , 15)
18. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
19. PRINT
20. PRINT "Test intersect with both lines vertical:"
21. PRINT " Line on (0, 20) and (0, 10) intersect line on (10, 0) and (10, 5)"
22. intersect = lineIntersectLine%(0, 20, 0, 10, 10, 0, 10, 5, answX, answY) 'intersect should be none
23. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
24. SLEEP
25.  
26. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
27. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
28.     IF ax1 = ax2 THEN 'line a is vertical
29.         IF bx1 = bx2 THEN
30.             EXIT FUNCTION 'no intersect
31.         ELSE
32.             ix = ax1
33.             slopeYintersect bx1, by1, bx2, by2, m2, y02
34.             iy = m2 * ix + y02
35.             lineIntersectLine% = -1 'signal a point was found
36.             EXIT FUNCTION
37.         END IF
38.     ELSE
39.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
40.     END IF
41.     IF bx1 = bx2 THEN 'b is vertical
42.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = -1 'signal a point was found
43.         EXIT FUNCTION
44.     ELSE
45.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
46.     END IF
47.     d = -m1 - -m2 ' if = 0 then parallel because slopes are same
48.     IF d THEN ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
49.     lineIntersectLine% = -1 'signal a point was found
50. END FUNCTION
51.  
52. 'Slope and Y-intersect for non vertical lines,
53. ' if x1 = x2 the line is vertical don't call this sub
54. ' because slope calculation would cause division by 0 error.
55. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
56.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
57. END SUB
58.  
59. FUNCTION ts$ (n)
60.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
61. END FUNCTION
62.  
63.  

And then took it a step further by finding the intersect of two line segments if there is one:

Code: QB64: [Select]

1. _TITLE "Two Line Segments Intersect" 'b+ 2020-03-14
2. ' Just worked Rosetta Code for Line Intersect Line
3. ' but what if we want to know if two line segments intersect?
4. CONST xmax = 800, ymax = 600
5. SCREEN _NEWIMAGE(xmax, ymax, 32)
6. _DELAY .25
7. _SCREENMOVE _MIDDLE
8. DO
9.     ax1 = xmax * RND: ay1 = ymax * RND
10.     ax2 = xmax * RND: ay2 = ymax * RND
11.     bx1 = xmax * RND: by1 = ymax * RND
12.     bx2 = xmax * RND: by2 = ymax * RND
13.     LINE (ax1, ay1)-(ax2, ay2), &HFFFF0000
14.     LINE (bx1, by1)-(bx2, by2), &HFF0000FF
15.     PRINT "Segments ("; ts$(ax1); ", "; ts$(ay1); ") ("; ts$(ax2); ", ";_
16.      ts$(ay2); ") and ("; ts$(bx1); ", "; ts$(by1); ") ("; ts$(bx2); ", "; ts$(by2); ")"
17.     intersect = twoLineSegmentsIntersect%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
18.     IF intersect THEN
19.         PRINT " intersect at ("; ts$(ix); ", "; ts$(iy); ")."
20.         CIRCLE (ix, iy), 3, &HFFFFFF00
21.     ELSE
22.         PRINT "Do not Intersect."
23.     END IF
24.     INPUT "Press enter for another demo, any + enter to quit...", again$
25.     CLS
26. LOOP UNTIL LEN(again$)
27.  
28. 'This function needs: FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
29. ' which in turn needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
30. FUNCTION twoLineSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
31.     intersect = lineIntersectLine%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
32.     IF intersect THEN 'ok we know the lines  intersect
33.         IF ax1 < ax2 THEN aMinX = ax1: aMaxX = ax2 ELSE aMinX = ax2: aMaxX = ax1
34.         IF bx1 < bx2 THEN bMinX = bx1: bMaxX = bx2 ELSE bMinX = bx2: bMaxX = bx1
35.         IF (aMinX <= ix AND ix <= aMaxX) AND (bMinX <= ix AND ix <= bMaxX) THEN
36.             twoLineSegmentsIntersect% = -1
37.         END IF
38.     END IF
39. END FUNCTION
40.  
41. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
42. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
43.     IF ax1 = ax2 THEN 'line a is vertical
44.         IF bx1 = bx2 THEN
45.             EXIT FUNCTION 'no intersect
46.         ELSE
47.             ix = ax1
48.             slopeYintersect bx1, by1, bx2, by2, m2, y02
49.             iy = m2 * ix + y02
50.             lineIntersectLine% = -1 'signal a point was found
51.             EXIT FUNCTION
52.         END IF
53.     ELSE
54.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
55.     END IF
56.     IF bx1 = bx2 THEN 'b is vertical
57.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = -1 'signal a point was found
58.         EXIT FUNCTION
59.     ELSE
60.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
61.     END IF
62.     d = -m1 - -m2 ' if = 0 then parallel because slopes are same
63.     IF d THEN ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
64.     lineIntersectLine% = -1 'signal a point was found
65. END FUNCTION
66.  
67. 'Slope and Y-intersect for non vertical lines,
68. ' if x1 = x2 the line is vertical don't call this sub
69. ' because slope calculation would cause division by 0 error.
70. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
71.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
72. END SUB
73.  
74. FUNCTION ts$ (n)
75.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
76. END FUNCTION
77.  
78.  

[TempodiBasic]

Hi Bplus
I like very much all your energy....and I have difficult to follow your posts.

In the intersecting test of two line I think it is useful also in a graphic tool or in a game...
and looking at your code it seems you don't manage if the two segment are overlapped... so I test your code
and it seems to be so-

Code: QB64: [Select]

1. _TITLE "lineIntersectLine" 'b+ 2020-03-14 Rosetta Code
2. '  http://rosettacode.org/wiki/Find_the_intersection_of_two_lines
3. ' This code also tells when there is no intersect between lines handling special case of vertical lines.
4.  
5. PRINT "Test normal intersect:"
6. PRINT " Line on (4, 0) and (6, 10) intersect line on (0, 3) and (10, 7)"
7. intersect = lineIntersectLine(4, 0, 6, 10, 0, 3, 10, 7, answX, answY) ' answer should be (5 , 5)
8. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
9. PRINT
10. PRINT "Test intersect line with 1st line vertical:"
11. PRINT " Line on (10, 0) and (10, 20) intersect line on (0, 20) and (20, 10)"
12. intersect = lineIntersectLine%(10, 0, 10, 20, 0, 20, 20, 10, answX, answY) 'intersect should be (10 , 15)
13. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
14. PRINT
15. PRINT "Test intersect with 2nd line vertical:"
16. PRINT " Line on (0, 20) and (20, 10) intersect line on (10, 0) and (10, 5)"
17. intersect = lineIntersectLine%(0, 20, 20, 10, 10, 0, 10, 5, answX, answY) 'intersect should be (10 , 15)
18. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
19. PRINT
20. PRINT "Test intersect with both lines vertical:"
21. PRINT " Line on (0, 20) and (0, 10) intersect line on (10, 0) and (10, 5)"
22. intersect = lineIntersectLine%(0, 20, 0, 10, 10, 0, 10, 5, answX, answY) 'intersect should be none
23. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
24. PRINT "overlapping test TdB"
25. PRINT " Line on (4, 0) and (6, 10) intersect line on (4, 0) and (6,10)"
26. intersect = lineIntersectLine(4, 0, 6, 10, 4, 0, 6, 10, answX, answY) ' answer should be (5 , 5)
27. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
28.  
29. SLEEP
30.  
31. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
32. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
33.     IF ax1 = ax2 THEN 'line a is vertical
34.         IF bx1 = bx2 THEN
35.             EXIT FUNCTION 'no intersect
36.         ELSE
37.             ix = ax1
38.             slopeYintersect bx1, by1, bx2, by2, m2, y02
39.             iy = m2 * ix + y02
40.             lineIntersectLine% = -1 'signal a point was found
41.             EXIT FUNCTION
42.         END IF
43.     ELSE
44.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
45.     END IF
46.     IF bx1 = bx2 THEN 'b is vertical
47.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = -1 'signal a point was found
48.         EXIT FUNCTION
49.     ELSE
50.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
51.     END IF
52.     d = -m1 - -m2 ' if = 0 then parallel because slopes are same
53.     IF d THEN ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
54.     lineIntersectLine% = -1 'signal a point was found
55. END FUNCTION
56.  
57. 'Slope and Y-intersect for non vertical lines,
58. ' if x1 = x2 the line is vertical don't call this sub
59. ' because slope calculation would cause division by 0 error.
60. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
61.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
62. END SUB
63.  
64. FUNCTION ts$ (n)
65.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
66. END FUNCTION
67.  

Waiting your thoughts

[bplus]

OK I guess I did miss the case where lines (and segments) might overlap and be on the same line.

Thanks for your interest :)

[TempodiBasic]

Thanks to share your works, your time, your interests!
In our eucledian geometry, two segments can  share  no point, one point and all points ....so in an universal application of your function I have thought that this rare case (overlapping) may  be included. But it is a my thought. :-)

[bplus]

OK here is the first part of code testing for intersecting lines, corrected with TempodiBasic's test case:
There are 3 results returned now as noted in comments section of code.

Code: QB64: [Select]

1. _TITLE "lineIntersectLine" 'b+ 2020-03-14 Rosetta Code
2. '  http://rosettacode.org/wiki/Find_the_intersection_of_two_lines
3. ' This code also tells when there is no intersect between lines handling special case of vertical lines.
4.  
5. ' 2020-03-15 overhaul this code to handle the case that all the points are on the same line.
6. ' Return -1, if all points are on the same line
7. ' Return 0, if no intersect
8. ' Return 1, if the intersect is a single point (lines cross).
9.  
10. PRINT "Test normal intersect: answ should be: (5, 5)"
11. printResultOfLineIntersectLine 4, 0, 6, 10, 0, 3, 10, 7
12. PRINT
13. PRINT "Test intersect line with 1st line vertical: answ should be: (10, 15)"
14. printResultOfLineIntersectLine 10, 0, 10, 20, 0, 20, 20, 10
15. PRINT
16. PRINT "Test intersect with 2nd line vertical: answ should be: (10, 15) again."
17. printResultOfLineIntersectLine 0, 20, 20, 10, 10, 0, 10, 5
18. PRINT
19. PRINT "Test intersect with both lines vertical: answ should be: No intersect."
20. printResultOfLineIntersectLine 0, 20, 0, 10, 10, 0, 10, 5
21. PRINT
22. PRINT "TempodiBasic test, 4 points on same line, try 2 vertical lines, same points:"
23. PRINT "Answer should be: Lines are the same."
24. printResultOfLineIntersectLine 5, 10, 5, 20, 5, 10, 5, 20
25. PRINT
26. PRINT "Test points off same sloped line: answ should be: Lines are the same."
27. printResultOfLineIntersectLine 2, 4, 6, 12, 10, 20, 15, 30
28. SLEEP
29.  
30. SUB printResultOfLineIntersectLine (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
31.     PRINT "Lines on ("; ts$(ax1); ", "; ts$(ay1); ") ("; ts$(ax2); ", ";_
32.      ts$(ay2); ") and ("; ts$(bx1); ", "; ts$(by1); ") ("; ts$(bx2); ", "; ts$(by2); ")"
33.     intersect = lineIntersectLine%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, answX, answY)
34.     IF intersect = 0 THEN
35.         PRINT "No intersection."
36.     ELSEIF intersect = -1 THEN
37.         PRINT "Lines are the same."
38.     ELSEIF intersect = 1 THEN
39.         PRINT "Lines intersect at ("; ts$(answX); ", "; ts$(answY); ")"
40.     END IF
41. END SUB
42.  
43. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
44. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
45.     IF ax1 = ax2 THEN 'line a is vertical
46.         IF bx1 = bx2 THEN ' b is vertical
47.             IF ax1 = bx1 THEN lineIntersectLine% = -1 ' if x's are same it is same vertical line
48.             EXIT FUNCTION '
49.         ELSE
50.             ix = ax1
51.             slopeYintersect bx1, by1, bx2, by2, m2, y02
52.             iy = m2 * ix + y02
53.             lineIntersectLine% = 1 'signal a point was found
54.             EXIT FUNCTION
55.         END IF
56.     ELSE
57.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
58.     END IF
59.     IF bx1 = bx2 THEN 'b is vertical
60.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = 1 'signal a point was found
61.         EXIT FUNCTION
62.     ELSE
63.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
64.     END IF
65.     d = -m1 - -m2 ' if = 0 then parallel or equal because slopes are same
66.     IF d <> 0 THEN
67.         ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
68.         lineIntersectLine% = 1 'signal one intersect point was found
69.     ELSE 'same line or parallel? if y0 are same they are the same
70.         IF y01 = y02 THEN lineIntersectLine% = -1 'signal same line!
71.     END IF
72. END FUNCTION
73.  
74. 'Slope and Y-intersect for non vertical lines,
75. ' if x1 = x2 the line is vertical don't call this sub
76. ' because slope calculation would cause division by 0 error.
77. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
78.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
79. END SUB
80.  
81. FUNCTION ts$ (n)
82.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
83. END FUNCTION
84.  
85.  

[TempodiBasic]

Great Bplus
as always  you're fast, rapid and accurate!

[bplus]

Thanks, that was a good catch TempodiBasic. I will likely have the line segments code reworked this afternoon.

[bplus]

Well doing overlapping Line Segments turned out to be a bear, lots of vertical line tests because tricky case:

Code: QB64: [Select]

1. _TITLE "Two Line Segments Intersect" 'b+ 2020-03-14
2. ' Just worked Rosetta Code for Line Intersect Line
3. ' but what if we want to know if two line segments intersect?
4.  
5. '2020-03-15 rework this code so we identify points all on same line and
6. ' if there is overlap of line segments say the two x endpoints of the segments
7. ' otherwise, if there is an intersect of 2 line segments say the point x, y.
8. ' Return 0 no intersect or overlap
9. ' Return 1 if intersect and ix, iy point of intersect
10. ' Return -1 if segments are on same and there is overlap: ix = overlap start x, iy overlap end x
11.  
12. CONST xmax = 1200, ymax = 700
13. SCREEN _NEWIMAGE(xmax, ymax, 32)
14. _DELAY .25
15. _SCREENMOVE _MIDDLE
16. DIM ax1 AS INTEGER, ax2 AS INTEGER, ay1 AS INTEGER, ay2 AS INTEGER
17. DIM bx1 AS INTEGER, bx2 AS INTEGER, by1 AS INTEGER, by2 AS INTEGER
18. DO
19.     restartA:
20.     CLS
21.     IF RND < .5 THEN 'throw in some vertical lines
22.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
23.         ax2 = ax1: ay2 = (ymax - 60) * RND + 50
24.     ELSE
25.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
26.         ax2 = (xmax - 20) * RND + 10: ay2 = (ymax - 60) * RND + 50
27.     END IF
28.     IF _HYPOT(ax1 - ax2, ay1 - ay2) < 50 THEN GOTO restartA
29.  
30.     IF RND < .5 THEN 'get some points on same line
31.         LOCATE 3, 80: PRINT "Blue Points are on same line as Red."
32.         slopeYintersect ax1, ay1, ax2, ay2, slope1, Yintercept1
33.         bx1 = (xmax - 20) * RND + 10: by1 = bx1 * slope1 + Yintercept1
34.         bx2 = (xmax - 20) * RND + 10: by2 = bx2 * slope1 + Yintercept1
35.     ELSE
36.         IF RND < .5 THEN 'throw in some verticals
37.             bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 60) * RND + 50
38.             bx2 = bx1: by2 = (ymax - 60) * RND + 50
39.         ELSE
40.             bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 60) * RND + 50
41.             bx2 = (xmax - 20) * RND + 10: by2 = (ymax - 60) * RND + 50
42.         END IF
43.     END IF
44.     IF bx1 < 10 OR bx1 > xmax - 10 THEN GOTO restartA
45.     IF bx2 < 10 OR bx2 > xmax - 10 THEN GOTO restartA
46.     IF by1 < 50 OR by1 > ymax - 10 THEN GOTO restartA
47.     IF by2 < 50 OR by2 > ymax - 10 THEN GOTO restartA
48.     IF _HYPOT(bx1 - bx2, by1 - by2) < 50 THEN GOTO restartA
49.  
50.     LINE (ax1, ay1)-(ax2, ay2), &HFFFF0000
51.     CIRCLE (ax1, ay1), 4, &HFFFF0000
52.     CIRCLE (ax2, ay2), 4, &HFFFF0000
53.  
54.     LINE (bx1, by1)-(bx2, by2), &HFF0000FF
55.     CIRCLE (bx1, by1), 4, &HFF0000FF
56.     CIRCLE (bx2, by2), 4, &HFF0000FF
57.  
58.     LOCATE 1, 1
59.     PRINT "Segments ("; ts$(ax1); ", "; ts$(ay1); ") ("; ts$(ax2); ", ";_
60.      ts$(ay2); ") and ("; ts$(bx1); ", "; ts$(by1); ") ("; ts$(bx2); ", "; ts$(by2); ")"
61.     intersect = twoLineSegmentsIntersect%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
62.     IF intersect = -1 THEN
63.         PRINT " Segments overlap between min x at "; ts$(ix); " and max x at "; ts$(iy) '< not a "y" here
64.         LINE (ix, 0)-(iy, ymax), &H22FFFF00, BF
65.     ELSEIF intersect = 1 THEN
66.         PRINT " Segments intersect at ("; ts$(ix); ", "; ts$(iy); ")."
67.         CIRCLE (ix, iy), 3, &HFFFFFF00
68.     ELSEIF intersect = 0 THEN
69.         PRINT " Segments do not Intersect or Overlap."
70.     END IF
71.     INPUT "Press enter for another demo, any + enter to quit...", again$
72.     CLS
73. LOOP UNTIL LEN(again$)
74.  
75. 'This function needs: FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
76. ' which in turn needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
77. FUNCTION twoLineSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
78.     intersect = lineIntersectLine%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
79.     IF ax1 < ax2 THEN aMinX = ax1: aMaxX = ax2 ELSE aMinX = ax2: aMaxX = ax1
80.     IF ay1 < ay2 THEN aMinY = ay1: aMaxY = ay2 ELSE aMinY = ay2: aMaxY = ay1
81.     IF bx1 < bx2 THEN bMinX = bx1: bMaxX = bx2 ELSE bMinX = bx2: bMaxX = bx1
82.     IF by1 < by2 THEN bMinY = by1: bMaxY = by2 ELSE bMinY = by2: bMaxY = by1
83.     IF intersect = 0 THEN 'no  intersect
84.         twoLineSegmentsIntersect% = 0
85.     ELSEIF intersect = 1 THEN
86.         IF ax1 = ax2 THEN 'is iy between
87.             IF iy < aMinY OR iy > aMaxY OR ix < bMinX OR ix > bMaxX THEN twoLineSegmentsIntersect% = 0 ELSE twoLineSegmentsIntersect% = 1
88.         ELSEIF bx1 = bx2 THEN
89.             IF iy < bMinY OR iy > bMaxY OR ix < aMinX OR ix > aMaxX THEN twoLineSegmentsIntersect% = 0 ELSE twoLineSegmentsIntersect% = 1
90.         ELSE
91.             IF (aMinX <= ix AND ix <= aMaxX) AND (bMinX <= ix AND ix <= bMaxX) THEN twoLineSegmentsIntersect% = 1 ELSE twoLineSegmentsIntersect% = 0
92.         END IF
93.     ELSEIF intersect = -1 THEN 'segments are on same line get over lap section
94.         IF aMinX < bMinX THEN
95.             IF aMaxX < bMinX THEN
96.                 twoLineSegmentsIntersect% = 0
97.             ELSE
98.                 twoLineSegmentsIntersect% = -1
99.                 ix = bMinX
100.                 IF aMaxX > bMaxX THEN iy = bMaxX ELSE iy = aMaxX
101.             END IF
102.         ELSE 'aMinX >= bMinX
103.             IF aMinX > bMaxX THEN
104.                 twoLineSegmentsIntersect% = 0
105.             ELSE
106.                 twoLineSegmentsIntersect% = -1
107.                 ix = aMinX
108.                 IF bMaxX > aMaxX THEN iy = aMaxX ELSE iy = bMaxX
109.             END IF
110.         END IF
111.     END IF
112. END FUNCTION
113.  
114. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
115. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
116.     IF ax1 = ax2 THEN 'line a is vertical
117.         IF bx1 = bx2 THEN ' b is vertical
118.             IF ax1 = bx1 THEN lineIntersectLine% = -1 ' if x's are same it is same vertical line
119.             EXIT FUNCTION '
120.         ELSE
121.             ix = ax1
122.             slopeYintersect bx1, by1, bx2, by2, m2, y02
123.             iy = m2 * ix + y02
124.             lineIntersectLine% = 1 'signal a point was found
125.             EXIT FUNCTION
126.         END IF
127.     ELSE
128.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
129.     END IF
130.     IF bx1 = bx2 THEN 'b is vertical
131.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = 1 'signal a point was found
132.         EXIT FUNCTION
133.     ELSE
134.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
135.     END IF
136.     d = -m1 - -m2 ' if = 0 then parallel or equal because slopes are same
137.     IF ABS(d) > .2 THEN 'otherwise about 0
138.         ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
139.         lineIntersectLine% = 1 'signal one intersect point was found
140.     ELSE 'same line or parallel? if y0 are same they are the same
141.         IF ABS(y01 - y02) < 5 THEN lineIntersectLine% = -1 'signal same line!
142.     END IF
143. END FUNCTION
144.  
145. 'Slope and Y-intersect for non vertical lines,
146. ' if x1 = x2 the line is vertical don't call this sub
147. ' because slope calculation would cause division by 0 error.
148. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
149.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
150. END SUB
151.  
152. FUNCTION ts$ (n)
153.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
154. END FUNCTION
155.  
156.  

Thanks to round-off errors (I think), it misses overlapping segments on occasion.

[EricE]

Here is a solution for the case when the two lines intersect at one point.
The code uses the parametric representation of lines.

Code: QB64: [Select]

1. PRINT "Test normal intersect:"
2. PRINT " Line on (4, 0) and (6, 10) intersect line on (0, 3) and (10, 7)"
3.  
4. ' A(x1, y1), B(x2, y2),
5. ' C(x3, y3), D(x4, y4)
6.  
7. DIM A(1 TO 2) AS DOUBLE
8. DIM B(1 TO 2) AS DOUBLE
9. DIM C(1 TO 2) AS DOUBLE
10. DIM D(1 TO 2) AS DOUBLE
11. DIM v1(1 TO 2) AS DOUBLE
12. DIM v2(1 TO 2) AS DOUBLE
13.  
14. DIM DetV AS DOUBLE
15. DIM invV(1 TO 2, 1 TO 2) AS DOUBLE
16. DIM r AS DOUBLE, s AS DOUBLE
17.  
18. ' Intersection point
19. DIM Xr(1 TO 2) AS DOUBLE
20. DIM Xs(1 TO 2) AS DOUBLE
21.  
22. ' Test Example
23. A(1) = 4.0
24. A(2) = 0.0
25. B(1) = 6.0
26. B(2) = 10.0
27. '---
28. C(1) = 0.0
29. C(2) = 3.0
30. D(1) = 10.0
31. D(2) = 7.0
32.  
33. ' directed segment AB
34. v1(1) = B(1) - A(1)
35. v1(2) = B(2) - A(2)
36.  
37. ' directed segment CD
38. v2(1) = D(1) - C(1)
39. v2(2) = D(2) - C(2)
40.  
41. ' Parametric line equations
42. '          Xr = A + v1*r
43. '          Xs = C + v2*s
44. '
45. ' Line intersection criteria
46. '    A + v1*r = C + v2*s
47. ' Determine scalars r, s
48. '
49. ' Matrix equation
50. '         A-C = [-v1, v2]*[r, s]^t
51. ' Define    V = [-v1, v2]
52. '        invV = V^-1
53. '    [r, s]^t = invV*(A - C)
54.  
55. ' Calculate invV([-v1, v2])
56. '
57. ' Compute determinant
58. DetV = -v1(1) * v2(2) + v2(1) * v1(2)
59. ' DetV must not be zero
60.  
61. invV(1, 1) = v2(2) / DetV
62. invV(2, 1) = v1(2) / DetV
63. invV(1, 2) = -v2(1) / DetV
64. invV(2, 2) = -v1(1) / DetV
65.  
66. r = invV(1, 1) * (A(1) - C(1)) + invV(1, 2) * (A(2) - C(2))
67. s = invV(2, 1) * (A(1) - C(1)) + invV(2, 2) * (A(2) - C(2))
68.  
69. ' Intersection point
70. Xr(1) = A(1) + r * v1(1)
71. Xr(2) = A(2) + r * v1(2)
72.  
73. Xs(1) = C(1) + s * v2(1)
74. Xs(2) = C(2) + s * v2(2)
75.  
76. PRINT "Intersection Point:"
77. ' (Xr(1), Xr(2)) and (Xs(1), Xs(2)) are the coordinates of the same point
78. PRINT Xr(1), Xr(2)
79. PRINT Xs(1), Xs(2)
80.  
81.  
82.  

[TerryRitchie]

When creating the vector engine for Widescreen Asteroids I wrote routines to detect line intersection. Here they are if you wish to use any of the code from them. It detects line intersection as well as the lines being collinear.

Plug the values into ObjIntersect() and it will return either -1 (TRUE) or 0 (FALSE)

Code: QB64: [Select]

1.  
2. TYPE POINTTYPE '                            X,Y point with integer precision
3.     x AS INTEGER
4.     y AS INTEGER
5. END TYPE
6.  
7.  
8. '**********************************************************************************************************************
9. FUNCTION ObjIntersect (p1x AS INTEGER, p1y AS INTEGER, q1x AS INTEGER, q1y AS INTEGER, p2x AS INTEGER, p2y AS INTEGER, q2x AS INTEGER, q2y AS INTEGER) ' OBJINTERSECT
10.     '******************************************************************************************************************
11.     '* Returns TRUE if line segments p1q1 and p2q2 intersect.                    *
12.     '*                                                                           *
13.     '* p1x,p1y - starting X,Y coordinates of segment 1                           *
14.     '* q1x,q1y -   ending X,Y coordinates of segment 1                           *
15.     '* p2x,p2y - starting X,Y coordinates of segment 2                           *
16.     '* q2x,q2y -   ending X,Y coordinates of segment 2                           *
17.     '*                                                                           *
18.     '* This function was created from example code found at:                     *
19.     '* https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ *
20.     '*****************************************************************************
21.  
22.     DIM p1 AS POINTTYPE ' line 1 coordinate X,Y pairs
23.     DIM q1 AS POINTTYPE
24.     DIM p2 AS POINTTYPE ' line 2 coordinate X,Y pairs
25.     DIM q2 AS POINTTYPE
26.     DIM o1 AS INTEGER '   four orientations
27.     DIM o2 AS INTEGER
28.     DIM o3 AS INTEGER
29.     DIM o4 AS INTEGER
30.  
31.     p1.x = p1x: p1.y = p1y '            line 1 start X,Y
32.     q1.x = q1x: q1.y = q1y '            line 1   end X,Y
33.     p2.x = p2x: p2.y = p2y '            line 2 start X,Y
34.     q2.x = q2x: q2.y = q2y '            line 2   end X,Y
35.     o1 = Orientation(p1, q1, p2) '      get the four orientations needed for general and special cases
36.     o2 = Orientation(p1, q1, q2)
37.     o3 = Orientation(p2, q2, p1)
38.     o4 = Orientation(p2, q2, q1)
39.     IF o1 <> o2 THEN
40.         IF o3 <> o4 THEN '              general case
41.             ObjIntersect = -1
42.             EXIT FUNCTION
43.         END IF
44.     END IF
45.     IF o1 = 0 THEN
46.         IF onSegment(p1, p2, q1) THEN ' p1, q1, and p2 are colinear and p2 lies on segment p1q1
47.             ObjIntersect = -1
48.             EXIT FUNCTION
49.         END IF
50.     END IF
51.     IF o2 = 0 THEN
52.         IF onSegment(p1, q2, q1) THEN ' p1, q1, and q2 are colinear and q2 lies on segment p1q1
53.             ObjIntersect = -1
54.             EXIT FUNCTION
55.         END IF
56.     END IF
57.     IF o3 = 0 THEN
58.         IF onSegment(p2, p1, q2) THEN ' p2, q2, and p1 are colinear and p1 lies on segment p2q2
59.             ObjIntersect = -1
60.             EXIT FUNCTION
61.         END IF
62.     END IF
63.     IF o4 = 0 THEN
64.         IF onSegment(p2, q1, q2) THEN ' p2, q2, and q1 are colinear and q1 lies on segment p2q2
65.             ObjIntersect = -1
66.             EXIT FUNCTION
67.         END IF
68.     END IF
69.     ObjIntersect = 0 '                  doesn't fall into any of the above cases
70.  
71. END FUNCTION
72.  
73.  
74. '**********************************************************************************************************************
75. FUNCTION Orientation (p AS POINTTYPE, q AS POINTTYPE, r AS POINTTYPE) '                                     ORIENTATION
76.     '******************************************************************************************************************
77.     '* Returns the orientation of ordered triplet p, q, r.                       *
78.     '* 0 = p, q, r are colinear                                                  *
79.     '* 1 = clockwise orientation                                                 *
80.     '* 2 = counter clockwise orientation                                         *
81.     '*                                                                           *
82.     '* This function was created from example code found at:                     *
83.     '* https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/ *
84.     '* (FOR INTERNAL USE ONLY)                                                   *
85.     '*****************************************************************************
86.  
87.     DIM Value AS INTEGER ' triplet orientation
88.  
89.     Value = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y) ' calculate orientation
90.     IF Value = 0 THEN '                                             colinear
91.         Orientation = 0
92.     ELSEIF Value > 0 THEN '                                         clockwise
93.         Orientation = 1
94.     ELSE '                                                          counter clockwise
95.         Orientation = 2
96.     END IF
97.  
98. END FUNCTION
99.  
100.  
101. '**********************************************************************************************************************
102. FUNCTION onSegment (p AS POINTTYPE, q AS POINTTYPE, r AS POINTTYPE) '                                         ONSEGMENT
103.     '******************************************************************************************************************
104.     '* Given 3 colinear points p, q, r, the function checks if point q lies on line segment pr. *
105.     '*                                                                                          *
106.     '* p, q, r - three colinear X,Y points                                                      *
107.     '*                                                                                          *
108.     '* This function was created from example code found at:                                    *
109.     '* https://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/                *
110.     '* (FOR INTERNAL USE ONLY)                                                                  *
111.     '********************************************************************************************
112.  
113.     IF q.x <= ObjMax(p.x, r.x) THEN
114.         IF q.x >= ObjMin(p.x, r.x) THEN
115.             IF q.y <= ObjMax(p.y, r.y) THEN
116.                 IF q.y >= ObjMin(p.y, r.y) THEN
117.                     onSegment = -1
118.                 END IF
119.             END IF
120.         END IF
121.     END IF
122.  
123. END FUNCTION
124.  
125.  
126. '**********************************************************************************************************************
127. FUNCTION ObjMax (n1 AS INTEGER, n2 AS INTEGER) '                                                                 OBJMAX
128.     '******************************************************************************************************************
129.     '* Returns the maximum of two numbers provided. *
130.     '*                                              *
131.     '* n1, n2 - the numbers to be compared          *
132.     '************************************************
133.  
134.     IF n1 > n2 THEN ObjMax = n1 ELSE ObjMax = n2 ' return largest number
135.  
136. END FUNCTION
137.  
138.  
139. '**********************************************************************************************************************
140. FUNCTION ObjMin (n1 AS INTEGER, n2 AS INTEGER) '                                                                 OBJMIN
141.     '******************************************************************************************************************
142.     '* Returns the minimum of two numbers provided. *
143.     '*                                              *
144.     '* n1, n2 - the numbers to be compared          *
145.     '************************************************
146.  
147.     IF n1 < n2 THEN ObjMin = n1 ELSE ObjMin = n2 ' return smallest number
148.  
149. END FUNCTION
150.  

[bplus]

Are you guys Erik and Terry talking about lines or line segments?

Lines are pretty easy, line segments are harder particularly finding the overlap zone of two segments on same line.

BTW my goal originally was to find an alternate way to determine if a triangle overlaps another by outlining the overlap area with intersect points again extending a Rosetta Code challenge from a yes/no answer to a visual representation of the overlap area.


Here is test code, see how your routines hold up ;-))

Code: QB64: [Select]

1. _TITLE "Two Line Segments Intersect" 'b+ 2020-03-14
2. ' Just worked Rosetta Code for Line Intersect Line
3. ' but what if we want to know if two line segments intersect?
4.  
5. '2020-03-15 rework this code so we identify points all on same line and
6. ' if there is overlap of line segments say the two x endpoints of the segments
7. ' otherwise, if there is an intersect of 2 line segments say the point x, y.
8. ' Return 0 no intersect or overlap
9. ' Return 1 if intersect and ix, iy point of intersect
10. ' Return -1 if segments are on same and there is overlap: ix = overlap start x, iy overlap end x
11.  
12. CONST xmax = 1200, ymax = 700
13. SCREEN _NEWIMAGE(xmax, ymax, 32)
14. _DELAY .25
15. _SCREENMOVE _MIDDLE
16. DIM ax1 AS INTEGER, ax2 AS INTEGER, ay1 AS INTEGER, ay2 AS INTEGER
17. DIM bx1 AS INTEGER, bx2 AS INTEGER, by1 AS INTEGER, by2 AS INTEGER
18. DO
19.     restartA:
20.     CLS
21.     IF RND < .5 THEN 'throw in some vertical lines
22.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
23.         ax2 = ax1: ay2 = (ymax - 60) * RND + 50
24.     ELSE
25.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
26.         ax2 = (xmax - 20) * RND + 10: ay2 = (ymax - 60) * RND + 50
27.     END IF
28.     IF _HYPOT(ax1 - ax2, ay1 - ay2) < 50 THEN GOTO restartA
29.  
30.     IF RND < .5 THEN 'get some points on same line
31.         LOCATE 3, 80: PRINT "Blue Points are on same line as Red."
32.         slopeYintersect ax1, ay1, ax2, ay2, slope1, Yintercept1  ' >>  to set up tests on same line
33.         bx1 = (xmax - 20) * RND + 10: by1 = bx1 * slope1 + Yintercept1
34.         bx2 = (xmax - 20) * RND + 10: by2 = bx2 * slope1 + Yintercept1
35.     ELSE
36.         IF RND < .5 THEN 'throw in some verticals
37.             bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 60) * RND + 50
38.             bx2 = bx1: by2 = (ymax - 60) * RND + 50
39.         ELSE
40.             bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 60) * RND + 50
41.             bx2 = (xmax - 20) * RND + 10: by2 = (ymax - 60) * RND + 50
42.         END IF
43.     END IF
44.     IF bx1 < 10 OR bx1 > xmax - 10 THEN GOTO restartA
45.     IF bx2 < 10 OR bx2 > xmax - 10 THEN GOTO restartA
46.     IF by1 < 50 OR by1 > ymax - 10 THEN GOTO restartA
47.     IF by2 < 50 OR by2 > ymax - 10 THEN GOTO restartA
48.     IF _HYPOT(bx1 - bx2, by1 - by2) < 50 THEN GOTO restartA
49.  
50.     LINE (ax1, ay1)-(ax2, ay2), &HFFFF0000
51.     CIRCLE (ax1, ay1), 4, &HFFFF0000
52.     CIRCLE (ax2, ay2), 4, &HFFFF0000
53.  
54.     LINE (bx1, by1)-(bx2, by2), &HFF0000FF
55.     CIRCLE (bx1, by1), 4, &HFF0000FF
56.     CIRCLE (bx2, by2), 4, &HFF0000FF
57.  
58.     LOCATE 1, 1
59.     PRINT "Segments ("; ts$(ax1); ", "; ts$(ay1); ") ("; ts$(ax2); ", ";_
60.      ts$(ay2); ") and ("; ts$(bx1); ", "; ts$(by1); ") ("; ts$(bx2); ", "; ts$(by2); ")"
61. '==================================================++++++++++++====================
62. '  Here is where your call to FUNCTION goes and followup with the graphing of your result
63.  ' VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
64.     intersect = twoLineSegmentsIntersect%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
65.     IF intersect = -1 THEN
66.         PRINT " Segments overlap between min x at "; ts$(ix); " and max x at "; ts$(iy) '< not a "y" here
67.         LINE (ix, 0)-(iy, ymax), &H22FFFF00, BF
68.     ELSEIF intersect = 1 THEN
69.         PRINT " Segments intersect at ("; ts$(ix); ", "; ts$(iy); ")."
70.         CIRCLE (ix, iy), 3, &HFFFFFF00
71.     ELSEIF intersect = 0 THEN
72.         PRINT " Segments do not Intersect or Overlap."
73.     END IF
74. '============================== >>>>>>>>>>>>>>>>>>>>>>> ends interpretation of your functions results
75.     INPUT "Press enter for another demo, any + enter to quit...", again$
76.     CLS
77. LOOP UNTIL LEN(again$)
78.  
79. 'Slope and Y-intersect for non vertical lines,
80. ' if x1 = x2 the line is vertical don't call this sub
81. ' because slope calculation would cause division by 0 error.
82. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
83.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
84. END SUB
85.  
86. FUNCTION ts$ (n)
87.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
88. END FUNCTION
89.  

[bplus]

The "step further" from title of this thread, I meant to get into identifying line segments as intersecting or overlapping and finding either the intersect point or area of overlap (I am happy with just x boundary points at moment) if there is any.

[STxAxTIC]

Sorry guys, have been out for a little bit... but I like this problem - I'll see what I can work out on paper, and if fruitful, may possibly undergo the formality of writing code as well.

Looks like the important cases are already solved - so will report back if I find anything exotic.

[bplus]

Hey STxAxTIC, I suspect this thread subject rather exotic already ;)

I should note something important. In order to get more line segments on the same line being recognized as such in the routines, I had to loosen up the restriction of d = 0 to it being close to 0, <.2 AND I loosened up the restriction of the Y intersects being exactly the same for the 2 line segments, I allowed a difference of 5 pixels. It still doesn't catch ALL segments lying on the same line but does catch most.

I will arrow the spots in the sub:

Code: QB64: [Select]

1. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
2. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
3.     IF ax1 = ax2 THEN 'line a is vertical
4.         IF bx1 = bx2 THEN ' b is vertical
5.             IF ax1 = bx1 THEN lineIntersectLine% = -1 ' if x's are same it is same vertical line
6.             EXIT FUNCTION '
7.         ELSE
8.             ix = ax1
9.             slopeYintersect bx1, by1, bx2, by2, m2, y02
10.             iy = m2 * ix + y02
11.             lineIntersectLine% = 1 'signal a point was found
12.             EXIT FUNCTION
13.         END IF
14.     ELSE
15.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
16.     END IF
17.     IF bx1 = bx2 THEN 'b is vertical
18.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = 1 'signal a point was found
19.         EXIT FUNCTION
20.     ELSE
21.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
22.     END IF
23.     d = -m1 - -m2 ' if = 0 then parallel or equal because slopes are same
24.     IF ABS(d) > .2 THEN 'otherwise about 0 '<<<<<<<<<<<<<<<<<<<<<<<<<< loosen restriction: d = 0
25.         ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
26.         lineIntersectLine% = 1 'signal one intersect point was found
27.     ELSE 'same line or parallel? if y0 are same they are the same
28.         IF ABS(y01 - y02) < 5 THEN lineIntersectLine% = -1 'signal same line! <<<<< loosen from strict:  y01 = yo2
29.     END IF
30. END FUNCTION
31.  

It was in reply #7 that I changed this FUNCTION.

[bplus]

Upon further thinking, determining if the 4 points are co-linear is weakest part of my coding adventure with this so far.

It might be productive to get a separate routine designed just for that purpose. Finding the x boundaries of overlap from there is pretty straight forward grunt work.