Author Topic: Intersect of 2 lines carried a step further  (Read 1198 times)

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

Offline bplus

  • Forum Resident
  • Posts: 4415
  • B+ ots
Intersect of 2 lines carried a step further
« on: March 14, 2020, 08:48:35 PM »
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 "Test intersect line with 1st line vertical:"
  10. PRINT " Line on (10, 0) and (10, 20) intersect line on (0, 20) and (20, 10)"
  11. intersect = lineIntersectLine%(10, 0, 10, 20, 0, 20, 20, 10, answX, answY) 'intersect should be (10 , 15)
  12. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
  13. PRINT "Test intersect with 2nd line vertical:"
  14. PRINT " Line on (0, 20) and (20, 10) intersect line on (10, 0) and (10, 5)"
  15. intersect = lineIntersectLine%(0, 20, 20, 10, 10, 0, 10, 5, answX, answY) 'intersect should be (10 , 15)
  16. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
  17. PRINT "Test intersect with both lines vertical:"
  18. PRINT " Line on (0, 20) and (0, 10) intersect line on (10, 0) and (10, 5)"
  19. intersect = lineIntersectLine%(0, 20, 0, 10, 10, 0, 10, 5, answX, answY) 'intersect should be none
  20. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
  21.  
  22. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
  23. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
  24.     IF ax1 = ax2 THEN 'line a is vertical
  25.         IF bx1 = bx2 THEN
  26.             EXIT FUNCTION 'no intersect
  27.         ELSE
  28.             ix = ax1
  29.             slopeYintersect bx1, by1, bx2, by2, m2, y02
  30.             iy = m2 * ix + y02
  31.             lineIntersectLine% = -1 'signal a point was found
  32.             EXIT FUNCTION
  33.         END IF
  34.     ELSE
  35.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
  36.     END IF
  37.     IF bx1 = bx2 THEN 'b is vertical
  38.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = -1 'signal a point was found
  39.         EXIT FUNCTION
  40.     ELSE
  41.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
  42.     END IF
  43.     d = -m1 - -m2 ' if = 0 then parallel because slopes are same
  44.     IF d THEN ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
  45.     lineIntersectLine% = -1 'signal a point was found
  46.  
  47. 'Slope and Y-intersect for non vertical lines,
  48. ' if x1 = x2 the line is vertical don't call this sub
  49. ' because slope calculation would cause division by 0 error.
  50. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
  51.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
  52.  
  53. FUNCTION ts$ (n)
  54.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
  55.  
  56.  

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

Offline TempodiBasic

  • Forum Resident
  • Posts: 1373
Re: Intersect of 2 lines carried a step further
« Reply #1 on: March 15, 2020, 04:14:25 AM »
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 "Test intersect line with 1st line vertical:"
  10. PRINT " Line on (10, 0) and (10, 20) intersect line on (0, 20) and (20, 10)"
  11. intersect = lineIntersectLine%(10, 0, 10, 20, 0, 20, 20, 10, answX, answY) 'intersect should be (10 , 15)
  12. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
  13. PRINT "Test intersect with 2nd line vertical:"
  14. PRINT " Line on (0, 20) and (20, 10) intersect line on (10, 0) and (10, 5)"
  15. intersect = lineIntersectLine%(0, 20, 20, 10, 10, 0, 10, 5, answX, answY) 'intersect should be (10 , 15)
  16. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
  17. PRINT "Test intersect with both lines vertical:"
  18. PRINT " Line on (0, 20) and (0, 10) intersect line on (10, 0) and (10, 5)"
  19. intersect = lineIntersectLine%(0, 20, 0, 10, 10, 0, 10, 5, answX, answY) 'intersect should be none
  20. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
  21. PRINT "overlapping test TdB"
  22. PRINT " Line on (4, 0) and (6, 10) intersect line on (4, 0) and (6,10)"
  23. intersect = lineIntersectLine(4, 0, 6, 10, 4, 0, 6, 10, answX, answY) ' answer should be (5 , 5)
  24. IF intersect THEN PRINT "("; ts$(answX); ", "; ts$(answY); ")" ELSE PRINT "No point intersect."
  25.  
  26.  
  27. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
  28. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
  29.     IF ax1 = ax2 THEN 'line a is vertical
  30.         IF bx1 = bx2 THEN
  31.             EXIT FUNCTION 'no intersect
  32.         ELSE
  33.             ix = ax1
  34.             slopeYintersect bx1, by1, bx2, by2, m2, y02
  35.             iy = m2 * ix + y02
  36.             lineIntersectLine% = -1 'signal a point was found
  37.             EXIT FUNCTION
  38.         END IF
  39.     ELSE
  40.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
  41.     END IF
  42.     IF bx1 = bx2 THEN 'b is vertical
  43.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = -1 'signal a point was found
  44.         EXIT FUNCTION
  45.     ELSE
  46.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
  47.     END IF
  48.     d = -m1 - -m2 ' if = 0 then parallel because slopes are same
  49.     IF d THEN ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
  50.     lineIntersectLine% = -1 'signal a point was found
  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.  
  58. FUNCTION ts$ (n)
  59.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
  60.  
