Re: [Algorithms] Moving Segment vs Moving Point Intersection (2D)
Brought to you by:
vexxed72
From: Jonathan B. <jo...@nu...> - 2006-03-31 19:46:30
|
This is pretty simple... There are 2 tricks to simplify it. The first is, (assuming that things are moving linearly inside a timestep), consider the point to be stationary, and just subtract its velocity from the endpoints of the segment. This simplifies the equations. The second is, instead of trying to test against the line segment, you test against the whole line. The point can only cross the line once during the timestep (due to linearity). So if it crosses, then you find the crossing point, and then determine whether that was inside the segment or outside (which is easy). Let's call the endpoints of the line A and B. They are really functions of t i.e. A(t) and B(t) but to keep the equations simple we will omit that.... The point you are testing is p. When p crosses the line, (p - A) dot (B - A)perp = 0. [Here dot is the 2d dot product and perp is the 2D operator that rotates the vector 90 degrees, i.e. Vperp = (-Vy, Vx)]. The perp and the dot can be combined, so this is just: (p - A) perp_dot (B - A) = 0. So you just want to solve the equation above for t (which remember is implicit in the A and B). This is pretty trivial but the exact detail depends on your game. [I'm not sure if you are testing a point against, say, a rotating square or what.] Suppose this segment is some piece of an n-gon and you know the positions of A and B both at the beginning and end of the timestep. So we will call them A0 and A1 = A0 + delta A, similarly for B. Then A(t) = A0 + t delta A And you just plug that in for A and B in the equation above and solve it. So you get: (p - A0 - t delta A) perp_dot (B0 - A0 + t(delta B - delta A)) = 0 which is pretty easy to solve, and there you go. If you have any questions about this feel free to drop me an email... this is maybe not the most lucid explanation. metanet software wrote: > > It turns out that determining the _time_ of collision would be very > useful; I've tried to figure this out in a few ways, however I always > end up with one too many unknowns (or one too few equations). I > suppose this is what Christer meant by "much more complicated" ;) > > > If we know that C intersects the quad Q1,Q2,Q3,Q4, then there must > exist a unique line L which passes through C and which intersects the > lines L1 = Q1 + t(Q4-Q1) and L2 = Q2 + t(Q3-Q2) at the same value of t. > > It seems like there should be a very straightforward solution, since > there can only be a single direction for L which intersects L1 and L2 > at the same t parameter, however.. I haven't managed to find it. > Substituting the parametric description of the intersection points and > rearranging always seems to produce an equation of the form x + y + xy > = 0.. which can't be solved without another equation. Of course, it's > also possible that I made some mistakes while rearranging things.. > > > A related problem is finding the point of intersection; once we know > the time of intersection t it is trivial to determine the point of > intersection (at time t, C is colinear with the segment, so it's easy > to find the parametric/barycentric coord of C in terms of the segment > endpoints). Similarly, given this parametric coord, it would be > trivial to determine the time of intersection. However, I know neither. > > Does anyone have any suggestions on how to approach this problem? It > seems irritatingly simple. > > thanks for your time, > raigan > > > */chr...@pl.../* wrote: > > > > > given linesegment with endpoints A,B and endpoint velocities vA,vB, > > and point C with velocity vC [determine if intersection occurs] > > > > I should mention that I only need a boolean result, no time/point of > > intersection. > > In that you're working in 2D and are only interested in the boolean > result, this is pretty easy (3D or non-boolean results would make > it much more complicated). > > As others noted, the movement of segment AB will form a (possibly > concave or self-intersecting) quad in the plane. However, rather > than testing the moving point against this quad, the right approach > is to work in the space of the moving point C. > > C then becomes stationary and we turn the problem into that of > determining if C lies inside the quad Q determined by the four > points: Q1=A, Q2=B, Q3=B+vB-vC, and Q4=A+vA-vC. > > To correctly determine containment in Q you would have to determine > which of three cases you have: > > 1. Q is convex > 2. Q is concave > 3. Q is self-intersecting > > The first case is straightforward. C lies inside Q if C is > consistently to the left or right of all segments Q1Q2, Q2Q3, > Q3Q4, and Q4Q1. > > The second case corresponds to Q being a dart (Star Trek badge). > Split Q on the diagonal to form two triangles and test C for > containment in either triangle. > > For the third case, compute the point where the quad self- > intersects and form two triangles extending from that point and > test C for containment in the triangles. > > > Christer Ericson > http://realtimecollisiondetection.net/ > > > > ------------------------------------------------------- > This SF.Net email is sponsored by xPML, a groundbreaking scripting > language > that extends applications into web and mobile media. Attend the > live webcast > and join the prime developer group breaking into this new coding > territory! > http://sel.as-us.falkag.net/sel?cmd=lnk&kid=110944&bid=241720&dat=121642 > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 > > > ------------------------------------------------------------------------ > Share your photos with the people who matter at *Yahoo! Canada Photos* > <http://photos.yahoo.ca> |