Re: [Algorithms] Moving Segment vs Moving Point Intersection (2D)

[metanet s. <met...@ya...>]

  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