   How to find time of line-line-interception
  Hi,there's a problem I've not been able to figure out even with a lot of searching, so I hope anyone here can help me. Here's the situation:I have a line segment with endpoints (x1,y1) and (x2,y2), and another line with endpoints (x3,y3) and (x4,y4). The line segments have a relative velocity vector v, so the line segments move |v| units per unit of time.Do anyone have any idea on how I can detect WHEN those two lines will intersect, given this information?Thank you very much in advance!   
  I'm assuming that we're talking about constant linear velocity here, with fixed orientation over the time step?If so, you should be able to use the SAT for this. I think that for practical purposes, you can think of the segments as oriented boxes with one dimension equal to zero. You can then use the usual continuous SAT for oriented boxes to determine the first time of intersection (if any).Note that it may be possible to optimize the test somewhat to take advantage of the fact that one of the dimensions is always zero. However, the full swept box test won't do that much extra work, and, I think, will be guaranteed to return the correct results (unless I'm overlooking something).   ;  Figure out the intersection point of the 2 lines created by those segments.If they don't intersect, then neverthen figure out when line 1, point A will be equal to that point, then when point B of line 1 will be there.  this is the time interval when line segment 1 will be there.  you will solve this with simple s = vt  (pos = velocity * time)Do the same for line 2if the time intervals overlap then they will be there, and choose the lowest common point of that interval.  If the time intervals do not overlap then they will never be in the same place at the same time-me   ;  Palidine, I'm trying to understand the method you described, but:Quote:Figure out the intersection point of the 2 lines created by those segments.What do you mean by 'the 2 lines created by those segments'? Are you talking about the supporting lines for the segments? Or something else?   ;Quote:Original post by jykI'm assuming that we're talking about constant linear velocity here, with fixed orientation over the time step?If so, you should be able to use the SAT for this. I think that for practical purposes, you can think of the segments as oriented boxes with one dimension equal to zero. You can then use the usual continuous SAT for oriented boxes to determine the first time of intersection (if any).Note that it may be possible to optimize the test somewhat to take advantage of the fact that one of the dimensions is always zero. However, the full swept box test won't do that much extra work, and, I think, will be guaranteed to return the correct results (unless I'm overlooking something).Ah, thank you very much. The velocity is indeed constant within one frame (which is the only thing that really matters for my usage) and orientation is indeed fixed (the lines are simply translated). Yeah, it does make sense that SAT would work. I'll try that out. Optimizations I'll worry about later. Thanks again. :)   ;  Yeah, extend those 2 line segments into lines.  If that's what "supporting line" means, then yeah, that.  I'm assuming that the line segments move along the line of which they are a segment.  OP didn't have the edge cases defined well.  If they move along any other trajectory, then your solution is obviously the correct one.  This just smelled of weird algebra homework or something to me. [smile]-me   ;Quote:Original post by PalidineYeah, extend those 2 line segments into lines.  If that's what "supporting line" means, then yeah, that.  I'm assuming that the line segments move along the line of which they are a segment.  OP didn't have the edge cases defined well.  If they move along any other trajectory, then your solution is obviously the correct one.  This just smelled of weird algebra homework or something to me. [smile]-meHehe, it's definitly not a homework assignment ;)What it's for is not surprisingly collision detection in my game engine which I've been developing on and off. The idea was to potentially allow collision between objects of arbitrary shapes built up using line segments. At least in the future. For now I'm simply trying to get a rectangle vs line segment collision test to work, so I'll be able to have slopes and such in my tile map.   ;  I just woke up and I'm a bit unclear in my head still, but just a thought:You have 2 line segments (s1 and s2) which only moves with a linear velocity each update.Since both moves linearly, the only thing that is relevant is the velocity difference between them. Lets sayv = v2 - v1Now for each point on s1, perform a line-segment collision between the segment s2 and the line that is intersecting each of the points and have the direction of v.Do the same thing for each point on s2.The time of the intersection should be the minimum distance between point and segment divided by the norm of v.   ;  It seems very expensive to test each point on the line, doesn't it? :)I've had success with using SAT. I still have work to do on it, but it looks promising.   ;  You only have to perform 4 line-segment test. Each end point of the two segments defines in total 4 lines together with the vector v as the direction. Those lines you test against the line segments.   