QB64.org Forum

Active Forums => Programs => Topic started by: bplus on March 14, 2020, 08:48:35 pm

Title: Intersect of 2 lines carried a step further
Post by: bplus 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
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.  

Title: Re: Intersect of 2 lines carried a step further
Post by: TempodiBasic 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
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

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus 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 :)

Title: Re: Intersect of 2 lines carried a step further
Post by: TempodiBasic 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. :-)

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus 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
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.  

Title: Re: Intersect of 2 lines carried a step further
Post by: TempodiBasic on March 15, 2020, 01:22:42 pm

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

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus 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.

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus 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. _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.

Title: Re: Intersect of 2 lines carried a step further
Post by: EricE 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 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.  

Title: Re: Intersect of 2 lines carried a step further
Post by: TerryRitchie 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. 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.  

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus 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. _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.  

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus 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.

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC 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.

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus 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. END FUNCTION
31.  

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

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus 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.

Title: Re: Intersect of 2 lines carried a step further
Post by: EricE on March 16, 2020, 01:11:40 pm

For this problem I need to know a good value for QB64's Machine Epsilon.

Edited to add:
I just started a new thread on the topic of QB64's Machine Epsilon.
https://www.qb64.org/forum/index.php?topic=2353.0 (https://www.qb64.org/forum/index.php?topic=2353.0)

Title: Re: Intersect of 2 lines carried a step further
Post by: TerryRitchie on March 16, 2020, 01:49:38 pm

Quote from: bplus on March 16, 2020, 10:28:54 am

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

The code I posted works with line segments. You need to supply the start and end X,Y coordinate pairs for each line segment.

Title: Re: Intersect of 2 lines carried a step further
Post by: EricE on March 16, 2020, 02:05:35 pm

My code is for the lines containing the segments.
However, adding a simple check will tell if the two segments intersect.

Code: QB64: [Select]

1. IF (0.0 <= r) AND (r <= 1.0) AND (0.0 <= s) AND (s <= 1.0) THEN
2.     PRINT "Line segments intersect"
3. ELSE
4.     PRINT "Line segments do not intersect"
5. END IF
6. <

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 16, 2020, 02:13:52 pm

Quote from: TerryRitchie on March 16, 2020, 01:49:38 pm

The code I posted works with line segments. You need to supply the start and end X,Y coordinate pairs for each line segment.

Yeah I was looking over your code Terry, you are even checking if points are co-linear but 3 at a time and in a weird way ie rotation clockwise or counter? I don't see line segments turning one way or another. Otherwise I would try to test your routines in the tester code.

Quote

You need to supply the start and end X,Y coordinate pairs for each line segment.

Just what the tester code sets up unless it makes a difference which is first and which is second. Still working through the code... maybe the orientation stuff is all internal and I just need a pointType to plug the numbers there.
ObjIntersect only returns true or false for intersect and/or for overlap?

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 16, 2020, 02:17:01 pm

Quote from: EricE on March 16, 2020, 02:05:35 pm

My code is for the lines containing the segments.
However, adding a simple check will tell if the two segments intersect.

Code: QB64: [Select]

1. IF (0.0 <= r) AND (r <= 1.0) AND (0.0 <= s) AND (s <= 1.0) THEN
2.     PRINT "Line segments intersect"
3. ELSE
4.     PRINT "Line segments do not intersect"
5. END IF
6. <

Your code only works if D <> 0

Quote

Code: QB64: [Select]

1. ' Compute determinant
2. DetV = -v1(1) * v2(2) + v2(1) * v1(2)
3. ' DetV must not be zero

Title: Re: Intersect of 2 lines carried a step further
Post by: TerryRitchie on March 16, 2020, 02:45:07 pm

Note the source cited in my code. I don't claim to have written that code myself, I converted it from the source cited. The clockwise/counter-clockwise thing has me a bit confused as well.

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 16, 2020, 06:50:33 pm

I have modified the twoSegmentsIntersect FUNCTION or SUB tester code. It was missing an important case of 2 segments lying on the same vertical line. Now the SUB or FUNCTION should ID either the Intersect Point or the segment Overlap boundary 2 end points (which could be the same if they only overlap at one point).

Code: QB64: [Select]

1. _TITLE "Segments Intersect mod tester" 'b+ 2020-03-16
2. ' Just worked Rosetta Code for Line Intersect Line
3. ' but what if we want to know if two line segments intersect?
4. '2020-03-14 "Two Line Segments Intersect" 'b+ 2020-03-14  start
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. '2020-03-16 "Segments Intersect mod tester"
13. 'mod tester for 2 segments of vertical line and found I need to add more parameters to
14. ' FUNCTION twoLineSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
15. ' mod that name and parameters to:
16. ' FUNCTION twoSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, i1x, i1y, i2x, i2y)
17.  
18. CONST xmax = 1200, ymax = 700
19. SCREEN _NEWIMAGE(xmax, ymax, 32)
20. _DELAY .25
21. _SCREENMOVE _MIDDLE
22. DIM ax1 AS INTEGER, ax2 AS INTEGER, ay1 AS INTEGER, ay2 AS INTEGER
23. DIM bx1 AS INTEGER, bx2 AS INTEGER, by1 AS INTEGER, by2 AS INTEGER
24. DO
25.     restartA:
26.     CLS
27.     IF RND < .5 THEN 'throw in some vertical lines
28.         LOCATE 3, 80: PRINT "Red Points are vertical."
29.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
30.         ax2 = ax1: ay2 = (ymax - 60) * RND + 50
31.     ELSE
32.         LOCATE 3, 80: PRINT "Red Points are Random."
33.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
34.         ax2 = (xmax - 20) * RND + 10: ay2 = (ymax - 60) * RND + 50
35.     END IF
36.     IF _HYPOT(ax1 - ax2, ay1 - ay2) < 50 THEN GOTO restartA
37.  
38.     IF RND < .5 THEN 'get some points on same line
39.         LOCATE 3, 80: PRINT "Blue Points are on same line as Red."
40.         slopeYintersect ax1, ay1, ax2, ay2, slope1, Yintercept1
41.         bx1 = (xmax - 20) * RND + 10: by1 = bx1 * slope1 + Yintercept1
42.         bx2 = (xmax - 20) * RND + 10: by2 = bx2 * slope1 + Yintercept1
43.     ELSE
44.         IF RND < .4 THEN 'throw in some verticals, we already have a doing verticals
45.             LOCATE 3, 80: PRINT SPACE$(50)
46.             LOCATE 3, 80: PRINT "All points vertical."
47.             ax1 = (xmax - 20) * RND + 10: ax2 = ax1: bx1 = ax1: bx2 = ax1
48.             ay1 = 50 + RND * 50: ay2 = ay1 + 50 + RND * 50
49.             by1 = ay1 + 25 + RND * 50: by2 = by1 + 50 + (RND * ymax - 60 - by1)
50.             by1 = (ymax - 60) * RND + 50: bx2 = bx1: by2 = (ymax - 60) * RND + 50
51.         ELSE
52.             LOCATE 4, 80: PRINT "Blue Points are Random."
53.             bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 60) * RND + 50
54.             bx2 = (xmax - 20) * RND + 10: by2 = (ymax - 60) * RND + 50
55.         END IF
56.     END IF
57.     IF bx1 < 10 OR bx1 > xmax - 10 THEN GOTO restartA
58.     IF bx2 < 10 OR bx2 > xmax - 10 THEN GOTO restartA
59.     IF by1 < 50 OR by1 > ymax - 10 THEN GOTO restartA
60.     IF by2 < 50 OR by2 > ymax - 10 THEN GOTO restartA
61.     IF _HYPOT(bx1 - bx2, by1 - by2) < 30 THEN GOTO restartA
62.  
63.     LINE (ax1, ay1)-(ax2, ay2), &HFFFF0000
64.     CIRCLE (ax1, ay1), 4, &HFFFF0000
65.     CIRCLE (ax2, ay2), 4, &HFFFF0000
66.  
67.     LINE (bx1, by1)-(bx2, by2), &HFF0000FF
68.     CIRCLE (bx1, by1), 4, &HFF0000FF
69.     CIRCLE (bx2, by2), 4, &HFF0000FF
70.  
71.     LOCATE 1, 1
72.     PRINT "Segments ("; ts$(ax1); ", "; ts$(ay1); ") ("; ts$(ax2); ", ";_
73.      ts$(ay2); ") and ("; ts$(bx1); ", "; ts$(by1); ") ("; ts$(bx2); ", "; ts$(by2); ")"
74.  
75.     '                    Plug in your 2 Segment Intersect SUB or FUNCTION Here
76.     '                 and interpret reults: yellow circle around intersect point
77.     '                and an alpha shaded box where two co-linear segments overlap
78.     '=====================================================================================================
79.     'intersect = twoSegmentsIntersect%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, i1x, i1y, i2x, i2y)
80.     'IF intersect = -1 THEN 'segments overlap on same line
81.     '    PRINT " Segments overlap between min x at "; ts$(ix); " and max x at "; ts$(iy) '< not a "y" here
82.     '    LINE (i1x, i1y)-(i2x, i2y), &HFFFFFFFF
83.     'ELSEIF intersect = 1 THEN 'segments intersect at one point
84.     '    PRINT " Segments intersect at ("; ts$(ix); ", "; ts$(iy); ")."
85.     '    CIRCLE (ix, iy), 3, &HFFFFFFFF
86.     'ELSEIF intersect = 0 THEN 'segments do not intersect nor overlap
87.     '    PRINT " Segments do not Intersect or Overlap."
88.     'END IF
89.     '=====================================================================================================
90.  
91.     INPUT "Press enter for another demo, any + enter to quit...", again$
92.     CLS
93. LOOP UNTIL LEN(again$)
94.  
95. 'Slope and Y-intersect for non vertical lines,
96. ' if x1 = x2 the line is vertical don't call this sub
97. ' because slope calculation would cause division by 0 error.
98. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
99.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
100. END SUB
101.  
102. FUNCTION ts$ (n)
103.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
104. END FUNCTION
105. ' ======================================== end tester code functions ======================================
106.  

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 16, 2020, 09:57:49 pm

OK I think I got it, running without error over 100 tests:

Code: QB64: [Select]

