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

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

hey.
  thanks! 
  
  this is great: a real/accurate solution, instead of "perfectly provided  the movement of each point is vert small".. _and_ i can reuse all the  decompose-quad-into-triangles code from my (horribly approximate)   lineseg-vs-quad test ;)
  
  i can't believe i tried it the other way around (testing the moving  point from the point of view of a static lineseg) and not this way. doh!
  
  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


		
---------------------------------
Enrich your life at Yahoo! Canada Finance