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

[Laurent A. <lau...@su...>]

I certainly missed something here, because it looks quite easy to me, =
with
this approximation:

Your moving segment will describe, between two frames, either a 4 sided
convex polygon, either two triangles (4 sided concave polygon). Your =
moving
point will describe a segment.

You test quite easily if you=92re in case 1 (quad), or in case 2 (two
triangles), and then perform a quad / segment collision test, or two
triangles / segment test.

=20

This will approximate to a per frame / linear velocity, but you can =
solve it
easily, and if you have a decent frame rate, it works well.

Then you can upgrade to a better test with parametric equation only on =
the
point, and keep the case 1 / case 2 tests for the moving segment.

=20

At least, it=92s easy to implement and works straightforward. It depends =
how
you actually intend to use the results =85

=20

            Laurent

=20

  _____ =20

De : gda...@li...
[mailto:gda...@li...] De la part de =
Robert
Dibley
Envoy=E9 : lundi 13 mars 2006 12:52
=C0 : gda...@li...
Objet : RE: [Algorithms] Moving Segment vs Moving Point Intersection =
(2D)

=20

The velocity of C with respect to AB is time dependent, because the =
closest
point on the line is also time dependent.

(Note that the surface swept by the line AB can be curved or flat, and =
even
if it is flat it still doesn=92t guarantee a linear solution)

=20

Just to add to the fun, you have to consider the case when the closest =
point
on the line is one of the end points, which changes everything.

=20

I would suggest that the most reliable way to do this would be to stick =
with
your =93closest point=94 approach, use that to find an instantaneous =
answer to
the relative velocity and then move forward to a point in time that is =
only
part way towards the potential collision point.  Then you can =
re-evaluate
the closest point and the relative velocity, and try again.

I would imagine in most cases you only need to know if collision in a
certain (short) time frame is going to happen, in which case the vast
majority of cases would probably get a quick out because there is no =
chance
of collision in that time frame.  The remainder would just need a few
iterations to convince you that collision was inevitable =96 if you get =
to the
point where you are only millimetres from collision then treating it as =
if
it has happened is probably quite safe.

=20

Cheers

=20

Robert

=20

=20

  _____ =20

From: gda...@li...
[mailto:gda...@li...] On Behalf Of =
metanet
software
Sent: 11 March 2006 21:51
To: gda...@li...
Subject: [Algorithms] Moving Segment vs Moving Point Intersection (2D)

=20

hi,
Hopefully someone can point me towards some good references/theory..
moving-segment tests came up in the context of Carmageddon a while ago =
(I
think), but searching the archives hasn't turned anything up.

My current "ad-hoc" algorithm is:

given linesegment with endpoints A,B and endpoint velocities vA,vB, and
point C with velocity vC:
1) find the velocity V of C relative to segment A->B**
2) use this to perform a segment-vs-segment test, using A->B vs C->(C+V)

**for step (1), I find the point on A->B closest to C, and use the
parametric description of this point to blend vA and vB together to =
generate
a single velocity for the segment (which is subtracted from vC to get =
C's
velocity from A-B's frame of reference).

Step 1 seems very approximate/hacky, since you can use any combination =
of
current or future positions, each of which will give you a different =
result:
-point on A->B closest to C
-point on A->B closest to (C+vC)
-point on (A+vA)->(B+vB) closest to C
-point on (A+vA)->(B+vB) closest to (C+vC)

..there's no obvious "best"/most correct combination, which seems to
indicate that the "real" solution to this problem is probably not so =
neat or
linear, involving root finding or closest-point-of-approach calculation.

Anyway, any tips, suggestions or references would be great, I'd really =
like
to know of any more accurate (or at least less spontaneously-invented)
approached.

I should mention that I only need a boolean result, no time/point of
intersection.

thanks,
raigan

  _____ =20

Enrich your life at  <http://finance.yahoo.ca> Yahoo! Canada Finance