1. _TITLE "Segments Intersect revised 2020-03-16:  White Circles are Intersects White Lines are Overlaps" 'b+ 2020-03-16
2. ' Just worked Rosetta Code for Line Intersect Line
3. ' but what if we want to know if two line segments intersect?
4. '2020-03-14 "Two Line Segments Intersect" 'b+ 2020-03-14  start
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. '2020-03-16 "Segments Intersect mod tester"  >>> just post testing code
13. 'mod tester for 2 segments of vertical line and found I need to add more parameters to
14. ' FUNCTION twoLineSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
15. ' mod that name and parameters to:
16. ' FUNCTION twoSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1, ix2, iy2)
17.  
18. '2020-03-16 Segments Intersect revised 2020-03-16
19. ' OK now get the new FUNCTION working
20. ' ah! I had to tighten down D from >.2 to >.05 but loosen y-axis intersect
21.  
22. CONST xmax = 1200, ymax = 700
23. SCREEN _NEWIMAGE(xmax, ymax, 32)
24. _DELAY .25
25. _SCREENMOVE _MIDDLE
26. DIM ax1 AS INTEGER, ax2 AS INTEGER, ay1 AS INTEGER, ay2 AS INTEGER
27. DIM bx1 AS INTEGER, bx2 AS INTEGER, by1 AS INTEGER, by2 AS INTEGER
28. DO
29.     restartA:
30.     CLS
31.     IF RND < .3 THEN 'throw in some vertical lines
32.         LOCATE 3, 80: PRINT "Red Points are vertical."
33.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
34.         ax2 = ax1: ay2 = (ymax - 60) * RND + 50
35.     ELSE
36.         LOCATE 3, 80: PRINT "Red Points are Random."
37.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 60) * RND + 50
38.         ax2 = (xmax - 20) * RND + 10: ay2 = (ymax - 60) * RND + 50
39.     END IF
40.     IF _HYPOT(ax1 - ax2, ay1 - ay2) < 50 THEN GOTO restartA
41.  
42.     IF RND < .6 THEN 'get some points on same line
43.         LOCATE 3, 80: PRINT "Blue Points are on same line as Red."
44.         slopeYintersect ax1, ay1, ax2, ay2, slope1, Yintercept1
45.         bx1 = (xmax - 20) * RND + 10: by1 = bx1 * slope1 + Yintercept1
46.         bx2 = (xmax - 20) * RND + 10: by2 = bx2 * slope1 + Yintercept1
47.     ELSE
48.         IF RND < .4 THEN 'throw in some verticals, we already have a doing verticals
49.             LOCATE 3, 80: PRINT SPACE$(50)
50.             LOCATE 3, 80: PRINT "All points vertical."
51.             ax1 = (xmax - 20) * RND + 10: ax2 = ax1: bx1 = ax1: bx2 = ax1
52.             ay1 = 50 + RND * 50: ay2 = ay1 + 50 + RND * 50
53.             by1 = ay1 + 25 + RND * 50: by2 = by1 + 50 + (RND * ymax - 60 - by1)
54.             by1 = (ymax - 60) * RND + 50: bx2 = bx1: by2 = (ymax - 60) * RND + 50
55.         ELSE
56.             LOCATE 4, 80: PRINT "Blue Points are Random."
57.             bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 60) * RND + 50
58.             bx2 = (xmax - 20) * RND + 10: by2 = (ymax - 60) * RND + 50
59.         END IF
60.     END IF
61.     IF bx1 < 10 OR bx1 > xmax - 10 THEN GOTO restartA
62.     IF bx2 < 10 OR bx2 > xmax - 10 THEN GOTO restartA
63.     IF by1 < 50 OR by1 > ymax - 10 THEN GOTO restartA
64.     IF by2 < 50 OR by2 > ymax - 10 THEN GOTO restartA
65.     IF _HYPOT(bx1 - bx2, by1 - by2) < 30 THEN GOTO restartA
66.  
67.     LINE (ax1, ay1)-(ax2, ay2), &HFFFF0000
68.     CIRCLE (ax1, ay1), 4, &HFFFF0000
69.     CIRCLE (ax2, ay2), 4, &HFFFF0000
70.  
71.     LINE (bx1, by1)-(bx2, by2), &HFF0000FF
72.     CIRCLE (bx1, by1), 4, &HFF0000FF
73.     CIRCLE (bx2, by2), 4, &HFF0000FF
74.  
75.     LOCATE 1, 1
76.     PRINT "Segments ("; ts$(ax1); ", "; ts$(ay1); ") ("; ts$(ax2); ", ";_
77.      ts$(ay2); ") and ("; ts$(bx1); ", "; ts$(by1); ") ("; ts$(bx2); ", "; ts$(by2); ")"
78.  
79.     '                    Plug in your 2 Segment Intersect SUB or FUNCTION Here
80.     '                 and interpret reults: yellow circle around intersect point
81.     '                and an alpha shaded box where two co-linear segments overlap
82.     '=====================================================================================================
83.     intersect = twoSegmentsIntersect%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1, ix2, iy2)
84.     IF intersect = -1 THEN 'segments overlap on same line
85.         PRINT " Segments overlap between: ("; ts$(ix1); ", "; ts$(iy1); ") and ("; ts$(ix2); ", "; ts$(iy2); ")"
86.         LINE (ix1, iy1)-(ix2, iy2), &HFFFFFFFF
87.     ELSEIF intersect = 1 THEN 'segments intersect at one point
88.         PRINT " Segments intersect: ("; ts$(ix1); ", "; ts$(iy1); ")"
89.         CIRCLE (ix1, iy1), 3, &HFFFFFFFF
90.     ELSEIF intersect = 0 THEN 'segments do not intersect nor overlap
91.         PRINT " Segments do not Intersect or Overlap."
92.     END IF
93.     '=====================================================================================================
94.  
95.     INPUT "Press enter for another demo, any + enter to quit...", again$
96.     CLS
97. LOOP UNTIL LEN(again$)
98.  
99. 'Slope and Y-intersect for non vertical lines,
100. ' if x1 = x2 the line is vertical don't call this sub
101. ' because slope calculation would cause division by 0 error.
102. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
103.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
104. END SUB
105.  
106. FUNCTION ts$ (n)
107.     ts$ = _TRIM$(STR$(INT(100 * n) / 100))
108. END FUNCTION
109. ' ======================================== end tester code functions ======================================
110.  
111.  
112. 'This function needs: FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
113. ' which in turn needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
114. FUNCTION twoSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1, ix2, iy2)
115.     intersect = lineIntersectLine%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
116.     IF ax1 < ax2 THEN aMinX = ax1: aMaxX = ax2 ELSE aMinX = ax2: aMaxX = ax1
117.     IF ay1 < ay2 THEN aMinY = ay1: aMaxY = ay2 ELSE aMinY = ay2: aMaxY = ay1
118.     IF bx1 < bx2 THEN bMinX = bx1: bMaxX = bx2 ELSE bMinX = bx2: bMaxX = bx1
119.     IF by1 < by2 THEN bMinY = by1: bMaxY = by2 ELSE bMinY = by2: bMaxY = by1
120.     IF intersect = 0 THEN 'no  intersect
121.         twoSegmentsIntersect% = 0
122.     ELSEIF intersect = 1 THEN 'segments intersect at one point
123.         IF ax1 = ax2 THEN 'is iy between
124.             IF iy < aMinY OR iy > aMaxY OR ix < bMinX OR ix > bMaxX THEN
125.                 twoSegmentsIntersect% = 0
126.             ELSE
127.                 ix1 = ix: iy1 = iy: twoSegmentsIntersect% = 1
128.             END IF
129.         ELSEIF bx1 = bx2 THEN
130.             IF iy < bMinY OR iy > bMaxY OR ix < aMinX OR ix > aMaxX THEN
131.                 twoSegmentsIntersect% = 0
132.             ELSE
133.                 ix1 = ix: iy1 = iy: twoSegmentsIntersect% = 1
134.             END IF
135.         ELSE
136.             IF (aMinX <= ix AND ix <= aMaxX) AND (bMinX <= ix AND ix <= bMaxX) THEN
137.                 ix1 = ix: iy1 = iy: twoSegmentsIntersect% = 1
138.             ELSE
139.                 twoSegmentsIntersect% = 0
140.             END IF
141.         END IF
142.     ELSEIF intersect = -1 THEN 'segments are on same line get over lap section
143.         'first check if both are on vertical line
144.         IF ax1 = ax2 THEN 'and we know both are same line  we have two vertical segemnts, do they over lap?
145.             ix1 = ax1: ix2 = ax1
146.             IF aMinY < bMinY THEN
147.                 IF aMaxY < bMinY THEN
148.                     twoSegmentsIntersect% = 0
149.                 ELSE
150.                     twoSegmentsIntersect% = -1: iy1 = bMinY
151.                     IF aMaxY > bMaxY THEN
152.                         iy2 = bMaxY
153.                     ELSE
154.                         iy2 = aMaxY
155.                     END IF
156.                 END IF
157.             ELSE 'bMinY <= aMinY
158.                 IF bMaxY < aMinY THEN
159.                     twoSegmentsIntersect% = 0
160.                 ELSE
161.                     twoSegmentsIntersect% = -1: iy1 = aMinY
162.                     IF bMaxY > aMaxY THEN
163.                         iy2 = aMaxY
164.                     ELSE
165.                         iy2 = bMaxY
166.                     END IF
167.                 END IF
168.             END IF
169.         ELSE 'the same line is not vertical
170.             IF aMinX < bMinX THEN
171.                 IF aMaxX < bMinX THEN
172.                     twoSegmentsIntersect% = 0
173.                 ELSE
174.                     twoSegmentsIntersect% = -1: ix1 = bMinX
175.                     IF bx1 = bMinX THEN iy1 = by1 ELSE iy1 = by2
176.                     IF aMaxX > bMaxX THEN
177.                         ix2 = bMaxX
178.                         IF bx1 = bMaxX THEN iy2 = by1 ELSE iy2 = by2
179.                     ELSE
180.                         ix2 = aMaxX
181.                         IF ax1 = aMaxX THEN iy2 = ay1 ELSE iy2 = ay2
182.                     END IF
183.                 END IF
184.             ELSE 'aMinX >= bMinX
185.                 IF aMinX > bMaxX THEN
186.                     twoSegmentsIntersect% = 0
187.                 ELSE
188.                     twoSegmentsIntersect% = -1: ix1 = aMinX
189.                     IF ax1 = aMinX THEN iy1 = ay1 ELSE iy1 = ay2
190.                     IF bMaxX > aMaxX THEN
191.                         ix2 = aMaxX
192.                         IF ax1 = aMaxX THEN iy2 = ay1 ELSE iy2 = ay2
193.                     ELSE
194.                         ix2 = bMaxX
195.                         IF bx1 = bMaxX THEN iy2 = by1 ELSE iy2 = by2
196.                     END IF
197.                 END IF
198.             END IF
199.         END IF
200.     END IF
201. END FUNCTION
202.  
203. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
204. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
205.     IF ax1 = ax2 THEN 'line a is vertical
206.         IF bx1 = bx2 THEN ' b is vertical
207.             IF ax1 = bx1 THEN lineIntersectLine% = -1 ' if x's are same it is same vertical line
208.             EXIT FUNCTION '
209.         ELSE
210.             ix = ax1
211.             slopeYintersect bx1, by1, bx2, by2, m2, y02
212.             iy = m2 * ix + y02
213.             lineIntersectLine% = 1 'signal a point was found
214.             EXIT FUNCTION
215.         END IF
216.     ELSE
217.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
218.     END IF
219.     IF bx1 = bx2 THEN 'b is vertical
220.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = 1 'signal a point was found
221.         EXIT FUNCTION
222.     ELSE
223.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
224.     END IF
225.     d = -m1 - -m2 ' if = 0 then parallel or equal because slopes are same
226.     IF ABS(d) > .05 THEN 'otherwise about 0 <<< tighten down from .2 to .05
227.         ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
228.         lineIntersectLine% = 1 'signal one intersect point was found
229.     ELSE 'same line or parallel? if y0 (y-axis interssect) are same they are the same
230.         IF ABS(y01 - y02) < 15 THEN lineIntersectLine% = -1 'signal same line!  <<< loosen more! 5 to 15
231.     END IF
232. END FUNCTION
233.  

Best answer so far, if anyone can cut down the size of twoSegmentIntersect%() Function...?


2020-03-18 Update: I have tested the twoSegmentIntersect%() Function in "Two Triangles Overlap" see below and found the Overlap signal was coming up with allot of false positives, so there is plenty of room for improvement yet remaining.

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 17, 2020, 06:30:51 pm

I worked something useful out on paper - if I can just get a darn second to sit and crystallize it I'll meet you at the end bplus!

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 17, 2020, 08:31:04 pm

I just heard "her" car pull in so I gotta go but here's what I have buddy. Hope it adds to something!

Drag line with mouse 1

Rotate with mouse wheel

All cases covered except parallel, which is easy

Code: QB64: [Select]

1. SCREEN 12
2.  
3. TYPE Vector
4.     x AS DOUBLE
5.     y AS DOUBLE
6. END TYPE
7.  
8. TYPE LineSegment
9.     b AS Vector
10.     alpha1 AS DOUBLE
11.     alpha2 AS DOUBLE
12.     ang AS DOUBLE
13.     t AS Vector
14.     p1 AS Vector
15.     p2 AS Vector
16. END TYPE
17.  
18. DIM SHARED Segments(2) AS LineSegment
19.  
20. Segments(1).b.x = 0
21. Segments(1).b.y = 0
22. Segments(1).alpha1 = -150
23. Segments(1).alpha2 = 150
24. Segments(1).ang = 0
25. CALL CalcLine(1)
26.  
27. Segments(2).b.x = 0
28. Segments(2).b.y = 50
29. Segments(2).alpha1 = -150
30. Segments(2).alpha2 = 150
31. Segments(2).ang = ATN(1)
32. CALL CalcLine(2)
33.  
34. DO
35.  
36.     DO WHILE _MOUSEINPUT
37.         x = _MOUSEX
38.         y = _MOUSEY
39.         IF ((x > 0) AND (x < _WIDTH) AND (y > 0) AND (y < _HEIGHT)) THEN
40.             IF _MOUSEBUTTON(1) THEN
41.                 x = _MOUSEX
42.                 y = _MOUSEY
43.                 Segments(1).b.x = (x - _WIDTH / 2)
44.                 Segments(1).b.y = (-y + _HEIGHT / 2)
45.                 CALL CalcLine(1)
46.             END IF
47.             IF _MOUSEWHEEL > 0 THEN
48.                 Segments(1).ang = Segments(1).ang + ATN(1) / 10
49.                 CALL CalcLine(1)
50.             END IF
51.             IF _MOUSEWHEEL < 0 THEN
52.                 Segments(1).ang = Segments(1).ang - ATN(1) / 10
53.                 CALL CalcLine(1)
54.             END IF
55.         END IF
56.     LOOP
57.  
58.     CLS
59.     CALL cline(Segments(1).p1.x, Segments(1).p1.y, Segments(1).p2.x, Segments(1).p2.y, 15)
60.     CALL cline(Segments(2).p1.x, Segments(2).p1.y, Segments(2).p2.x, Segments(2).p2.y, 14)
61.  
62.     ''' Intersection calculation
63.     DIM db AS Vector
64.     db.x = Segments(2).b.x - Segments(1).b.x
65.     db.y = Segments(2).b.y - Segments(1).b.y
66.     qj = DotProduct(db, Segments(1).t)
67.     ql = DotProduct(db, Segments(2).t)
68.     p = DotProduct(Segments(1).t, Segments(2).t)
69.     pp = p * p
70.     IF (pp < 1) THEN
71.         alphaj = (qj - p * ql) / (1 - pp)
72.         alphal = (p * qj - ql) / (1 - pp) ' This is actually redundant (along with anything depending on it.)
73.         IF ((alphaj > Segments(1).alpha1) AND (alphaj < Segments(1).alpha2)) THEN
74.             IF ((alphal > Segments(2).alpha1) AND (alphal < Segments(2).alpha2)) THEN
75.                 CALL ccircle(Segments(1).b.x + alphaj * Segments(1).t.x, Segments(1).b.y + alphaj * Segments(1).t.y, 5, 15)
76.                 CALL ccircle(Segments(2).b.x + alphal * Segments(2).t.x, Segments(2).b.y + alphal * Segments(2).t.y, 5, 15)
77.             END IF
78.         END IF
79.     ELSE
80.         ' Parallel case.
81.     END IF
82.     '''
83.  
84.     _DISPLAY
85.     _LIMIT 60
86. LOOP
87.  
88. END
89.  
90. SUB CalcLine (i AS INTEGER)
91.     Segments(i).t.x = COS(Segments(i).ang)
92.     Segments(i).t.y = SIN(Segments(i).ang)
93.     Segments(i).p1.x = Segments(i).b.x + Segments(i).alpha1 * Segments(i).t.x
94.     Segments(i).p1.y = Segments(i).b.y + Segments(i).alpha1 * Segments(i).t.y
95.     Segments(i).p2.x = Segments(i).b.x + Segments(i).alpha2 * Segments(i).t.x
96.     Segments(i).p2.y = Segments(i).b.y + Segments(i).alpha2 * Segments(i).t.y
97. END SUB
98.  
99. FUNCTION DotProduct (a AS Vector, b AS Vector)
100.     DotProduct = a.x * b.x + a.y * b.y
101. END FUNCTION
102.  
103. SUB cline (x1 AS DOUBLE, y1 AS DOUBLE, x2 AS DOUBLE, y2 AS DOUBLE, col AS _UNSIGNED LONG)
104.     LINE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2)-(_WIDTH / 2 + x2, -y2 + _HEIGHT / 2), col
105. END SUB
106.  
107. SUB ccircle (x1 AS DOUBLE, y1 AS DOUBLE, rad AS DOUBLE, col AS _UNSIGNED LONG)
108.     CIRCLE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), rad, col
109. END SUB
110.  
111. SUB cpset (x1 AS DOUBLE, y1 AS DOUBLE, col AS _UNSIGNED LONG)
112.     PSET (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col
113. END SUB
114.  
115. SUB cpaint (x1 AS DOUBLE, y1 AS DOUBLE, col1 AS _UNSIGNED LONG, col2 AS _UNSIGNED LONG)
116.     PAINT (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col1, col2
117. END SUB
118.  
119. SUB cprintstring (y AS DOUBLE, a AS STRING)
120.     _PRINTSTRING (_WIDTH / 2 - (LEN(a) * 8) / 2, -y + _HEIGHT / 2), a
121. END SUB
122.  

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 17, 2020, 10:41:21 pm

Dang I had intersections done in the first OP, that's easy. Find when and where they overlap (on the same line) too, draw that line segment. That was like 75% of my subroutine and 90% of my time. That's what TempodiBasic pointed out.

Dang but those lines looked sharp and clean, oh it's the angle.

Here is the challenging case (that I have solved) determine if 2 line segments are sitting on the same line or do they lay on different lines that intersect, if they overlap, say the 2 endpoints that contain the overlap, if they intersect say the intersect point, or say they neither intersect nor overlap.

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 17, 2020, 11:31:44 pm

You got it man - I swear next time I sit down I'll finish my math up there - it'll stay tight, promise.

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 18, 2020, 12:32:28 am

Oh rats and nutz and worse@!

Turns out all I really needed was intersect, at least with completely random triangles. It is rare occasion two line segments actually do line up on exact line. Here is basically what I was going after, and intersect handles it nicely:

Code: QB64: [Select]

1. _TITLE "Two Triangles Overlap is Outlined in White dots" 'b+ 2020-03-18
2. ' Just worked Rosetta Code for Line Intersect Line
3. ' but what if we want to know if two line segments intersect?
4. '2020-03-14 "Two Line Segments Intersect" 'b+ 2020-03-14  start
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. '2020-03-16 "Segments Intersect mod tester"  >>> just post testing code
13. 'mod tester for 2 segments of vertical line and found I need to add more parameters to
14. ' FUNCTION twoLineSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
15. ' mod that name and parameters to:
16. ' FUNCTION twoSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1, ix2, iy2)
17.  
18. '2020-03-16 Segments Intersect revised 2020-03-16
19. ' OK now get the new FUNCTION working
20. ' ah! I had to tighten down D from >.2 to >.05 but loosen y-axis intersect
21.  
22. '2020-03-18 apply routines to two triangles
23. ' modified FUNCTION twoSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1)
24. ' to do only intersect. This code proved, Segments Intersect revised 2020-03-16, was faulty.
25.  
26. CONST xmax = 800, ymax = 600
27. SCREEN _NEWIMAGE(xmax, ymax, 32)
28. _DELAY .25
29. _SCREENMOVE _MIDDLE
30. DIM ax1 AS INTEGER, ax2 AS INTEGER, ay1 AS INTEGER, ay2 AS INTEGER, ax3 AS INTEGER, ay3 AS INTEGER
31. DIM bx1 AS INTEGER, bx2 AS INTEGER, by1 AS INTEGER, by2 AS INTEGER, bx3 AS INTEGER, by3 AS INTEGER
32. DO
33.     ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 20) * RND + 10
34.     ax2 = (xmax - 20) * RND + 10: ay2 = (ymax - 20) * RND + 10
35.     ax3 = (xmax - 20) * RND + 10: ay3 = (ymax - 20) * RND + 10
36.     bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 20) * RND + 10
37.     bx2 = (xmax - 20) * RND + 10: by2 = (ymax - 20) * RND + 10
38.     bx3 = (xmax - 20) * RND + 10: by3 = (ymax - 20) * RND + 10
39.     'tri a
40.     LINE (ax1, ay1)-(ax2, ay2), &HFFFF0000
41.     LINE (ax2, ay2)-(ax3, ay3), &HFFFF0000
42.     LINE (ax3, ay3)-(ax1, ay1), &HFFFF0000
43.     'tri b
44.     LINE (bx1, by1)-(bx2, by2), &HFF0000FF
45.     LINE (bx2, by2)-(bx3, by3), &HFF0000FF
46.     LINE (bx3, by3)-(bx1, by1), &HFF0000FF
47.  
48.     dista2a3 = _HYPOT(ax2 - ax3, ay2 - ay3)
49.     adx = (ax3 - ax2) / dista2a3: ady = (ay3 - ay2) / dista2a3
50.     distb2b3 = _HYPOT(bx2 - bx3, by2 - by3)
51.     bdx = (bx3 - bx2) / distb2b3: bdy = (by3 - by2) / distb2b3
52.  
53.     FOR i = 0 TO dista2a3
54.         x1 = ax2 + adx * i: y1 = ay2 + ady * i
55.         sect = twoSegmentsIntersect%(ax1, ay1, x1, y1, bx1, by1, bx2, by2, ix1, iy1)
56.         IF sect THEN PSET (ix1, iy1)
57.         sect = twoSegmentsIntersect%(ax1, ay1, x1, y1, bx3, by3, bx2, by2, ix1, iy1)
58.         IF sect THEN PSET (ix1, iy1)
59.         sect = twoSegmentsIntersect%(ax1, ay1, x1, y1, bx1, by1, bx3, by3, ix1, iy1)
60.         IF sect = 1 THEN PSET (ix1, iy1)
61.     NEXT
62.  
63.     FOR i = 0 TO distb2b3
64.         x1 = bx2 + bdx * i: y1 = by2 + bdy * i
65.         sect = twoSegmentsIntersect%(bx1, by1, x1, y1, ax1, ay1, ax2, ay2, ix1, iy1)
66.         IF sect = 1 THEN PSET (ix1, iy1)
67.         sect = twoSegmentsIntersect%(bx1, by1, x1, y1, ax3, ay3, ax2, ay2, ix1, iy1)
68.         IF sect THEN PSET (ix1, iy1)
69.         sect = twoSegmentsIntersect%(bx1, by1, x1, y1, ax1, ay1, ax3, ay3, ix1, iy1)
70.         IF sect = 1 THEN PSET (ix1, iy1)
71.     NEXT
72.  
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. END SUB
83.  
84. ' ======================================== end tester code functions ======================================
85.  
86. 'This function needs: FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
87. ' which in turn needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
88. FUNCTION twoSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1)
89.     intersect = lineIntersectLine%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
90.     IF ax1 < ax2 THEN aMinX = ax1: aMaxX = ax2 ELSE aMinX = ax2: aMaxX = ax1
91.     IF ay1 < ay2 THEN aMinY = ay1: aMaxY = ay2 ELSE aMinY = ay2: aMaxY = ay1
92.     IF bx1 < bx2 THEN bMinX = bx1: bMaxX = bx2 ELSE bMinX = bx2: bMaxX = bx1
93.     IF by1 < by2 THEN bMinY = by1: bMaxY = by2 ELSE bMinY = by2: bMaxY = by1
94.     IF intersect = 0 THEN 'no  intersect
95.         twoSegmentsIntersect% = 0
96.     ELSEIF intersect = 1 THEN 'segments intersect at one point
97.         IF ax1 = ax2 THEN 'is iy between
98.             IF iy < aMinY OR iy > aMaxY OR ix < bMinX OR ix > bMaxX THEN
99.                 twoSegmentsIntersect% = 0
100.             ELSE
101.                 ix1 = ix: iy1 = iy: twoSegmentsIntersect% = 1
102.             END IF
103.         ELSEIF bx1 = bx2 THEN
104.             IF iy < bMinY OR iy > bMaxY OR ix < aMinX OR ix > aMaxX THEN
105.                 twoSegmentsIntersect% = 0
106.             ELSE
107.                 ix1 = ix: iy1 = iy: twoSegmentsIntersect% = 1
108.             END IF
109.         ELSE
110.             IF (aMinX <= ix AND ix <= aMaxX) AND (bMinX <= ix AND ix <= bMaxX) THEN
111.                 ix1 = ix: iy1 = iy: twoSegmentsIntersect% = 1
112.             END IF
113.         END IF
114.     END IF
115. END FUNCTION
116.  
117. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
118. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
119.     IF ax1 = ax2 THEN 'line a is vertical
120.         IF bx1 = bx2 THEN ' b is vertical
121.             IF ax1 = bx1 THEN lineIntersectLine% = -1 ' if x's are same it is same vertical line
122.             EXIT FUNCTION '
123.         ELSE
124.             ix = ax1
125.             slopeYintersect bx1, by1, bx2, by2, m2, y02
126.             iy = m2 * ix + y02
127.             lineIntersectLine% = 1 'signal a point was found
128.             EXIT FUNCTION
129.         END IF
130.     ELSE
131.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
132.     END IF
133.     IF bx1 = bx2 THEN 'b is vertical
134.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = 1 'signal a point was found
135.         EXIT FUNCTION
136.     ELSE
137.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
138.     END IF
139.     d = -m1 - -m2 ' if = 0 then parallel or equal because slopes are same
140.     IF d THEN 'otherwise about 0 <<< tighten down from .2 to .05
141.         ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
142.         lineIntersectLine% = 1 'signal one intersect point was found
143.     END IF
144. END FUNCTION
145.  

  [ This attachment cannot be displayed inline in 'Print Page' view ]  