Waiting your thoughts
Programming isn't difficult, only it's  consuming time and coffee

Offline bplus

  • Forum Resident
  • Posts: 4415
  • B+ ots
Re: Intersect of 2 lines carried a step further
« Reply #2 on: March 15, 2020, 10:56:01 AM »
OK I guess I did miss the case where lines (and segments) might overlap and be on the same line.

Thanks for your interest :)
« Last Edit: March 15, 2020, 11:05:14 AM by bplus »

Offline TempodiBasic

  • Forum Resident
  • Posts: 1373
Re: Intersect of 2 lines carried a step further
« Reply #3 on: March 15, 2020, 12:37:17 PM »
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. :-)
« Last Edit: March 15, 2020, 12:38:27 PM by TempodiBasic »
Programming isn't difficult, only it's  consuming time and coffee

Offline bplus

  • Forum Resident
  • Posts: 4415
  • B+ ots
Re: Intersect of 2 lines carried a step further
« Reply #4 on: March 15, 2020, 01:01:01 PM »
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 "Test intersect line with 1st line vertical: answ should be: (10, 15)"
  13. printResultOfLineIntersectLine 10, 0, 10, 20, 0, 20, 20, 10
  14. PRINT "Test intersect with 2nd line vertical: answ should be: (10, 15) again."
  15. printResultOfLineIntersectLine 0, 20, 20, 10, 10, 0, 10, 5
  16. PRINT "Test intersect with both lines vertical: answ should be: No intersect."
  17. printResultOfLineIntersectLine 0, 20, 0, 10, 10, 0, 10, 5
  18. PRINT "TempodiBasic test, 4 points on same line, try 2 vertical lines, same points:"
  19. PRINT "Answer should be: Lines are the same."
  20. printResultOfLineIntersectLine 5, 10, 5, 20, 5, 10, 5, 20
  21. PRINT "Test points off same sloped line: answ should be: Lines are the same."
  22. printResultOfLineIntersectLine 2, 4, 6, 12, 10, 20, 15, 30
  23.  
  24. SUB printResultOfLineIntersectLine (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2)
  25.     PRINT "Lines on ("; ts$(ax1); ", "; ts$(ay1); ") ("; ts$(ax2); ", ";_
  26.      ts$(ay2); ") and ("; ts$(bx1); ", "; ts$(by1); ") ("; ts$(bx2); ", "; ts$(by2); ")"
  27.     intersect = lineIntersectLine%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, answX, answY)
  28.     IF intersect = 0 THEN
  29.         PRINT "No intersection."
  30.     ELSEIF intersect = -1 THEN
  31.         PRINT "Lines are the same."
  32.     ELSEIF intersect = 1 THEN
  33.         PRINT "Lines intersect at ("; ts$(answX); ", "; ts$(answY); ")"
  34.     END IF
  35.  
  36. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
  37. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
  38.     IF ax1 = ax2 THEN 'line a is vertical
  39.         IF bx1 = bx2 THEN ' b is vertical
  40.             IF ax1 = bx1 THEN lineIntersectLine% = -1 ' if x's are same it is same vertical line
  41.             EXIT FUNCTION '
  42.         ELSE
  43.             ix = ax1
  44.             slopeYintersect bx1, by1, bx2, by2, m2, y02
  45.             iy = m2 * ix + y02
  46.             lineIntersectLine% = 1 'signal a point was found
  47.             EXIT FUNCTION
  48.         END IF
  49.     ELSE
  50.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
  51.     END IF
  52.     IF bx1 = bx2 THEN 'b is vertical
  53.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = 1 'signal a point was found
  54.         EXIT FUNCTION
  55.     ELSE
  56.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
  57.     END IF
  58.     d = -m1 - -m2 ' if = 0 then parallel or equal because slopes are same
  59.     IF d <> 0 THEN
  60.         ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
  61.         lineIntersectLine% = 1 'signal one intersect point was found
  62.     ELSE 'same line or parallel? if y0 are same they are the same
  63.         IF y01 = y02 THEN lineIntersectLine% = -1 'signal same line!
  64.     END IF
  65.  
  66. 'Slope and Y-intersect for non vertical lines,
  67. ' if x1 = x2 the line is vertical don't call this sub
  68. ' because slope calculation would cause division by 0 error.
  69. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
  70.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
  71.  
  72. FUNCTION ts$ (n)
  73.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
  74.  
  75.  

