Intersect of 2 lines carried a step further

[EricE]

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

[TerryRitchie]

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.

[EricE]

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. <

[bplus]

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.

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?

[bplus]

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

Code: QB64: [Select]

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

[TerryRitchie]

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.

[bplus]

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.  

[bplus]

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.

[STxAxTIC]

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!

[STxAxTIC]

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.  

[bplus]

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.

[STxAxTIC]

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

[bplus]

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.  

 

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.

[STxAxTIC]

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

[bplus]

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. ;)