Using the overlap signal from the code in Best Answer was getting some really screwy lines, messing up the outlines way, way more than helping with anything. Phooey all that effort... oh well.

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 18, 2020, 07:26:51 am

Alrighty - so I'm (in a rush as usual) trying to piece together if there are any remaining questions. Would you say this question is fully cooked now? FWIW the intersection calculations are way simpler with vectors, and only one IF statement is technically needed. (The two CIRCLE statements put two copies of the same circle in the same place so this code can basically be cut in half again for the minimalist approach.)

Code: QB64: [Select]

1.     DIM db AS Vector
2.     db.x = Segments(2).b.x - Segments(1).b.x
3.     db.y = Segments(2).b.y - Segments(1).b.y
4.     qj = DotProduct(db, Segments(1).t)
5.     ql = DotProduct(db, Segments(2).t)
6.     p = DotProduct(Segments(1).t, Segments(2).t)
7.     pp = p * p
8.     IF (pp < 1) THEN
9.         alphaj = (qj - p * ql) / (1 - pp)
10.         alphal = (p * qj - ql) / (1 - pp) ' This is actually redundant (along with anything depending on it.)
11.         IF ((alphaj > Segments(1).alpha1) AND (alphaj < Segments(1).alpha2)) THEN
12.             IF ((alphal > Segments(2).alpha1) AND (alphal < Segments(2).alpha2)) THEN
13.                 CALL ccircle(Segments(1).b.x + alphaj * Segments(1).t.x, Segments(1).b.y + alphaj * Segments(1).t.y, 5, 15)
14.                 CALL ccircle(Segments(2).b.x + alphal * Segments(2).t.x, Segments(2).b.y + alphal * Segments(2).t.y, 5, 15)
15.             END IF
16.         END IF
17.     ELSE
18.         ' Parallel case.
19.     END IF

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 18, 2020, 11:05:51 am

Quote from: STxAxTIC on March 18, 2020, 07:26:51 am

Alrighty - so I'm (in a rush as usual) trying to piece together if there are any remaining questions. Would you say this question is fully cooked now? FWIW the intersection calculations are way simpler with vectors, and only one IF statement is technically needed. (The two CIRCLE statements put two copies of the same circle in the same place so this code can basically be cut in half again for the minimalist approach.)

Code: QB64: [Select]

1.     DIM db AS Vector
2.     db.x = Segments(2).b.x - Segments(1).b.x
3.     db.y = Segments(2).b.y - Segments(1).b.y
4.     qj = DotProduct(db, Segments(1).t)
5.     ql = DotProduct(db, Segments(2).t)
6.     p = DotProduct(Segments(1).t, Segments(2).t)
7.     pp = p * p
8.     IF (pp < 1) THEN
9.         alphaj = (qj - p * ql) / (1 - pp)
10.         alphal = (p * qj - ql) / (1 - pp) ' This is actually redundant (along with anything depending on it.)
11.         IF ((alphaj > Segments(1).alpha1) AND (alphaj < Segments(1).alpha2)) THEN
12.             IF ((alphal > Segments(2).alpha1) AND (alphal < Segments(2).alpha2)) THEN
13.                 CALL ccircle(Segments(1).b.x + alphaj * Segments(1).t.x, Segments(1).b.y + alphaj * Segments(1).t.y, 5, 15)
14.                 CALL ccircle(Segments(2).b.x + alphal * Segments(2).t.x, Segments(2).b.y + alphal * Segments(2).t.y, 5, 15)
15.             END IF
16.         END IF
17.     ELSE
18.         ' Parallel case.
19.     END IF

If you put your code into a sub routine (SUB or FUNCTION) I will test it in my code tester app but your "simple" thing has need of two Types at least and at least 2 supplemental helper routines, maybe just one DotProduct (and how many supplements might that have?) because I am NOT looking for drawing, just a FUNCTION that returns True if there is an Intersect and gives the intersect point (ix, iy) say.

If you can by-pass the case of vertical lines when the Determinate = 0 without more code to cover that case I am all eyes because that's what takes up the majority of my Intersect FUNCTION.

Hmm... if just going for Intersect maybe I can combine LineIntersect with SegmentIntersect but seems both might come in handy in app.

What's your DotProduct Function, I might be able to put it all together in a tester. I will call my Point Type XY and segments will just be two points. BUT first guarantee you have vertical line cases covered ;-))

Not cooked at all! Nobody has tested another's code and approved. The code I have quoted above is obviously pulled out of some other context and is incomplete to run.


Update: Oh I see the context! (Reply #24) from first code, OK I will work up test for my own satisfaction anyway. ;)

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 18, 2020, 11:30:55 am

Sorry my posting context has been so fleeting - my usual verboseness is missing.

So I define lines as a parameterized vector:

vec(y) = vec(b) + alpha * hat(t)

Where vec(y) is any location on the line, vec(b) is the lines origin, alpha is a dimensionless parameter that scales the lines unit tangent vector, vec(t). You can see where I convert this to XY coordinates in a sub.

As for multiple alignments, etc etc - it's all very easy in this framework. The simple question of intersections simply solves vec(y_a) = vec(y_b) for two lines a and b.

Will make nice notes on it in time. Lemme know where the cutting edge is, I'll try to keep near you.

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 18, 2020, 02:00:19 pm

For two overlapping triangles, I think I know how to cover the case should 2 line segments line up perfect PLUS make the entire outline better. But if the triangle should overlap along 2 sides... ;-))

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 18, 2020, 02:15:46 pm

Oh god let's not talk about triangles yet. Are we onto that though? Lines are done?

Title: Re: Intersect of 2 lines carried a step further
Post by: TempodiBasic on March 18, 2020, 03:34:10 pm

great geometry knowledge!

Quote

But if the triangle should overlap along 2 sides... ;-))

https://it.wikipedia.org/wiki/Criteri_di_congruenza_dei_triangoli (https://it.wikipedia.org/wiki/Criteri_di_congruenza_dei_triangoli)
https://www.youtube.com/watch?v=xaXV-RVpXgo (https://www.youtube.com/watch?v=xaXV-RVpXgo)

Math & Logic can be useful

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 18, 2020, 03:47:40 pm

Quote from: STxAxTIC on March 18, 2020, 02:15:46 pm

Oh god let's not talk about triangles yet. Are we onto that though? Lines are done?

Ha! my plan from the start was to use this segment intersect stuff to do overlapping triangles. It's what got me started on this segment intersect adventure in the first place.
https://www.qb64.org/forum/index.php?topic=2342.msg115768#msg115768

Quote

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.

and here you see I am succeeding! with only LineSegmentIntersect
https://www.qb64.org/forum/index.php?topic=2342.msg115824#msg115824

Title: Re: Intersect of 2 lines carried a step further
Post by: TempodiBasic on March 18, 2020, 04:44:18 pm

Great Bplus...
and I may see another application of your code .... in a graphic world... let's think to a 3D engine with _Maptriangle....
in perspective is it possible?

Thanks  to read

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 18, 2020, 05:03:14 pm

Here is even better demo of Outlining Overlapping Triangles. It does everything I wanted it to do, beautiful!

Code: QB64: [Select]

