Intersect of 2 lines carried a step further

[STxAxTIC]

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?

[bplus]

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.

[STxAxTIC]

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

[bplus]

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.

[STxAxTIC]

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.

[STxAxTIC]

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.  

[bplus]

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.

[bplus]

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.

[TempodiBasic]

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!

[bplus]

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

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