Offline TempodiBasic

  • Forum Resident
  • Posts: 1373
Re: Intersect of 2 lines carried a step further
« Reply #5 on: March 15, 2020, 01:22:42 PM »
Great Bplus
as always  you're fast, rapid and accurate!
Programming isn't difficult, only it's  consuming time and coffee

Offline bplus

  • Forum Resident
  • Posts: 4415
  • B+ ots
Re: Intersect of 2 lines carried a step further
« Reply #6 on: March 15, 2020, 01:24:33 PM »
Thanks, that was a good catch TempodiBasic. I will likely have the line segments code reworked this afternoon.

Offline bplus

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

Thanks to round-off errors (I think), it misses overlapping segments on occasion.
« Last Edit: March 15, 2020, 11:35:44 PM by bplus »

Offline EricE

  • Forum Regular
  • Posts: 117
Re: Intersect of 2 lines carried a step further
« Reply #8 on: March 16, 2020, 02:24:54 AM »
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 invV(1 TO 2, 1 TO 2) AS DOUBLE
  15.  
  16. ' Intersection point
  17. DIM Xr(1 TO 2) AS DOUBLE
  18. DIM Xs(1 TO 2) AS DOUBLE
  19.  
  20. ' Test Example
  21. A(1) = 4.0
  22. A(2) = 0.0
  23. B(1) = 6.0
  24. B(2) = 10.0
  25. '---
  26. C(1) = 0.0
  27. C(2) = 3.0
  28. D(1) = 10.0
  29. D(2) = 7.0
  30.  
  31. ' directed segment AB
  32. v1(1) = B(1) - A(1)
  33. v1(2) = B(2) - A(2)
  34.  
  35. ' directed segment CD
  36. v2(1) = D(1) - C(1)
  37. v2(2) = D(2) - C(2)
  38.  
  39. ' Parametric line equations
  40. '          Xr = A + v1*r
  41. '          Xs = C + v2*s
  42. '
  43. ' Line intersection criteria
  44. '    A + v1*r = C + v2*s
  45. ' Determine scalars r, s
  46. '
  47. ' Matrix equation
  48. '         A-C = [-v1, v2]*[r, s]^t
  49. ' Define    V = [-v1, v2]
  50. '        invV = V^-1
  51. '    [r, s]^t = invV*(A - C)
  52.  
  53. ' Calculate invV([-v1, v2])
  54. '
  55. ' Compute determinant
  56. DetV = -v1(1) * v2(2) + v2(1) * v1(2)
  57. ' DetV must not be zero
  58.  
  59. invV(1, 1) = v2(2) / DetV
  60. invV(2, 1) = v1(2) / DetV
  61. invV(1, 2) = -v2(1) / DetV
  62. invV(2, 2) = -v1(1) / DetV
  63.  
  64. r = invV(1, 1) * (A(1) - C(1)) + invV(1, 2) * (A(2) - C(2))
  65. s = invV(2, 1) * (A(1) - C(1)) + invV(2, 2) * (A(2) - C(2))
  66.  
  67. ' Intersection point
  68. Xr(1) = A(1) + r * v1(1)
  69. Xr(2) = A(2) + r * v1(2)
  70.  
  71. Xs(1) = C(1) + s * v2(1)
  72. Xs(2) = C(2) + s * v2(2)
  73.  
  74. PRINT "Intersection Point:"
  75. ' (Xr(1), Xr(2)) and (Xs(1), Xs(2)) are the coordinates of the same point
  76. PRINT Xr(1), Xr(2)
  77. PRINT Xs(1), Xs(2)
  78.  
  79.  
  80.  


Offline TerryRitchie

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

Offline bplus

  • Forum Resident
  • Posts: 4415
  • B+ ots