1. _TITLE "Two Triangles Overlap is Outlined in White dots" 'b+ 2020-03-18
2. ' Just worked Rosetta Code for Line Intersect Line
3. ' but what if we want to know if two line segments intersect?
4. '2020-03-14 "Two Line Segments Intersect" 'b+ 2020-03-14  start
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. '2020-03-16 "Segments Intersect mod tester"  >>> just post testing code
13. 'mod tester for 2 segments of vertical line and found I need to add more parameters to
14. ' FUNCTION twoLineSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
15. ' mod that name and parameters to:
16. ' FUNCTION twoSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1, ix2, iy2)
17.  
18. '2020-03-16 Segments Intersect revised 2020-03-16
19. ' OK now get the new FUNCTION working
20. ' ah! I had to tighten down D from >.2 to >.05 but loosen y-axis intersect
21.  
22. '2020-03-18 apply routines to two triangles
23. ' modified FUNCTION twoSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1)
24. ' to do only intersect. This code proved, Segments Intersect revised 2020-03-16, was faulty.
25.  
26. '2020-03-18 a more exactling test of triangle overlaps with line segments over lapping
27. ' purposely to the random triangles already tested and working well.
28.  
29.  
30. CONST xmax = 800, ymax = 600
31. SCREEN _NEWIMAGE(xmax, ymax, 32)
32. _DELAY .25
33. _SCREENMOVE _MIDDLE
34. DIM ax1 AS INTEGER, ax2 AS INTEGER, ay1 AS INTEGER, ay2 AS INTEGER, ax3 AS INTEGER, ay3 AS INTEGER
35. DIM bx1 AS INTEGER, bx2 AS INTEGER, by1 AS INTEGER, by2 AS INTEGER, bx3 AS INTEGER, by3 AS INTEGER
36.  
37. DO 'main testing loop sets up two triangles to test overlap area
38.     lCnt = lCnt + 1 'loop counter to control some purposeful test triangles
39.     IF lCnt MOD 4 = 0 THEN 'purpose overlap vertical lines
40.         cText 400, 580, 32, &HFF0088FF, "Two Triangles with Common Vertical Segment"
41.         ax1 = 400: ay1 = 20
42.         ax2 = 400: ay2 = 570
43.         ax3 = (xmax - 20) * RND + 10: ay3 = (ymax - 20) * RND + 10
44.         bx1 = 400: by1 = 200
45.         bx2 = 400: by2 = 450
46.         bx3 = (xmax - 20) * RND + 10: by3 = (ymax - 20) * RND + 10
47.  
48.     ELSEIF lCnt MOD 4 = 1 THEN 'purpose overlap horizontal line
49.         cText 400, 580, 32, &HFF008800, "Two Triangles with Common Horizontal Segment"
50.         ax1 = 10: ay1 = 300
51.         ax2 = 400: ay2 = 300
52.         ax3 = (xmax - 20) * RND + 10: ay3 = (ymax - 20) * RND + 10
53.         bx1 = 125: by1 = 300
54.         bx2 = 700: by2 = 300
55.         bx3 = (xmax - 20) * RND + 10: by3 = by3 = (ymax - 20) * RND + 10
56.  
57.     ELSEIF lCnt MOD 4 = 2 THEN 'purpose overlap 1/5 triangle
58.         cText 400, 580, 32, &HFFFF8800, "Two Triangles with Common 45 Degree Segment"
59.         ax1 = 100: ay1 = 100
60.         ax2 = 400: ay2 = 400
61.         ax3 = (xmax - 20) * RND + 10: ay3 = (ymax - 20) * RND + 10
62.         bx1 = 50: by1 = 50
63.         bx2 = 500: by2 = 500
64.         bx3 = (xmax - 20) * RND + 10: by3 = (ymax - 20) * RND + 10
65.  
66.     ELSEIF lCnt MOD 4 = 3 THEN ' completely random triangles
67.         cText 400, 580, 32,  &HFF0000FF, "Two Completely Random Triangles"
68.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 20) * RND + 10
69.         ax2 = (xmax - 20) * RND + 10: ay2 = (ymax - 20) * RND + 10
70.         ax3 = (xmax - 20) * RND + 10: ay3 = (ymax - 20) * RND + 10
71.         bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 20) * RND + 10
72.         bx2 = (xmax - 20) * RND + 10: by2 = (ymax - 20) * RND + 10
73.         bx3 = (xmax - 20) * RND + 10: by3 = (ymax - 20) * RND + 10
74.     END IF
75.     'tri a
76.     LINE (ax1, ay1)-(ax2, ay2), &HFFFF0000
77.     LINE (ax2, ay2)-(ax3, ay3), &HFFFF0000
78.     LINE (ax3, ay3)-(ax1, ay1), &HFFFF0000
79.     'tri b
80.     LINE (bx1, by1)-(bx2, by2), &HFF0000FF
81.     LINE (bx2, by2)-(bx3, by3), &HFF0000FF
82.     LINE (bx3, by3)-(bx1, by1), &HFF0000FF
83.  
84.     dista2a3 = _HYPOT(ax2 - ax3, ay2 - ay3)
85.     adx = (ax3 - ax2) / dista2a3: ady = (ay3 - ay2) / dista2a3
86.     FOR i = 0 TO dista2a3
87.         x1 = ax2 + adx * i: y1 = ay2 + ady * i
88.         sect = twoSegmentsIntersect%(ax1, ay1, x1, y1, bx1, by1, bx2, by2, ix1, iy1)
89.         IF sect THEN PSET (ix1, iy1)
90.         sect = twoSegmentsIntersect%(ax1, ay1, x1, y1, bx3, by3, bx2, by2, ix1, iy1)
91.         IF sect THEN PSET (ix1, iy1)
92.         sect = twoSegmentsIntersect%(ax1, ay1, x1, y1, bx1, by1, bx3, by3, ix1, iy1)
93.         IF sect = 1 THEN PSET (ix1, iy1)
94.     NEXT
95.  
96.     dista1a3 = _HYPOT(ax1 - ax3, ay1 - ay3)
97.     adx = (ax3 - ax1) / dista1a3: ady = (ay3 - ay1) / dista1a3
98.     FOR i = 0 TO dista1a3
99.         x1 = ax1 + adx * i: y1 = ay1 + ady * i
100.         sect = twoSegmentsIntersect%(ax2, ay2, x1, y1, bx1, by1, bx2, by2, ix1, iy1)
101.         IF sect THEN PSET (ix1, iy1)
102.         sect = twoSegmentsIntersect%(ax2, ay2, x1, y1, bx3, by3, bx2, by2, ix1, iy1)
103.         IF sect THEN PSET (ix1, iy1)
104.         sect = twoSegmentsIntersect%(ax2, ay2, x1, y1, bx1, by1, bx3, by3, ix1, iy1)
105.         IF sect = 1 THEN PSET (ix1, iy1)
106.     NEXT
107.  
108.     dista1a2 = _HYPOT(ax1 - ax2, ay1 - ay2)
109.     adx = (ax2 - ax1) / dista1a2: ady = (ay2 - ay1) / dista1a2
110.     FOR i = 0 TO dista1a2
111.         x1 = ax1 + adx * i: y1 = ay1 + ady * i
112.         sect = twoSegmentsIntersect%(ax3, ay3, x1, y1, bx1, by1, bx2, by2, ix1, iy1)
113.         IF sect THEN PSET (ix1, iy1)
114.         sect = twoSegmentsIntersect%(ax3, ay3, x1, y1, bx3, by3, bx2, by2, ix1, iy1)
115.         IF sect THEN PSET (ix1, iy1)
116.         sect = twoSegmentsIntersect%(ax3, ay3, x1, y1, bx1, by1, bx3, by3, ix1, iy1)
117.         IF sect = 1 THEN PSET (ix1, iy1)
118.     NEXT
119.  
120.     distb2b3 = _HYPOT(bx2 - bx3, by2 - by3)
121.     bdx = (bx3 - bx2) / distb2b3: bdy = (by3 - by2) / distb2b3
122.     FOR i = 0 TO distb2b3
123.         x1 = bx2 + bdx * i: y1 = by2 + bdy * i
124.         sect = twoSegmentsIntersect%(bx1, by1, x1, y1, ax1, ay1, ax2, ay2, ix1, iy1)
125.         IF sect = 1 THEN PSET (ix1, iy1)
126.         sect = twoSegmentsIntersect%(bx1, by1, x1, y1, ax3, ay3, ax2, ay2, ix1, iy1)
127.         IF sect THEN PSET (ix1, iy1)
128.         sect = twoSegmentsIntersect%(bx1, by1, x1, y1, ax1, ay1, ax3, ay3, ix1, iy1)
129.         IF sect = 1 THEN PSET (ix1, iy1)
130.     NEXT
131.  
132.     distb1b3 = _HYPOT(bx1 - bx3, by1 - by3)
133.     bdx = (bx3 - bx1) / distb1b3: bdy = (by3 - by1) / distb1b3
134.     FOR i = 0 TO distb1b3
135.         x1 = bx1 + bdx * i: y1 = by1 + bdy * i
136.         sect = twoSegmentsIntersect%(bx2, by2, x1, y1, ax1, ay1, ax2, ay2, ix1, iy1)
137.         IF sect THEN PSET (ix1, iy1)
138.         sect = twoSegmentsIntersect%(bx2, by2, x1, y1, ax3, ay3, ax2, ay2, ix1, iy1)
139.         IF sect THEN PSET (ix1, iy1)
140.         sect = twoSegmentsIntersect%(bx2, by2, x1, y1, ax1, ay1, ax3, ay3, ix1, iy1)
141.         IF sect = 1 THEN PSET (ix1, iy1)
142.     NEXT
143.  
144.     distb1b2 = _HYPOT(bx1 - bx2, by1 - by2)
145.     bdx = (bx2 - bx1) / distb1b2: bdy = (by2 - by1) / distb1b2
146.     FOR i = 0 TO distb1b2
147.         x1 = bx1 + bdx * i: y1 = by1 + bdy * i
148.         sect = twoSegmentsIntersect%(bx3, by3, x1, y1, ax1, ay1, ax2, ay2, ix1, iy1)
149.         IF sect THEN PSET (ix1, iy1)
150.         sect = twoSegmentsIntersect%(bx3, by3, x1, y1, ax3, ay3, ax2, ay2, ix1, iy1)
151.         IF sect THEN PSET (ix1, iy1)
152.         sect = twoSegmentsIntersect%(bx3, by3, x1, y1, ax1, ay1, ax3, ay3, ix1, iy1)
153.         IF sect = 1 THEN PSET (ix1, iy1)
154.     NEXT
155.  
156.     INPUT "Press enter for another demo, any + enter to quit...", again$
157.     CLS
158. LOOP UNTIL LEN(again$)
159.  
160. 'Slope and Y-intersect for non vertical lines,
161. ' if x1 = x2 the line is vertical don't call this sub
162. ' because slope calculation would cause division by 0 error.
163. SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
164.     slope = (Y2 - Y1) / (X2 - X1): Yintercept = slope * (0 - X1) + Y1
165. END SUB
166.  
167. ' ======================================== end tester code functions ======================================
168.  
169. 'This function needs: FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
170. ' which in turn needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept) 'check x1 <> x2 first!
171. FUNCTION twoSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1)
172.     intersect = lineIntersectLine%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
173.     IF ax1 < ax2 THEN aMinX = ax1: aMaxX = ax2 ELSE aMinX = ax2: aMaxX = ax1
174.     IF ay1 < ay2 THEN aMinY = ay1: aMaxY = ay2 ELSE aMinY = ay2: aMaxY = ay1
175.     IF bx1 < bx2 THEN bMinX = bx1: bMaxX = bx2 ELSE bMinX = bx2: bMaxX = bx1
176.     IF by1 < by2 THEN bMinY = by1: bMaxY = by2 ELSE bMinY = by2: bMaxY = by1
177.     IF intersect = 0 THEN 'no  intersect
178.         twoSegmentsIntersect% = 0
179.     ELSEIF intersect = 1 THEN 'segments intersect at one point
180.         IF ax1 = ax2 THEN 'is iy between
181.             IF iy < aMinY OR iy > aMaxY OR ix < bMinX OR ix > bMaxX THEN
182.                 twoSegmentsIntersect% = 0
183.             ELSE
184.                 ix1 = ix: iy1 = iy: twoSegmentsIntersect% = 1
185.             END IF
186.         ELSEIF bx1 = bx2 THEN
187.             IF iy < bMinY OR iy > bMaxY OR ix < aMinX OR ix > aMaxX THEN
188.                 twoSegmentsIntersect% = 0
189.             ELSE
190.                 ix1 = ix: iy1 = iy: twoSegmentsIntersect% = 1
191.             END IF
192.         ELSE
193.             IF (aMinX <= ix AND ix <= aMaxX) AND (bMinX <= ix AND ix <= bMaxX) THEN
194.                 ix1 = ix: iy1 = iy: twoSegmentsIntersect% = 1
195.             END IF
196.         END IF
197.     END IF
198. END FUNCTION
199.  
200. ' this function needs: SUB slopeYintersect (X1, Y1, X2, Y2, slope, Yintercept)
201. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
202.     IF ax1 = ax2 THEN 'line a is vertical
203.         IF bx1 = bx2 THEN ' b is vertical
204.             IF ax1 = bx1 THEN lineIntersectLine% = -1 ' if x's are same it is same vertical line
205.             EXIT FUNCTION '
206.         ELSE
207.             ix = ax1
208.             slopeYintersect bx1, by1, bx2, by2, m2, y02
209.             iy = m2 * ix + y02
210.             lineIntersectLine% = 1 'signal a point was found
211.             EXIT FUNCTION
212.         END IF
213.     ELSE
214.         slopeYintersect ax1, ay1, ax2, ay2, m1, y01 ' -m = a, 1 = b, y0 = c  std form
215.     END IF
216.     IF bx1 = bx2 THEN 'b is vertical
217.         ix = bx1: iy = m1 * ix + y01: lineIntersectLine% = 1 'signal a point was found
218.         EXIT FUNCTION
219.     ELSE
220.         slopeYintersect bx1, by1, bx2, by2, m2, y02 ' -m = a, 1 = b, y0 = c  std form
221.     END IF
222.     d = -m1 - -m2 ' if = 0 then parallel or equal because slopes are same
223.     IF d THEN 'otherwise about 0 <<< tighten down from .2 to .05
224.         ix = (y01 - y02) / d: iy = (-m1 * y02 - -m2 * y01) / d
225.         lineIntersectLine% = 1 'signal one intersect point was found
226.     END IF
227. END FUNCTION
228.  
229. 'center the text at x, y with given height and color
230. SUB cText (x, y, textHeight, K AS _UNSIGNED LONG, txt$)
231.     DIM fg AS _UNSIGNED LONG, cur&, I&, mult, xlen
232.     fg = _DEFAULTCOLOR
233.     'screen snapshot
234.     cur& = _DEST
235.     I& = _NEWIMAGE(8 * LEN(txt$), 16, 32)
236.     _DEST I&
237.     COLOR K, _RGBA32(0, 0, 0, 0)
238.     _PRINTSTRING (0, 0), txt$
239.     mult = textHeight / 16
240.     xlen = LEN(txt$) * 8 * mult
241.     _PUTIMAGE (x - .5 * xlen, y - .5 * textHeight)-STEP(xlen, textHeight), I&, cur&
242.     COLOR fg
243.     _FREEIMAGE I&
244. END SUB
245.  
246.  

 

It's taking about 60+ lines of code to figure intersect point of two line segments.

Title: Re: Intersect of 2 lines carried a step further
Post by: TempodiBasic on March 18, 2020, 08:52:05 pm

Very Impressive Bplus
  [ This attachment cannot be displayed inline in 'Print Page' view ]  
Thanks to share the code

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 21, 2020, 03:43:32 pm

Nice one bplus.

While I didn't bother with triangles, I wrote up the case of intersecting lines and wrote out the requirements for overlapping segments. Jst for academic completeness...

EDIT - removed third page - it was bullshit

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 21, 2020, 04:03:04 pm

Quote from: STxAxTIC on March 21, 2020, 03:43:32 pm

Nice one bplus.

While I didn't bother with triangles, I wrote up the case of intersecting lines and wrote out the requirements for overlapping segments. Jst for academic completeness...

Thanks STxAxTIC, you know I've a feeling your code is way shorter than mine and theoretically accomplish the same thing. It is so abstract for me, I couldn't translate it into something I could use for the app. If you wouldn't mind I'd prefer simple brevity of a Segment Intersect SUB set up as I have and returns True if Intersect with the ix, iy point named in value. Can it be written without the segment Type and maintain it's brevity? If I am asking you to commit a Physic's sin? pretend I never asked. :)

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 21, 2020, 04:07:12 pm

Aw man bplus no worries - I mean, these works really do accomplish the same thing, and my notation is undoubtedly stylized for the thick-skinned. My real thoughts on the matter are that you've got this ground covered. I hesitated to make the code into a sub because there are an ambiguous number of return values and QB64 is funny about that.

However - because the conversion from mine to yours is straightforward enough, I could easily work this into a SUB of some kind that returns the intersection points and flags perfect overlapping, or even overlapping to a threshold. I'll whip it up just so we have two floating around, but I get the sense you got there first 100% and I'm in your shadow on this one.

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 21, 2020, 04:21:29 pm

Quote from: STxAxTIC on March 21, 2020, 04:07:12 pm

Aw man bplus no worries - I mean, these works really do accomplish the same thing, and my notation is undoubtedly stylized for the thick-skinned. My real thoughts on the matter are that you've got this ground covered. I hesitated to make the code into a sub because there are an ambiguous number of return values and QB64 is funny about that.

However - because the conversion from mine to yours is straightforward enough, I could easily work this into a SUB of some kind that returns the intersection points and flags perfect overlapping, or even overlapping to a threshold. I'll whip it up just so we have two floating around, but I get the sense you got there first 100% and I'm in your shadow on this one.

Just a reminder, I've realized, at least for this particular application, I don't need to know about overlap, count that as 0 or false Intersect, please don't bother with that difficult case. Just a straight and simple intersect will do it for me for this.

For Bonus, you could try the overlap case too, I used -1 for overlap, 1 for Intersect, 0 for neither Intersect nor Overlap, but then you need 2 points and more tricky code. It's likely to come in handy down the line. I never did nail down overlap and this application proved it to me.

