Intersect of 2 lines carried a step further

[STxAxTIC]

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.

[bplus]

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

[STxAxTIC]

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

[TempodiBasic]

great geometry knowledge!

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

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

Math & Logic can be useful

[bplus]

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

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

[TempodiBasic]

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

[bplus]

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.

[TempodiBasic]

Very Impressive Bplus
 

Thanks to share the code

[STxAxTIC]

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

[bplus]

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

[STxAxTIC]

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.

[bplus]

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.

[STxAxTIC]

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.  

[STxAxTIC]

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.  

[bplus]

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.