Re: Intersect of 2 lines carried a step further
« Reply #10 on: March 16, 2020, 10:28:54 AM »
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. DIM ax1 AS INTEGER, ax2 AS INTEGER, ay1 AS INTEGER, ay2 AS INTEGER
  16. DIM bx1 AS INTEGER, bx2 AS INTEGER, by1 AS INTEGER, by2 AS INTEGER
  17.     restartA:
  18.     CLS
  19.     IF RND < .5 THEN 'throw in some vertical lines
  20.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
  21.         ax2 = ax1: ay2 = (ymax - 60) * RND + 50
  22.     ELSE
  23.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
  24.         ax2 = (xmax - 20) * RND + 10: ay2 = (ymax - 60) * RND + 50
  25.     END IF
  26.     IF _HYPOT(ax1 - ax2, ay1 - ay2) < 50 THEN GOTO restartA
  27.  
  28.     IF RND < .5 THEN 'get some points on same line
  29.         LOCATE 3, 80: PRINT "Blue Points are on same line as Red."
  30.         slopeYintersect ax1, ay1, ax2, ay2, slope1, Yintercept1  ' >>  to set up tests on same line
  31.         bx1 = (xmax - 20) * RND + 10: by1 = bx1 * slope1 + Yintercept1
  32.         bx2 = (xmax - 20) * RND + 10: by2 = bx2 * slope1 + Yintercept1
  33.     ELSE
  34.         IF RND < .5 THEN 'throw in some verticals
  35.             bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 60) * RND + 50
  36.             bx2 = bx1: by2 = (ymax - 60) * RND + 50
  37.         ELSE
  38.             bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 60) * RND + 50
  39.             bx2 = (xmax - 20) * RND + 10: by2 = (ymax - 60) * RND + 50
  40.         END IF
  41.     END IF
  42.     IF bx1 < 10 OR bx1 > xmax - 10 THEN GOTO restartA
  43.     IF bx2 < 10 OR bx2 > xmax - 10 THEN GOTO restartA
  44.     IF by1 < 50 OR by1 > ymax - 10 THEN GOTO restartA
  45.     IF by2 < 50 OR by2 > ymax - 10 THEN GOTO restartA
  46.     IF _HYPOT(bx1 - bx2, by1 - by2) < 50 THEN GOTO restartA
  47.  
  48.     LINE (ax1, ay1)-(ax2, ay2), &HFFFF0000
  49.     CIRCLE (ax1, ay1), 4, &HFFFF0000
  50.     CIRCLE (ax2, ay2), 4, &HFFFF0000
  51.  
  52.     LINE (bx1, by1)-(bx2, by2), &HFF0000FF
  53.     CIRCLE (bx1, by1), 4, &HFF0000FF
  54.     CIRCLE (bx2, by2), 4, &HFF0000FF
  55.  
  56.     LOCATE 1, 1
  57.     PRINT "Segments ("; ts$(ax1); ", "; ts$(ay1); ") ("; ts$(ax2); ", ";_
  58.      ts$(ay2); ") and ("; ts$(bx1); ", "; ts$(by1); ") ("; ts$(bx2); ", "; ts$(by2); ")"
  59. '==================================================++++++++++++====================
  60. '  Here is where your call to FUNCTION goes and followup with the graphing of your result
  61.  ' VVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
  62.     intersect = twoLineSegmentsIntersect%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
  63.     IF intersect = -1 THEN
  64.         PRINT " Segments overlap between min x at "; ts$(ix); " and max x at "; ts$(iy) '< not a "y" here
  65.         LINE (ix, 0)-(iy, ymax), &H22FFFF00, BF
  66.     ELSEIF intersect = 1 THEN
  67.         PRINT " Segments intersect at ("; ts$(ix); ", "; ts$(iy); ")."
  68.         CIRCLE (ix, iy), 3, &HFFFFFF00
  69.     ELSEIF intersect = 0 THEN
  70.         PRINT " Segments do not Intersect or Overlap."
  71.     END IF
  72. '============================== >>>>>>>>>>>>>>>>>>>>>>> ends interpretation of your functions results
  73.     INPUT "Press enter for another demo, any + enter to quit...", again$
  74.     CLS
  75. LOOP UNTIL LEN(again$)
  76.  
  77. 'Slope and Y-intersect for non vertical lines,
  78. ' if x1 = x2 the line is vertical don't call this sub
  79. ' because slope calculation would cause division by 0 error.
  80. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
  81.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
  82.  
  83. FUNCTION ts$ (n)
  84.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
  85.  
« Last Edit: March 16, 2020, 10:54:58 AM by bplus »

Offline bplus

  • Forum Resident
  • Posts: 4415
  • B+ ots
Re: Intersect of 2 lines carried a step further
« Reply #11 on: March 16, 2020, 11:39:02 AM »
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.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 809
  • Savage.
    • WFBarnes
Re: Intersect of 2 lines carried a step further
« Reply #12 on: March 16, 2020, 11:45:01 AM »
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.
« Last Edit: March 16, 2020, 11:47:51 AM by STxAxTIC »

Offline bplus

  • Forum Resident
  • Posts: 4415
  • B+ ots
Re: Intersect of 2 lines carried a step further
« Reply #13 on: March 16, 2020, 12:02:12 PM »
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.  


It was in reply #7 that I changed this FUNCTION.
« Last Edit: March 16, 2020, 12:06:49 PM by bplus »

Offline bplus

  • Forum Resident
  • Posts: 4415
  • B+ ots
Re: Intersect of 2 lines carried a step further
« Reply #14 on: March 16, 2020, 12:21:17 PM »
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.