Those triangle overlaps are drawn only from tons of intersects.

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 21, 2020, 05:54:27 pm

Heya bplus,

So this code has the intersections and the overlaps perfectly calculated - the overlap threshold is set high for demo purposes. If you rotate the line with the mouse wheel you can see it in action.

Next thing would be to turn this into a SUB. Gonna let this cook for a minute before I change it again.

Code: QB64: [Select]

1. SCREEN 12
2.  
3. TYPE Vector
4.     x AS DOUBLE
5.     y AS DOUBLE
6. END TYPE
7.  
8. TYPE LineSegment
9.     b AS Vector
10.     alpha1 AS DOUBLE
11.     alpha2 AS DOUBLE
12.     ang AS DOUBLE
13.     t AS Vector
14.     p1 AS Vector
15.     p2 AS Vector
16. END TYPE
17.  
18. DIM SHARED Segments(2) AS LineSegment
19.  
20. Segments(1).b.x = 0
21. Segments(1).b.y = 0
22. Segments(1).alpha1 = -50
23. Segments(1).alpha2 = 50
24. Segments(1).ang = 0
25. CALL CalcLine(1)
26.  
27. Segments(2).b.x = 0
28. Segments(2).b.y = 50
29. Segments(2).alpha1 = -100
30. Segments(2).alpha2 = 100
31. Segments(2).ang = ATN(1)
32. CALL CalcLine(2)
33.  
34. DO
35.  
36.     DO WHILE _MOUSEINPUT
37.         x = _MOUSEX
38.         y = _MOUSEY
39.         IF ((x > 0) AND (x < _WIDTH) AND (y > 0) AND (y < _HEIGHT)) THEN
40.             IF _MOUSEBUTTON(1) THEN
41.                 x = _MOUSEX
42.                 y = _MOUSEY
43.                 Segments(1).b.x = (x - _WIDTH / 2)
44.                 Segments(1).b.y = (-y + _HEIGHT / 2)
45.                 CALL CalcLine(1)
46.             END IF
47.             IF _MOUSEWHEEL > 0 THEN
48.                 Segments(1).ang = Segments(1).ang + ATN(1) / 10
49.                 CALL CalcLine(1)
50.             END IF
51.             IF _MOUSEWHEEL < 0 THEN
52.                 Segments(1).ang = Segments(1).ang - ATN(1) / 10
53.                 CALL CalcLine(1)
54.             END IF
55.         END IF
56.     LOOP
57.  
58.     CLS
59.     CALL cline(Segments(1).p1.x, Segments(1).p1.y, Segments(1).p2.x, Segments(1).p2.y, 15)
60.     CALL cline(Segments(2).p1.x, Segments(2).p1.y, Segments(2).p2.x, Segments(2).p2.y, 14)
61.  
62.     ''' Intersection calculation
63.     DIM db AS Vector
64.     db.x = Segments(2).b.x - Segments(1).b.x
65.     db.y = Segments(2).b.y - Segments(1).b.y
66.     qj = DotProduct(db, Segments(1).t)
67.     ql = DotProduct(db, Segments(2).t)
68.     p = DotProduct(Segments(1).t, Segments(2).t)
69.     pp = p * p
70.     IF (pp < 1) THEN
71.         alphaj = (qj - p * ql) / (1 - pp)
72.         alphal = (p * qj - ql) / (1 - pp)
73.         IF ((alphaj > Segments(1).alpha1) AND (alphaj < Segments(1).alpha2)) THEN
74.             IF ((alphal > Segments(2).alpha1) AND (alphal < Segments(2).alpha2)) THEN
75.                 CALL ccircle(Segments(1).b.x + alphaj * Segments(1).t.x, Segments(1).b.y + alphaj * Segments(1).t.y, 3, 13)
76.                 CALL ccircle(Segments(2).b.x + alphal * Segments(2).t.x, Segments(2).b.y + alphal * Segments(2).t.y, 5, 15)
77.             END IF
78.         END IF
79.     ELSE ' Parallel case
80.         DIM dbhat AS Vector
81.         dbmag = SQR(db.x * db.x + db.y * db.y)
82.         dbhat.x = db.x / dbmag
83.         dbhat.y = db.y / dbmag
84.         thresh = DotProduct(dbhat, Segments(1).t)
85.         IF (1 - thresh * thresh < 0.01) THEN ' Overlap case
86.             t1t2 = DotProduct(Segments(1).t, Segments(2).t)
87.             alphaj1 = Segments(2).alpha1 * t1t2 + DotProduct(Segments(1).t, db)
88.             alphaj2 = Segments(2).alpha2 * t1t2 + DotProduct(Segments(1).t, db)
89.             IF ((alphaj1 > Segments(1).alpha1) AND (alphaj1 < Segments(1).alpha2)) THEN
90.                 CALL ccircle(Segments(1).b.x + alphaj1 * Segments(1).t.x, Segments(1).b.y + alphaj1 * Segments(1).t.y, 3, 13)
91.                 CALL ccircle(Segments(2).b.x + Segments(2).alpha1 * Segments(2).t.x, Segments(2).b.y + Segments(2).alpha1 * Segments(2).t.y, 4, 14)
92.             END IF
93.             IF ((alphaj2 > Segments(1).alpha1) AND (alphaj2 < Segments(1).alpha2)) THEN
94.                 CALL ccircle(Segments(1).b.x + alphaj2 * Segments(1).t.x, Segments(1).b.y + alphaj2 * Segments(1).t.y, 3, 13)
95.                 CALL ccircle(Segments(2).b.x + Segments(2).alpha2 * Segments(2).t.x, Segments(2).b.y + Segments(2).alpha2 * Segments(2).t.y, 4, 14)
96.             END IF
97.             alphal1 = Segments(1).alpha1 * t1t2 - DotProduct(Segments(2).t, db)
98.             alphal2 = Segments(1).alpha2 * t1t2 - DotProduct(Segments(2).t, db)
99.             IF ((alphal1 > Segments(2).alpha1) AND (alphal1 < Segments(2).alpha2)) THEN
100.                 CALL ccircle(Segments(2).b.x + alphal1 * Segments(2).t.x, Segments(2).b.y + alphal1 * Segments(2).t.y, 3, 13)
101.                 CALL ccircle(Segments(1).b.x + Segments(1).alpha1 * Segments(1).t.x, Segments(1).b.y + Segments(1).alpha1 * Segments(1).t.y, 5, 15)
102.             END IF
103.             IF ((alphal2 > Segments(2).alpha1) AND (alphal2 < Segments(2).alpha2)) THEN
104.                 CALL ccircle(Segments(2).b.x + alphal2 * Segments(2).t.x, Segments(2).b.y + alphal2 * Segments(2).t.y, 3, 13)
105.                 CALL ccircle(Segments(1).b.x + Segments(1).alpha2 * Segments(1).t.x, Segments(1).b.y + Segments(1).alpha2 * Segments(1).t.y, 5, 15)
106.             END IF
107.         END IF
108.     END IF
109.     '''
110.  
111.     _DISPLAY
112.     _LIMIT 60
113. LOOP
114.  
115. END
116.  
117. SUB CalcLine (i AS INTEGER)
118.     Segments(i).t.x = COS(Segments(i).ang)
119.     Segments(i).t.y = SIN(Segments(i).ang)
120.     Segments(i).p1.x = Segments(i).b.x + Segments(i).alpha1 * Segments(i).t.x
121.     Segments(i).p1.y = Segments(i).b.y + Segments(i).alpha1 * Segments(i).t.y
122.     Segments(i).p2.x = Segments(i).b.x + Segments(i).alpha2 * Segments(i).t.x
123.     Segments(i).p2.y = Segments(i).b.y + Segments(i).alpha2 * Segments(i).t.y
124. END SUB
125.  
126. FUNCTION DotProduct (a AS Vector, b AS Vector)
127.     DotProduct = a.x * b.x + a.y * b.y
128. END FUNCTION
129.  
130. SUB cline (x1 AS DOUBLE, y1 AS DOUBLE, x2 AS DOUBLE, y2 AS DOUBLE, col AS _UNSIGNED LONG)
131.     LINE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2)-(_WIDTH / 2 + x2, -y2 + _HEIGHT / 2), col
132. END SUB
133.  
134. SUB ccircle (x1 AS DOUBLE, y1 AS DOUBLE, rad AS DOUBLE, col AS _UNSIGNED LONG)
135.     CIRCLE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), rad, col
136. END SUB
137.  
138. SUB cpset (x1 AS DOUBLE, y1 AS DOUBLE, col AS _UNSIGNED LONG)
139.     PSET (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col
140. END SUB
141.  
142. SUB cpaint (x1 AS DOUBLE, y1 AS DOUBLE, col1 AS _UNSIGNED LONG, col2 AS _UNSIGNED LONG)
143.     PAINT (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col1, col2
144. END SUB
145.  
146. SUB cprintstring (y AS DOUBLE, a AS STRING)
147.     _PRINTSTRING (_WIDTH / 2 - (LEN(a) * 8) / 2, -y + _HEIGHT / 2), a
148. END SUB
149.  

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 22, 2020, 02:09:38 am

This version will do triangles and more. Detects all intersections *and* overlaps in all lines to an adjustable threshold. See screenshot

Code: QB64: [Select]

1. SCREEN 12
2.  
3. TYPE Vector
4.     x AS DOUBLE
5.     y AS DOUBLE
6. END TYPE
7.  
8. TYPE LineSegment
9.     b AS Vector
10.     alpha1 AS DOUBLE
11.     alpha2 AS DOUBLE
12.     ang AS DOUBLE
13.     t AS Vector
14.     p1 AS Vector
15.     p2 AS Vector
16. END TYPE
17.  
18. DIM SHARED Segments(100) AS LineSegment
19. DIM SHARED NumSegments AS INTEGER
20.  
21. NumSegments = 0
22.  
23. NumSegments = NumSegments + 1
24. Segments(NumSegments).b.x = 0
25. Segments(NumSegments).b.y = 0
26. Segments(NumSegments).alpha1 = -150
27. Segments(NumSegments).alpha2 = 150
28. Segments(NumSegments).ang = ATN(1)
29. CALL CalibrateLine(NumSegments)
30.  
31. NumSegments = NumSegments + 1
32. Segments(NumSegments).b.x = 0
33. Segments(NumSegments).b.y = 50
34. Segments(NumSegments).alpha1 = -100
35. Segments(NumSegments).alpha2 = 100
36. Segments(NumSegments).ang = ATN(1)
37. CALL CalibrateLine(NumSegments)
38.  
39. NumSegments = NumSegments + 1
40. Segments(NumSegments).b.x = 0
41. Segments(NumSegments).b.y = 50
42. Segments(NumSegments).alpha1 = -100
43. Segments(NumSegments).alpha2 = 100
44. Segments(NumSegments).ang = -ATN(1)
45. CALL CalibrateLine(NumSegments)
46.  
47. FOR k = 1 TO 15
48.     NumSegments = NumSegments + 1
49.     Segments(NumSegments).b.x = 1 * _WIDTH * (RND - .5)
50.     Segments(NumSegments).b.y = 1 * _HEIGHT * (RND - .5)
51.     Segments(NumSegments).alpha1 = -100 - RND * 100
52.     Segments(NumSegments).alpha2 = 100 + RND * 100
53.     Segments(NumSegments).ang = RND * 4 * ATN(1)
54.     CALL CalibrateLine(NumSegments)
55. NEXT
56.  
57. DO
58.  
59.     DO WHILE _MOUSEINPUT
60.         x = _MOUSEX
61.         y = _MOUSEY
62.         IF ((x > 0) AND (x < _WIDTH) AND (y > 0) AND (y < _HEIGHT)) THEN
63.             IF _MOUSEBUTTON(1) THEN
64.                 x = _MOUSEX
65.                 y = _MOUSEY
66.                 Segments(1).b.x = (x - _WIDTH / 2)
67.                 Segments(1).b.y = (-y + _HEIGHT / 2)
68.                 CALL CalibrateLine(1)
69.             END IF
70.             IF _MOUSEWHEEL > 0 THEN
71.                 Segments(1).ang = Segments(1).ang + ATN(1) / 10
72.                 CALL CalibrateLine(1)
73.             END IF
74.             IF _MOUSEWHEEL < 0 THEN
75.                 Segments(2).ang = Segments(2).ang + ATN(1) / 10
76.                 CALL CalibrateLine(2)
77.             END IF
78.         END IF
79.     LOOP
80.  
81.     CLS
82.     FOR k = 1 TO NumSegments
83.         CALL cline(Segments(k).p1.x, Segments(k).p1.y, Segments(k).p2.x, Segments(k).p2.y, 15)
84.     NEXT
85.  
86.     FOR k = 1 TO NumSegments
87.         FOR j = k + 1 TO NumSegments
88.  
89.             ''' Intersection calculation
90.             Seg1 = k
91.             Seg2 = j
92.  
93.             DIM db AS Vector
94.             db.x = Segments(Seg2).b.x - Segments(Seg1).b.x
95.             db.y = Segments(Seg2).b.y - Segments(Seg1).b.y
96.             qj = DotProduct(db, Segments(Seg1).t)
97.             ql = DotProduct(db, Segments(Seg2).t)
98.             p = DotProduct(Segments(Seg1).t, Segments(Seg2).t)
99.             pp = p * p
100.             IF (pp < 1) THEN ' Non-parallel case
101.                 alphaj = (qj - p * ql) / (1 - pp)
102.                 alphal = (p * qj - ql) / (1 - pp)
103.                 IF ((alphaj > Segments(Seg1).alpha1) AND (alphaj < Segments(Seg1).alpha2)) THEN
104.                     IF ((alphal > Segments(Seg2).alpha1) AND (alphal < Segments(Seg2).alpha2)) THEN
105.                         CALL ccircle(Segments(Seg1).b.x + alphaj * Segments(Seg1).t.x, Segments(Seg1).b.y + alphaj * Segments(Seg1).t.y, 3, 13)
106.                         CALL ccircle(Segments(Seg2).b.x + alphal * Segments(Seg2).t.x, Segments(Seg2).b.y + alphal * Segments(Seg2).t.y, 5, 15)
107.                     END IF
108.                 END IF
109.             ELSE ' Parallel case
110.                 DIM dbhat AS Vector
111.                 dbmag = SQR(db.x * db.x + db.y * db.y)
112.                 dbhat.x = db.x / dbmag
113.                 dbhat.y = db.y / dbmag
114.                 thresh = DotProduct(dbhat, Segments(Seg1).t)
115.                 IF (1 - thresh * thresh < 0.001) THEN ' Overlap case
116.                     t1t2 = DotProduct(Segments(Seg1).t, Segments(Seg2).t)
117.                     alphaj1 = Segments(Seg2).alpha1 * t1t2 + DotProduct(Segments(Seg1).t, db)
118.                     alphaj2 = Segments(Seg2).alpha2 * t1t2 + DotProduct(Segments(Seg1).t, db)
119.                     x1 = 0
120.                     y1 = 0
121.                     x2 = 0
122.                     y2 = 0
123.                     IF ((alphaj1 > Segments(Seg1).alpha1) AND (alphaj1 < Segments(Seg1).alpha2)) THEN
124.                         xx = Segments(Seg1).b.x + alphaj1 * Segments(Seg1).t.x
125.                         yy = Segments(Seg1).b.y + alphaj1 * Segments(Seg1).t.y
126.                         IF (x1 = 0) THEN x1 = xx ELSE x2 = xx
127.                         IF (y1 = 0) THEN y1 = yy ELSE y2 = yy
128.                         CALL ccircle(xx, yy, 3, 13)
129.                         'CALL ccircle(Segments(Seg2).b.x + Segments(Seg2).alpha1 * Segments(Seg2).t.x, Segments(Seg2).b.y + Segments(Seg2).alpha1 * Segments(Seg2).t.y, 4, 14)
130.                     END IF
131.                     IF ((alphaj2 > Segments(Seg1).alpha1) AND (alphaj2 < Segments(Seg1).alpha2)) THEN
132.                         xx = Segments(Seg1).b.x + alphaj2 * Segments(Seg1).t.x
133.                         yy = Segments(Seg1).b.y + alphaj2 * Segments(Seg1).t.y
134.                         IF (x1 = 0) THEN x1 = xx ELSE x2 = xx
135.                         IF (y1 = 0) THEN y1 = yy ELSE y2 = yy
136.                         CALL ccircle(xx, yy, 3, 13)
137.                         'CALL ccircle(Segments(Seg2).b.x + Segments(Seg2).alpha2 * Segments(Seg2).t.x, Segments(Seg2).b.y + Segments(Seg2).alpha2 * Segments(Seg2).t.y, 4, 14)
138.                     END IF
139.                     alphal1 = Segments(Seg1).alpha1 * t1t2 - DotProduct(Segments(Seg2).t, db)
140.                     alphal2 = Segments(Seg1).alpha2 * t1t2 - DotProduct(Segments(Seg2).t, db)
141.                     IF ((alphal1 > Segments(Seg2).alpha1) AND (alphal1 < Segments(Seg2).alpha2)) THEN
142.                         xx = Segments(Seg2).b.x + alphal1 * Segments(Seg2).t.x
143.                         yy = Segments(Seg2).b.y + alphal1 * Segments(Seg2).t.y
144.                         IF (x1 = 0) THEN x1 = xx ELSE x2 = xx
145.                         IF (y1 = 0) THEN y1 = yy ELSE y2 = yy
146.                         CALL ccircle(xx, yy, 3, 15)
147.                         'CALL ccircle(Segments(Seg1).b.x + Segments(Seg1).alpha1 * Segments(Seg1).t.x, Segments(Seg1).b.y + Segments(Seg1).alpha1 * Segments(Seg1).t.y, 5, 15)
148.                     END IF
149.                     IF ((alphal2 > Segments(Seg2).alpha1) AND (alphal2 < Segments(Seg2).alpha2)) THEN
150.                         xx = Segments(Seg2).b.x + alphal2 * Segments(Seg2).t.x
151.                         yy = Segments(Seg2).b.y + alphal2 * Segments(Seg2).t.y
152.                         IF (x1 = 0) THEN x1 = xx ELSE x2 = xx
153.                         IF (y1 = 0) THEN y1 = yy ELSE y2 = yy
154.                         CALL ccircle(xx, yy, 3, 15)
155.                         'CALL ccircle(Segments(Seg1).b.x + Segments(Seg1).alpha2 * Segments(Seg1).t.x, Segments(Seg1).b.y + Segments(Seg1).alpha2 * Segments(Seg1).t.y, 5, 15)
156.                     END IF
157.                     IF (x1 OR x2 OR y1 OR y2) THEN
158.                         CALL cline(x1, y1, x2, y2, 13)
159.                     END IF
160.                 END IF
161.             END IF
162.             '''
163.  
164.         NEXT
165.     NEXT
166.  
167.     _DISPLAY
168.     _LIMIT 60
169. LOOP
170.  
171. END
172.  
173. SUB CalibrateLine (i AS INTEGER)
174.     Segments(i).t.x = COS(Segments(i).ang)
175.     Segments(i).t.y = SIN(Segments(i).ang)
176.     Segments(i).p1.x = Segments(i).b.x + Segments(i).alpha1 * Segments(i).t.x
177.     Segments(i).p1.y = Segments(i).b.y + Segments(i).alpha1 * Segments(i).t.y
178.     Segments(i).p2.x = Segments(i).b.x + Segments(i).alpha2 * Segments(i).t.x
179.     Segments(i).p2.y = Segments(i).b.y + Segments(i).alpha2 * Segments(i).t.y
180. END SUB
181.  
182. FUNCTION DotProduct (a AS Vector, b AS Vector)
183.     DotProduct = a.x * b.x + a.y * b.y
184. END FUNCTION
185.  
186. SUB cline (x1 AS DOUBLE, y1 AS DOUBLE, x2 AS DOUBLE, y2 AS DOUBLE, col AS _UNSIGNED LONG)
187.     LINE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2)-(_WIDTH / 2 + x2, -y2 + _HEIGHT / 2), col
188. END SUB
189.  
190. SUB ccircle (x1 AS DOUBLE, y1 AS DOUBLE, rad AS DOUBLE, col AS _UNSIGNED LONG)
191.     CIRCLE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), rad, col
192. END SUB
193.  
194. SUB cpset (x1 AS DOUBLE, y1 AS DOUBLE, col AS _UNSIGNED LONG)
195.     PSET (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col
196. END SUB
197.  
198. SUB cpaint (x1 AS DOUBLE, y1 AS DOUBLE, col1 AS _UNSIGNED LONG, col2 AS _UNSIGNED LONG)
199.     PAINT (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col1, col2
200. END SUB
201.  
202. SUB cprintstring (y AS DOUBLE, a AS STRING)
203.     _PRINTSTRING (_WIDTH / 2 - (LEN(a) * 8) / 2, -y + _HEIGHT / 2), a
204. END SUB
205.  

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 22, 2020, 10:12:44 am

Well no segment intersect function in sight except from bplus. OK ;-))

