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

0 Members and 1 Guest are viewing this topic.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #45 on: March 22, 2020, 10:51:25 am »
This can be made into a sub now that it's done, of course.

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

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

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #46 on: March 22, 2020, 04:42:46 pm »
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.
« Last Edit: March 22, 2020, 04:49:14 pm by bplus »

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #47 on: March 22, 2020, 04:52:36 pm »
Yeah - I suppose we have to work around QB64 only outputting one thing per function. I can make this into a SUB prolly - but there may have to be some hacky helper functions.

The real problem arises from the overly cartesian mindset brought on by the QB64 coordinate system. Grumble grumble... get to work...
You're not done when it works, you're done when it's right.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #48 on: March 22, 2020, 05:09:20 pm »
Yeah - I suppose we have to work around QB64 only outputting one thing per function. I can make this into a SUB prolly - but there may have to be some hacky helper functions.

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

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


Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #49 on: March 22, 2020, 05:12:47 pm »
QB64 coordinate system has no effect on the math, it's just one quadrant that's upside down in our subjective vision.

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

EDIT:

Not to mention, it makes Trig COMPLETELY UPSIDE DOWN and only helps to stifle the learning around here, trust me.
« Last Edit: March 22, 2020, 05:21:02 pm by STxAxTIC »
You're not done when it works, you're done when it's right.

Offline STxAxTIC

  • Library Staff
  • Forum Resident
  • Posts: 1091
  • he lives
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #50 on: March 23, 2020, 06:26:28 am »
Alrighty, here's about 90% of what you asked for. The intersection calculation sub takes endpoints as its inputs, but outputs nothing right now. I figure if you want it to return specific stuff, the road should be easy, very easy, to travel from here.

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

Anyway, here's the compromise:

(Control it with the mouse)

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

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #51 on: March 23, 2020, 01:41:33 pm »
Quote
Not to mention, it makes Trig COMPLETELY UPSIDE DOWN and only helps to stifle the learning around here, trust me.

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

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

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

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

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

Marked as best answer by bplus on March 29, 2020, 07:51:13 am

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #52 on: March 24, 2020, 10:10:40 pm »
Oh yeah! From 56 lines of code down to 32 and the 2 supplemental subs are useful too without line segments intersect.

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

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

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.
« Last Edit: March 25, 2020, 01:08:06 am by bplus »

Offline TempodiBasic

  • Forum Resident
  • Posts: 1792
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #53 on: March 25, 2020, 06:31:22 am »
Hi guys
I'm following fascinated your math graphic thread!
Starting from the search of a point of contact between two segments, you have arrived to show IF , WHERE and HOW two triangles ( so 2 plane objects) interacts between and what part of each them is  envolved in the contact.
Cool!
I think applications of this one into  Graphic function, Collision detection,  3D rendering and so go on ( for example, AI, MAP editing)!

Thanks to share!
Programming isn't difficult, only it's  consuming time and coffee

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
    • View Profile
Re: Intersect of 2 lines carried a step further
« Reply #54 on: March 25, 2020, 11:48:56 am »
Thanks TempodiBasic, I think you've got the significance. :)

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