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

[Robert D. <bli...@go...>]

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't guarantee a linear solution)

 

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.

 

I would suggest that the most reliable way to do this would be to stick with
your "closest point" 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 - 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.

 

Cheers

 

Robert

 

 

  _____  

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)

 

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

  _____  

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