OK Terry had one that said True or False for Intersect but does not name the point values.

OK Well I will take another crack at making a shorter one after snakeBrain.

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 22, 2020, 10:51:25 am

This can be made into a sub now that it's done, of course.

You gotta see where i was coming from though - to ask for a SUB before this milestone would be asking for premature optimization.

Now that we're on this, what kind of outputs do you want the sub to give? Just a true/false? Pish posh right? Because what about the actual intersection points?

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 22, 2020, 04:42:46 pm

Quote from: STxAxTIC on March 22, 2020, 10:51:25 am

This can be made into a sub now that it's done, of course.

You gotta see where i was coming from though - to ask for a SUB before this milestone would be asking for premature optimization.

Now that we're on this, what kind of outputs do you want the sub to give? Just a true/false? Pish posh right? Because what about the actual intersection points?

https://www.qb64.org/forum/index.php?topic=2342.msg115971#msg115971
https://www.qb64.org/forum/index.php?topic=2342.msg115974#msg115974

FUNCTION SegIntersect%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
Return True or -1 if intersect with i point at ix, iy
Return 0 if overlap or no intersect.

Purpose of sub as you've already figured out is for outlining intersect boundaries of 2D objects.

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 22, 2020, 04:52:36 pm

Yeah - I suppose we have to work around QB64 only outputting one thing per function. I can make this into a SUB prolly - but there may have to be some hacky helper functions.

The real problem arises from the overly cartesian mindset brought on by the QB64 coordinate system. Grumble grumble... get to work...

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 22, 2020, 05:09:20 pm

Quote from: STxAxTIC on March 22, 2020, 04:52:36 pm

Yeah - I suppose we have to work around QB64 only outputting one thing per function. I can make this into a SUB prolly - but there may have to be some hacky helper functions.

The real problem arises from the overly cartesian mindset brought on by the QB64 coordinate system. Grumble grumble... get to work...

Remember all parameters are passed by reference so what goes in still comes out SUB or FUNCTION and is available to main code (as long as you are careful with Type). I have 2 helpers total 67 lines, I'm thinking that can be beat easily. I have allot of code dealing with slopes when 0 is denominator, if you use Standard Form you might be able to get around that. QB64 coordinate system has no effect on the math, it's just one quadrant that's upside down in our subjective vision.

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 22, 2020, 05:12:47 pm

Quote from: bplus on March 22, 2020, 05:09:20 pm

QB64 coordinate system has no effect on the math, it's just one quadrant that's upside down in our subjective vision.

Deeply wrong sadly - the QB64 coordinate systems all violate the right hand rule. All depths must be thought of as negative depths (in screen). All cross products are backwards. All line integrals are backwards. Green's theorems become wonky. Everything sucks, it's counter intuitive, yall are simply used to it. I'm trying to drive home the fact that this isn't subjective - this isn't one of those things where my yellow is your green. The coordinate systems are objectively ill-chosen. But hey, what else is new in computing?

EDIT:

Not to mention, it makes Trig COMPLETELY UPSIDE DOWN and only helps to stifle the learning around here, trust me.

Title: Re: Intersect of 2 lines carried a step further
Post by: STxAxTIC on March 23, 2020, 06:26:28 am

Alrighty, here's about 90% of what you asked for. The intersection calculation sub takes endpoints as its inputs, but outputs nothing right now. I figure if you want it to return specific stuff, the road should be easy, very easy, to travel from here.

The Segments() array is still there, basically for show. The LineSegment UDT is crucial though. This code already became a mess doing what you asked - I wouldn't imagine doing this without vector notation.

Anyway, here's the compromise:

(Control it with the mouse)

Code: QB64: [Select]

