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

[<chr...@pl...>]

> 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/