1. SCREEN 12
2. RANDOMIZE TIMER
3.  
4. TYPE Vector
5.     x AS DOUBLE
6.     y AS DOUBLE
7. END TYPE
8.  
9. TYPE LineSegment
10.     '                  Endpoint definition:
11.     p1 AS Vector '     Endpoint 1
12.     p2 AS Vector '     Endpoint 2
13.     '                  Parameterized definition:
14.     b AS Vector '      Origin vector
15.     alpha1 AS DOUBLE ' End-parameter 1
16.     alpha2 AS DOUBLE ' End-parameter 2
17.     ang AS DOUBLE '    Orientation angle
18.     t AS Vector '      Tangent (unit) vector
19. END TYPE
20.  
21. DIM SHARED Segments(100) AS LineSegment
22. DIM SHARED NumSegments AS INTEGER
23. NumSegments = 0
24.  
25. '' Example: Define a line using parameters (calculates endpoints anyway):
26. 'NumSegments = NumSegments + 1
27. 'Segments(NumSegments).b.x = 0
28. 'Segments(NumSegments).b.y = 0
29. 'Segments(NumSegments).alpha1 = 0
30. 'Segments(NumSegments).alpha2 = 100
31. 'Segments(NumSegments).ang = ATN(0)
32. 'Segments(NumSegments).t.x = COS(Segments(NumSegments).ang)
33. 'Segments(NumSegments).t.y = SIN(Segments(NumSegments).ang)
34. 'CALL CalcEndpoints(NumSegments)
35.  
36. '' Example: Define a line using endpoints (calculates parameters anyway):
37. 'NumSegments = NumSegments + 1
38. 'Segments(NumSegments).p1.x = 0
39. 'Segments(NumSegments).p1.y = 0
40. 'Segments(NumSegments).p2.x = 100
41. 'Segments(NumSegments).p2.y = 0
42.  
43. ' Main lines and shapes
44.  
45. NumSegments = NumSegments + 1
46. Segments(NumSegments).p1.x = -100
47. Segments(NumSegments).p1.y = -100
48. Segments(NumSegments).p2.x = 100
49. Segments(NumSegments).p2.y = -100
50.  
51. NumSegments = NumSegments + 1
52. Segments(NumSegments).p1.x = -200
53. Segments(NumSegments).p1.y = -100
54. Segments(NumSegments).p2.x = 200
55. Segments(NumSegments).p2.y = -100
56.  
57. NumSegments = NumSegments + 1
58. Segments(NumSegments).p1.x = 200
59. Segments(NumSegments).p1.y = -100
60. Segments(NumSegments).p2.x = 0
61. Segments(NumSegments).p2.y = 200
62.  
63. NumSegments = NumSegments + 1
64. Segments(NumSegments).p1.x = 0
65. Segments(NumSegments).p1.y = 200
66. Segments(NumSegments).p2.x = -200
67. Segments(NumSegments).p2.y = -100
68.  
69. NumSegments = NumSegments + 1
70. Segments(NumSegments).p1.x = -200
71. Segments(NumSegments).p1.y = -200
72. Segments(NumSegments).p2.x = 200
73. Segments(NumSegments).p2.y = 200
74.  
75. NumSegments = NumSegments + 1
76. Segments(NumSegments).p1.x = 200
77. Segments(NumSegments).p1.y = -200
78. Segments(NumSegments).p2.x = -200
79. Segments(NumSegments).p2.y = 200
80.  
81. ' Main loop
82. DO
83.  
84.     ' User input
85.     DO WHILE _MOUSEINPUT
86.         x = _MOUSEX
87.         y = _MOUSEY
88.         IF ((x > 0) AND (x < _WIDTH) AND (y > 0) AND (y < _HEIGHT)) THEN
89.             IF (_MOUSEBUTTON(1)) THEN
90.                 CALL CalcParameters(1)
91.                 x = _MOUSEX
92.                 y = _MOUSEY
93.                 Segments(1).b.x = INT((x - _WIDTH / 2))
94.                 Segments(1).b.y = INT((-y + _HEIGHT / 2))
95.                 CALL CalcEndpoints(1)
96.             END IF
97.             IF (_MOUSEWHEEL > 0) THEN
98.                 CALL CalcParameters(1)
99.                 Segments(1).ang = Segments(1).ang + ATN(1) / 10
100.                 Segments(1).t.x = COS(Segments(1).ang)
101.                 Segments(1).t.y = SIN(Segments(1).ang)
102.                 CALL CalcEndpoints(1)
103.             END IF
104.             IF (_MOUSEWHEEL < 0) THEN
105.                 CALL CalcParameters(1)
106.                 Segments(1).ang = Segments(1).ang - ATN(1) / 10
107.                 Segments(1).t.x = COS(Segments(1).ang)
108.                 Segments(1).t.y = SIN(Segments(1).ang)
109.                 CALL CalcEndpoints(1)
110.             END IF
111.         END IF
112.     LOOP
113.  
114.     ' Graphics
115.     CLS
116.     FOR k = 1 TO NumSegments
117.         CALL cline(Segments(k).p1.x, Segments(k).p1.y, Segments(k).p2.x, Segments(k).p2.y, 15)
118.     NEXT
119.  
120.     ' Intersections loop
121.     FOR k = 1 TO NumSegments
122.         FOR j = k + 1 TO NumSegments
123.             a1x = Segments(k).p1.x
124.             a1y = Segments(k).p1.y
125.             a2x = Segments(k).p2.x
126.             a2y = Segments(k).p2.y
127.             b1x = Segments(j).p1.x
128.             b1y = Segments(j).p1.y
129.             b2x = Segments(j).p2.x
130.             b2y = Segments(j).p2.y
131.             CALL CalcIntersections(a1x, a1y, a2x, a2y, b1x, b1y, b2x, b2y)
132.         NEXT
133.     NEXT
134.  
135.     _DISPLAY
136.     _LIMIT 60
137. LOOP
138.  
139. END
140.  
141. SUB CalcIntersections (a1x, a1y, a2x, a2y, b1x, b1y, b2x, b2y)
142.     ' Requires UDT LineSegment
143.     ' Requires FUNCTION DotProduct
144.  
145.     DIM s1 AS LineSegment
146.     DIM s2 AS LineSegment
147.  
148.     s1.p1.x = a1x
149.     s1.p1.y = a1y
150.     s1.p2.x = a2x
151.     s1.p2.y = a2y
152.     s1.ang = ATN((s1.p2.y - s1.p1.y) / (s1.p2.x - s1.p1.x))
153.     s1.b.x = .5 * (s1.p1.x + s1.p2.x)
154.     s1.b.y = .5 * (s1.p1.y + s1.p2.y)
155.     s1.alpha1 = -.5 * _HYPOT(s1.p2.x - s1.p1.x, s1.p2.y - s1.p1.y)
156.     s1.alpha2 = .5 * _HYPOT(s1.p2.x - s1.p1.x, s1.p2.y - s1.p1.y)
157.     s1.t.x = COS(s1.ang)
158.     s1.t.y = SIN(s1.ang)
159.  
160.     s2.p1.x = b1x
161.     s2.p1.y = b1y
162.     s2.p2.x = b2x
163.     s2.p2.y = b2y
164.     s2.ang = ATN((s2.p2.y - s2.p1.y) / (s2.p2.x - s2.p1.x))
165.     s2.b.x = .5 * (s2.p1.x + s2.p2.x)
166.     s2.b.y = .5 * (s2.p1.y + s2.p2.y)
167.     s2.alpha1 = -.5 * _HYPOT(s2.p2.x - s2.p1.x, s2.p2.y - s2.p1.y)
168.     s2.alpha2 = .5 * _HYPOT(s2.p2.x - s2.p1.x, s2.p2.y - s2.p1.y)
169.     s2.t.x = COS(s2.ang)
170.     s2.t.y = SIN(s2.ang)
171.  
172.     DIM db AS Vector
173.     db.x = s2.b.x - s1.b.x
174.     db.y = s2.b.y - s1.b.y
175.     qj = DotProduct(db, s1.t)
176.     ql = DotProduct(db, s2.t)
177.     p = DotProduct(s1.t, s2.t)
178.     pp = p * p
179.     IF (pp < 1) THEN ' Non-parallel case
180.         alphaj = (qj - p * ql) / (1 - pp)
181.         alphal = (p * qj - ql) / (1 - pp)
182.         IF ((alphaj > s1.alpha1) AND (alphaj < s1.alpha2)) THEN
183.             IF ((alphal > s2.alpha1) AND (alphal < s2.alpha2)) THEN
184.                 CALL ccircle(s1.b.x + alphaj * s1.t.x, s1.b.y + alphaj * s1.t.y, 3, 13)
185.                 CALL ccircle(s2.b.x + alphal * s2.t.x, s2.b.y + alphal * s2.t.y, 5, 15)
186.             END IF
187.         END IF
188.     ELSE ' Parallel case
189.         LOCATE 5, 5: PRINT pp
190.         DIM dbhat AS Vector
191.         dbmag = SQR(db.x * db.x + db.y * db.y)
192.         IF (dbmag <> 0) THEN
193.             dbhat.x = db.x / dbmag
194.             dbhat.y = db.y / dbmag
195.             thresh = DotProduct(dbhat, s1.t)
196.         END IF
197.         IF ((1 - thresh * thresh < 0.001) OR (dbmag = 0)) THEN ' Overlap detection
198.             t1t2 = DotProduct(s1.t, s2.t)
199.             alphaj1 = s2.alpha1 * t1t2 + DotProduct(s1.t, db)
200.             alphaj2 = s2.alpha2 * t1t2 + DotProduct(s1.t, db)
201.             x1 = 0
202.             y1 = 0
203.             x2 = 0
204.             y2 = 0
205.             IF ((alphaj1 >= s1.alpha1) AND (alphaj1 <= s1.alpha2)) THEN
206.                 xx = s1.b.x + alphaj1 * s1.t.x
207.                 yy = s1.b.y + alphaj1 * s1.t.y
208.                 IF (x1 = 0) THEN x1 = xx ELSE x2 = xx
209.                 IF (y1 = 0) THEN y1 = yy ELSE y2 = yy
210.                 CALL ccircle(xx, yy, 3, 13)
211.                 'CALL ccircle(s2.b.x + s2.alpha1 * s2.t.x, s2.b.y + s2.alpha1 * s2.t.y, 4, 14)
212.             END IF
213.             IF ((alphaj2 >= s1.alpha1) AND (alphaj2 <= s1.alpha2)) THEN
214.                 xx = s1.b.x + alphaj2 * s1.t.x
215.                 yy = s1.b.y + alphaj2 * s1.t.y
216.                 IF (x1 = 0) THEN x1 = xx ELSE x2 = xx
217.                 IF (y1 = 0) THEN y1 = yy ELSE y2 = yy
218.                 CALL ccircle(xx, yy, 3, 13)
219.                 'CALL ccircle(s2.b.x + s2.alpha2 * s2.t.x, s2.b.y + s2.alpha2 * s2.t.y, 4, 14)
220.             END IF
221.             alphal1 = s1.alpha1 * t1t2 - DotProduct(s2.t, db)
222.             alphal2 = s1.alpha2 * t1t2 - DotProduct(s2.t, db)
223.             IF ((alphal1 >= s2.alpha1) AND (alphal1 <= s2.alpha2)) THEN
224.                 xx = s2.b.x + alphal1 * s2.t.x
225.                 yy = s2.b.y + alphal1 * s2.t.y
226.                 IF (x1 = 0) THEN x1 = xx ELSE x2 = xx
227.                 IF (y1 = 0) THEN y1 = yy ELSE y2 = yy
228.                 CALL ccircle(xx, yy, 3, 15)
229.                 'CALL ccircle(s1.b.x + s1.alpha1 * s1.t.x, s1.b.y + s1.alpha1 * s1.t.y, 5, 15)
230.             END IF
231.             IF ((alphal2 >= s2.alpha1) AND (alphal2 <= s2.alpha2)) THEN
232.                 xx = s2.b.x + alphal2 * s2.t.x
233.                 yy = s2.b.y + alphal2 * s2.t.y
234.                 IF (x1 = 0) THEN x1 = xx ELSE x2 = xx
235.                 IF (y1 = 0) THEN y1 = yy ELSE y2 = yy
236.                 CALL ccircle(xx, yy, 3, 15)
237.                 'CALL ccircle(s1.b.x + s1.alpha2 * s1.t.x, s1.b.y + s1.alpha2 * s1.t.y, 5, 15)
238.             END IF
239.             IF (x1 OR x2 OR y1 OR y2) THEN ' Overlap occurred
240.                 CALL cline(x1, y1, x2, y2, 13)
241.             END IF
242.         END IF
243.     END IF
244.  
245. END SUB
246.  
247. SUB CalcEndpoints (i AS INTEGER)
248.     Segments(i).p1.x = Segments(i).b.x + Segments(i).alpha1 * Segments(i).t.x
249.     Segments(i).p1.y = Segments(i).b.y + Segments(i).alpha1 * Segments(i).t.y
250.     Segments(i).p2.x = Segments(i).b.x + Segments(i).alpha2 * Segments(i).t.x
251.     Segments(i).p2.y = Segments(i).b.y + Segments(i).alpha2 * Segments(i).t.y
252. END SUB
253.  
254. SUB CalcParameters (i AS INTEGER)
255.     Segments(i).ang = ATN((Segments(i).p2.y - Segments(i).p1.y) / (Segments(i).p2.x - Segments(i).p1.x))
256.     Segments(i).b.x = .5 * (Segments(i).p1.x + Segments(i).p2.x)
257.     Segments(i).b.y = .5 * (Segments(i).p1.y + Segments(i).p2.y)
258.     Segments(i).alpha1 = -.5 * _HYPOT(Segments(i).p2.x - Segments(i).p1.x, Segments(i).p2.y - Segments(i).p1.y)
259.     Segments(i).alpha2 = .5 * _HYPOT(Segments(i).p2.x - Segments(i).p1.x, Segments(i).p2.y - Segments(i).p1.y)
260.     Segments(i).t.x = COS(Segments(i).ang)
261.     Segments(i).t.y = SIN(Segments(i).ang)
262. END SUB
263.  
264. FUNCTION DotProduct (a AS Vector, b AS Vector)
265.     DotProduct = a.x * b.x + a.y * b.y
266. END FUNCTION
267.  
268. SUB cline (x1 AS DOUBLE, y1 AS DOUBLE, x2 AS DOUBLE, y2 AS DOUBLE, col AS _UNSIGNED LONG)
269.     LINE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2)-(_WIDTH / 2 + x2, -y2 + _HEIGHT / 2), col
270. END SUB
271.  
272. SUB ccircle (x1 AS DOUBLE, y1 AS DOUBLE, rad AS DOUBLE, col AS _UNSIGNED LONG)
273.     CIRCLE (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), rad, col
274. END SUB
275.  
276. SUB cpset (x1 AS DOUBLE, y1 AS DOUBLE, col AS _UNSIGNED LONG)
277.     PSET (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col
278. END SUB
279.  
280. SUB cpaint (x1 AS DOUBLE, y1 AS DOUBLE, col1 AS _UNSIGNED LONG, col2 AS _UNSIGNED LONG)
281.     PAINT (_WIDTH / 2 + x1, -y1 + _HEIGHT / 2), col1, col2
282. END SUB
283.  
284. SUB cprintstring (y AS DOUBLE, a AS STRING)
285.     _PRINTSTRING (_WIDTH / 2 - (LEN(a) * 8) / 2, -y + _HEIGHT / 2), a
286. END SUB
287.  

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 23, 2020, 01:41:33 pm

Quote

Not to mention, it makes Trig COMPLETELY UPSIDE DOWN and only helps to stifle the learning around here, trust me.

Sorry man, didn't think this would turn into such a chore. Can't get there from here, not without going around the whole world first, yikes I think you are way past 67 LOC (245 - 141 + Dot Product = 100+ LOC) and still no FUNCTION in sight.

The trig is right on for an "upside down" 1st quadrant, angles increase as you go clockwise just as a "right side up" math quadrant goes counter clockwise with increasing angle. What is NOT consistent is the CIRCLE SUB built into QB64, those start and end angles for arcs are wrong for an "upside down" first quadrant.

A proper WINDOW command let's you "right" the coordinates and put the origin wherever your heart desires but CIRCLE will still be inconsistent.

One WINDOW command and a CIRCLE SUB of your own will save you all those supplemental procedures you keep adding to "fix" the coordinate system.

... but it's 6 of 1 half dozen of another, use WINDOW and you have PSET and LINE but not MOUSE but there is a command to fix that (see wiki WINDOW) but not sure how _PRINTSTRING and such will do.

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 24, 2020, 10:10:40 pm

Oh yeah! From 56 lines of code down to 32 and the 2 supplemental subs are useful too without line segments intersect.

Here is what I've whittle it down to, to get the intersect point of two line segments:

Code: QB64: [Select]

1. ' For segments intersect first we need to know if lines do and for that we need to knoww stuff
2. ' about the line from the segment given.
3.  
4. '  Return 0 if x = x2 and line is perpendicular otherwise return -1, slope = M and yIntersect = Y0
5. FUNCTION slopeY0% (X, Y, X2, Y2, M, Y0)
6.     IF X = X2 THEN EXIT FUNCTION ELSE slopeY0% = -1: M = (Y2 - Y) / (X2 - X): Y0 = -X * M + Y
7. END SUB
8.  
9. ' Return 1, ix, iy if lines intersect, Return -1 if they overlap, return 0 if neither.
10. ' This function needs:
11. '  Return 0 if x = x2 and line is perpendicular otherwise return -1, slope = M and yIntersect = Y0
12. ' FUNCTION slopeY0% (X, Y, X2, Y2, M, Y0)
13. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
14.     DIM ai, bi, aM, bM, aY0, bY0, d
15.     ai = slopeY0%(ax1, ay1, ax2, ay2, aM, aY0) '                        here's the scoop on line a
16.     bi = slopeY0%(bx1, by1, bx2, by2, bM, bY0) '                         here's the dope on line b
17.     IF ai = 0 AND bi = 0 THEN '                              both are perpendicular how bout that!
18.         IF ax1 = bx1 THEN lineIntersectLine% = -1 '             whole line overlaps more amazing!!
19.     ELSEIF ai = 0 AND bi THEN '                         a is perpendicular and b is not so ix = ax
20.         ix = ax1: iy = bM * ix + bY0: lineIntersectLine% = 1 '            signal a point was found
21.     ELSEIF ai AND bi = 0 THEN '                         b is perpendicular and a is not so ix = bx
22.         ix = bx1: iy = aM * ix + aY0: lineIntersectLine% = 1 '            signal a point was found
23.     ELSE
24.         d = -aM + bM '                       if = 0 then parallel or equal because slopes are same
25.         IF d = 0 THEN '                                                 lines a and b are parallel
26.             IF aY0 = bY0 THEN lineIntersectLine% = -1 ' the same Y0 means signal overlapping lines
27.         ELSE '                           get values of ix, iy intersect point and signal intersect
28.             ix = (aY0 - bY0) / d: iy = (-aM * bY0 + bM * aY0) / d: lineIntersectLine% = 1
29.         END IF
30.     END IF
31. END FUNCTION
32.  
33. ' Return 1, ix, iy if line segments intersect, Return 0 if they don't
34. ' This function needs:
35. '  Return 0 if x = x2 and line is perpendicular otherwise return -1, slope = M and yIntersect = Y0
36. '  FUNCTION slopeY0% (X, Y, X2, Y2, M, Y0)
37. '  Return 1, ix, iy if lines intersect, Return -1 if they overlap, return 0 if neither.
38. '  FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
39. FUNCTION twoSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
40.     DIM intersect AS INTEGER, a1, a2, near0 '                                       default SINGLE
41.     intersect = lineIntersectLine%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
42.     near0 = _PI(2 / 360)
43.     IF intersect = 1 THEN
44.         a1 = _ATAN2(ay1 - iy, ax1 - ix): a2 = _ATAN2(ay2 - iy, ax2 - ix)
45.         IF ABS(a1 - a2) < near0 THEN EXIT SUB
46.         a1 = _ATAN2(by1 - iy, bx1 - ix): a2 = _ATAN2(by2 - iy, bx2 - ix)
47.         IF ABS(a1 - a2) < near0 THEN EXIT SUB
48.         twoSegmentsIntersect% = 1
49.     END IF
50. END FUNCTION
51.  

Here is the overlap of two triangles again with the procedures plugged into this test application:

Code: QB64: [Select]

1. OPTION _EXPLICIT
2. _TITLE "Two Triangles Overlap v2 2020-03-24" 'b+ 2020-03-24
3. ' Just worked Rosetta Code for Line Intersect Line
4. ' but what if we want to know if two line segments intersect?
5. '2020-03-14 "Two Line Segments Intersect" 'b+ 2020-03-14  start
6. '2020-03-15 rework this code so we identify points all on same line and
7. ' if there is overlap of line segments say the two x endpoints of the segments
8. ' otherwise, if there is an intersect of 2 line segments say the point x, y.
9. ' Return 0 no intersect or overlap
10. ' Return 1 if intersect and ix, iy point of intersect
11. ' Return -1 if segments are on same and there is overlap: ix = overlap start x, iy overlap end x
12.  
13. '2020-03-16 "Segments Intersect mod tester"  >>> just post testing code
14. 'mod tester for 2 segments of vertical line and found I need to add more parameters to
15. ' FUNCTION twoLineSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
16. ' mod that name and parameters to:
17. ' FUNCTION twoSegmentsIntersect%  (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1, ix2, iy2)
18.  
19. '2020-03-16 Segments Intersect revised 2020-03-16
20. ' OK now get the new FUNCTION working
21. ' ah! I had to tighten down D from >.2 to >.05 but loosen y-axis intersect
22.  
23. '2020-03-18 apply routines to two triangles
24. ' modified FUNCTION twoSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix1, iy1)
25. ' to do only intersect. This code proved, Segments Intersect revised 2020-03-16, was faulty.
26.  
27. '2020-03-18 a more exactling test of triangle overlaps with line segments over lapping
28. ' purposely to the random triangles already tested and working well.
29.  
30. ' 2020-03-24     Two Triangles Overlap v2 2020-03-24
31. ' Can I tighten up the code for getting the Intersect of 2 Line Segments?
32. ' beat 3 + 26 + 27 = 56 lines of code in 3 procedures?
33. ' Oh yes!!! now have 3 + 18 + 11 = 32 lines of code
34. ' lineIntersectLine% cut 8 lines of code :)
35. ' twoSegmentsIntersect cut 16 lines of cutting from 27 lines to 11!
36.  
37. CONST xmax = 800, ymax = 600
38. SCREEN _NEWIMAGE(xmax, ymax, 32)
39. _DELAY .25
40. _SCREENMOVE _MIDDLE
41. DIM ax1 AS INTEGER, ax2 AS INTEGER, ay1 AS INTEGER, ay2 AS INTEGER
42. DIM ax3 AS INTEGER, ay3 AS INTEGER, bx1 AS INTEGER, bx2 AS INTEGER
43. DIM by1 AS INTEGER, by2 AS INTEGER, bx3 AS INTEGER, by3 AS INTEGER
44. DIM lCnt, dista2a3, adx, ady, ix1, i, x1, y1, sect, iy1, dista1a3
45. DIM dista1a2, distb2b3, bdx, bdy, distb1b3, distb1b2, again$
46.  
47. DO 'main testing loop sets up two triangles to test overlap area
48.     lCnt = lCnt + 1 'loop counter to control some purposeful test triangles
49.     IF lCnt MOD 4 = 0 THEN 'purpose overlap vertical lines
50.         cText 400, 580, 32, &HFF0088FF, "Two Triangles with Common Vertical Segment"
51.         ax1 = 400: ay1 = 20
52.         ax2 = 400: ay2 = 570
53.         ax3 = (xmax - 20) * RND + 10: ay3 = (ymax - 20) * RND + 10
54.         bx1 = 400: by1 = 200
55.         bx2 = 400: by2 = 450
56.         bx3 = (xmax - 20) * RND + 10: by3 = (ymax - 20) * RND + 10
57.  
58.     ELSEIF lCnt MOD 4 = 1 THEN 'purpose overlap horizontal line
59.         cText 400, 580, 32, &HFF008800, "Two Triangles with Common Horizontal Segment"
60.         ax1 = 10: ay1 = 300
61.         ax2 = 400: ay2 = 300
62.         ax3 = (xmax - 20) * RND + 10: ay3 = (ymax - 20) * RND + 10
63.         bx1 = 125: by1 = 300
64.         bx2 = 700: by2 = 300
65.         bx3 = (xmax - 20) * RND + 10: by3 = by3 = (ymax - 20) * RND + 10
66.  
67.     ELSEIF lCnt MOD 4 = 2 THEN 'purpose overlap 1/5 triangle
68.         cText 400, 580, 32, &HFFFF8800, "Two Triangles with Common 45 Degree Segment"
69.         ax1 = 100: ay1 = 100
70.         ax2 = 400: ay2 = 400
71.         ax3 = (xmax - 20) * RND + 10: ay3 = (ymax - 20) * RND + 10
72.         bx1 = 50: by1 = 50
73.         bx2 = 500: by2 = 500
74.         bx3 = (xmax - 20) * RND + 10: by3 = (ymax - 20) * RND + 10
75.  
76.     ELSEIF lCnt MOD 4 = 3 THEN ' completely random triangles
77.         cText 400, 580, 32, &HFF0000FF, "Two Completely Random Triangles"
78.         ax1 = (xmax - 20) * RND + 10: ay1 = (ymax - 20) * RND + 10
79.         ax2 = (xmax - 20) * RND + 10: ay2 = (ymax - 20) * RND + 10
80.         ax3 = (xmax - 20) * RND + 10: ay3 = (ymax - 20) * RND + 10
81.         bx1 = (xmax - 20) * RND + 10: by1 = (ymax - 20) * RND + 10
82.         bx2 = (xmax - 20) * RND + 10: by2 = (ymax - 20) * RND + 10
83.         bx3 = (xmax - 20) * RND + 10: by3 = (ymax - 20) * RND + 10
84.     END IF
85.     'tri a
86.     LINE (ax1, ay1)-(ax2, ay2), &HFFFF0000
87.     LINE (ax2, ay2)-(ax3, ay3), &HFFFF0000
88.     LINE (ax3, ay3)-(ax1, ay1), &HFFFF0000
89.     'tri b
90.     LINE (bx1, by1)-(bx2, by2), &HFF0000FF
91.     LINE (bx2, by2)-(bx3, by3), &HFF0000FF
92.     LINE (bx3, by3)-(bx1, by1), &HFF0000FF
93.  
94.     dista2a3 = _HYPOT(ax2 - ax3, ay2 - ay3)
95.     adx = (ax3 - ax2) / dista2a3: ady = (ay3 - ay2) / dista2a3
96.     FOR i = 0 TO dista2a3
97.         x1 = ax2 + adx * i: y1 = ay2 + ady * i
98.         sect = twoSegmentsIntersect%(ax1, ay1, x1, y1, bx1, by1, bx2, by2, ix1, iy1)
99.         IF sect THEN PSET (ix1, iy1)
100.         sect = twoSegmentsIntersect%(ax1, ay1, x1, y1, bx3, by3, bx2, by2, ix1, iy1)
101.         IF sect THEN PSET (ix1, iy1)
102.         sect = twoSegmentsIntersect%(ax1, ay1, x1, y1, bx1, by1, bx3, by3, ix1, iy1)
103.         IF sect = 1 THEN PSET (ix1, iy1)
104.     NEXT
105.  
106.     dista1a3 = _HYPOT(ax1 - ax3, ay1 - ay3)
107.     adx = (ax3 - ax1) / dista1a3: ady = (ay3 - ay1) / dista1a3
108.     FOR i = 0 TO dista1a3
109.         x1 = ax1 + adx * i: y1 = ay1 + ady * i
110.         sect = twoSegmentsIntersect%(ax2, ay2, x1, y1, bx1, by1, bx2, by2, ix1, iy1)
111.         IF sect THEN PSET (ix1, iy1)
112.         sect = twoSegmentsIntersect%(ax2, ay2, x1, y1, bx3, by3, bx2, by2, ix1, iy1)
113.         IF sect THEN PSET (ix1, iy1)
114.         sect = twoSegmentsIntersect%(ax2, ay2, x1, y1, bx1, by1, bx3, by3, ix1, iy1)
115.         IF sect = 1 THEN PSET (ix1, iy1)
116.     NEXT
117.  
118.     dista1a2 = _HYPOT(ax1 - ax2, ay1 - ay2)
119.     adx = (ax2 - ax1) / dista1a2: ady = (ay2 - ay1) / dista1a2
120.     FOR i = 0 TO dista1a2
121.         x1 = ax1 + adx * i: y1 = ay1 + ady * i
122.         sect = twoSegmentsIntersect%(ax3, ay3, x1, y1, bx1, by1, bx2, by2, ix1, iy1)
123.         IF sect THEN PSET (ix1, iy1)
124.         sect = twoSegmentsIntersect%(ax3, ay3, x1, y1, bx3, by3, bx2, by2, ix1, iy1)
125.         IF sect THEN PSET (ix1, iy1)
126.         sect = twoSegmentsIntersect%(ax3, ay3, x1, y1, bx1, by1, bx3, by3, ix1, iy1)
127.         IF sect = 1 THEN PSET (ix1, iy1)
128.     NEXT
129.  
130.     distb2b3 = _HYPOT(bx2 - bx3, by2 - by3)
131.     bdx = (bx3 - bx2) / distb2b3: bdy = (by3 - by2) / distb2b3
132.     FOR i = 0 TO distb2b3
133.         x1 = bx2 + bdx * i: y1 = by2 + bdy * i
134.         sect = twoSegmentsIntersect%(bx1, by1, x1, y1, ax1, ay1, ax2, ay2, ix1, iy1)
135.         IF sect = 1 THEN PSET (ix1, iy1)
136.         sect = twoSegmentsIntersect%(bx1, by1, x1, y1, ax3, ay3, ax2, ay2, ix1, iy1)
137.         IF sect THEN PSET (ix1, iy1)
138.         sect = twoSegmentsIntersect%(bx1, by1, x1, y1, ax1, ay1, ax3, ay3, ix1, iy1)
139.         IF sect = 1 THEN PSET (ix1, iy1)
140.     NEXT
141.  
142.     distb1b3 = _HYPOT(bx1 - bx3, by1 - by3)
143.     bdx = (bx3 - bx1) / distb1b3: bdy = (by3 - by1) / distb1b3
144.     FOR i = 0 TO distb1b3
145.         x1 = bx1 + bdx * i: y1 = by1 + bdy * i
146.         sect = twoSegmentsIntersect%(bx2, by2, x1, y1, ax1, ay1, ax2, ay2, ix1, iy1)
147.         IF sect THEN PSET (ix1, iy1)
148.         sect = twoSegmentsIntersect%(bx2, by2, x1, y1, ax3, ay3, ax2, ay2, ix1, iy1)
149.         IF sect THEN PSET (ix1, iy1)
150.         sect = twoSegmentsIntersect%(bx2, by2, x1, y1, ax1, ay1, ax3, ay3, ix1, iy1)
151.         IF sect = 1 THEN PSET (ix1, iy1)
152.     NEXT
153.  
154.     distb1b2 = _HYPOT(bx1 - bx2, by1 - by2)
155.     bdx = (bx2 - bx1) / distb1b2: bdy = (by2 - by1) / distb1b2
156.     FOR i = 0 TO distb1b2
157.         x1 = bx1 + bdx * i: y1 = by1 + bdy * i
158.         sect = twoSegmentsIntersect%(bx3, by3, x1, y1, ax1, ay1, ax2, ay2, ix1, iy1)
159.         IF sect = 1 THEN PSET (ix1, iy1)
160.         sect = twoSegmentsIntersect%(bx3, by3, x1, y1, ax3, ay3, ax2, ay2, ix1, iy1)
161.         IF sect = 1 THEN PSET (ix1, iy1)
162.         sect = twoSegmentsIntersect%(bx3, by3, x1, y1, ax1, ay1, ax3, ay3, ix1, iy1)
163.         IF sect = 1 THEN PSET (ix1, iy1)
164.     NEXT
165.  
166.     INPUT "Press enter for another demo, any + enter to quit...", again$
167.     CLS
168. LOOP UNTIL LEN(again$)
169.  
170. 'center the text at x, y with given height and color
171. SUB cText (x, y, textHeight, K AS _UNSIGNED LONG, txt$)
172.     DIM fg AS _UNSIGNED LONG, cur&, I&, mult, xlen
173.     fg = _DEFAULTCOLOR
174.     'screen snapshot
175.     cur& = _DEST
176.     I& = _NEWIMAGE(8 * LEN(txt$), 16, 32)
177.     _DEST I&
178.     COLOR K, _RGBA32(0, 0, 0, 0)
179.     _PRINTSTRING (0, 0), txt$
180.     mult = textHeight / 16
181.     xlen = LEN(txt$) * 8 * mult
182.     _PUTIMAGE (x - .5 * xlen, y - .5 * textHeight)-STEP(xlen, textHeight), I&, cur&
183.     COLOR fg
184.     _FREEIMAGE I&
185. END SUB
186.  
187. ' ======================================== end tester code functions ===========================98
188.  
189. ' For segments intersect first we need to know if lines do and for that we need to knoww stuff
190. ' about the line from the segment given.
191.  
192. '  Return 0 if x = x2 and line is perpendicular otherwise return -1, slope = M and yIntersect = Y0
193. FUNCTION slopeY0% (X, Y, X2, Y2, M, Y0)
194.     IF X = X2 THEN EXIT FUNCTION ELSE slopeY0% = -1: M = (Y2 - Y) / (X2 - X): Y0 = -X * M + Y
195. END SUB
196.  
197. ' Return 1, ix, iy if lines intersect, Return -1 if they overlap, return 0 if neither.
198. ' This function needs:
199. '  Return 0 if x = x2 and line is perpendicular otherwise return -1, slope = M and yIntersect = Y0
200. ' FUNCTION slopeY0% (X, Y, X2, Y2, M, Y0)
201. FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
202.     DIM ai, bi, aM, bM, aY0, bY0, d
203.     ai = slopeY0%(ax1, ay1, ax2, ay2, aM, aY0) '                        here's the scoop on line a
204.     bi = slopeY0%(bx1, by1, bx2, by2, bM, bY0) '                         here's the dope on line b
205.     IF ai = 0 AND bi = 0 THEN '                              both are perpendicular how bout that!
206.         IF ax1 = bx1 THEN lineIntersectLine% = -1 '             whole line overlaps more amazing!!
207.     ELSEIF ai = 0 AND bi THEN '                         a is perpendicular and b is not so ix = ax
208.         ix = ax1: iy = bM * ix + bY0: lineIntersectLine% = 1 '            signal a point was found
209.     ELSEIF ai AND bi = 0 THEN '                         b is perpendicular and a is not so ix = bx
210.         ix = bx1: iy = aM * ix + aY0: lineIntersectLine% = 1 '            signal a point was found
211.     ELSE
212.         d = -aM + bM '                       if = 0 then parallel or equal because slopes are same
213.         IF d = 0 THEN '                                                 lines a and b are parallel
214.             IF aY0 = bY0 THEN lineIntersectLine% = -1 ' the same Y0 means signal overlapping lines
215.         ELSE '                           get values of ix, iy intersect point and signal intersect
216.             ix = (aY0 - bY0) / d: iy = (-aM * bY0 + bM * aY0) / d: lineIntersectLine% = 1
217.         END IF
218.     END IF
219. END FUNCTION
220.  
221. ' Return 1, ix, iy if line segments intersect, Return 0 if they don't
222. ' This function needs:
223. '  Return 0 if x = x2 and line is perpendicular otherwise return -1, slope = M and yIntersect = Y0
224. '  FUNCTION slopeY0% (X, Y, X2, Y2, M, Y0)
225. '  Return 1, ix, iy if lines intersect, Return -1 if they overlap, return 0 if neither.
226. '  FUNCTION lineIntersectLine% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
227. FUNCTION twoSegmentsIntersect% (ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
228.     DIM intersect AS INTEGER, a1, a2, near0 '                                       default SINGLE
229.     intersect = lineIntersectLine%(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2, ix, iy)
230.     near0 = _PI(2 / 360)
231.     IF intersect = 1 THEN
232.         a1 = _ATAN2(ay1 - iy, ax1 - ix): a2 = _ATAN2(ay2 - iy, ax2 - ix)
233.         IF ABS(a1 - a2) < near0 THEN EXIT SUB
234.         a1 = _ATAN2(by1 - iy, bx1 - ix): a2 = _ATAN2(by2 - iy, bx2 - ix)
235.         IF ABS(a1 - a2) < near0 THEN EXIT SUB
236.         twoSegmentsIntersect% = 1
237.     END IF
238. END FUNCTION
239.  

The shortcut for line segments was made when I realized if a line does not cross the intersect point BOTH it's points will lie on the same side and have the same angle from the intersect point whereas if the segment crossed the intersect point there would be a 180 degree difference between the angles from the intersect point.

Title: Re: Intersect of 2 lines carried a step further
Post by: TempodiBasic on March 25, 2020, 06:31:22 am

Hi guys
I'm following fascinated your math graphic thread!
Starting from the search of a point of contact between two segments, you have arrived to show IF , WHERE and HOW two triangles ( so 2 plane objects) interacts between and what part of each them is  envolved in the contact.
Cool!
I think applications of this one into  Graphic function, Collision detection,  3D rendering and so go on ( for example, AI, MAP editing)!

Thanks to share!

Title: Re: Intersect of 2 lines carried a step further
Post by: bplus on March 25, 2020, 11:48:56 am

Thanks TempodiBasic, I think you've got the significance. :)

I don't know if this will be practical but we'll see.

Text Only | Text with Attachments