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

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

How about taking the other view of this - instead of looking for the moving
line segment which hits your point, look for the point on your line segment
which will hit your point.

 

So you are looking for t such that:

 

(C - (A + t(B-A))) cross (Av + t(Bv-Av)) = 0

 

( Oh, I'm assuming you have already subtracted the velocity of C from
everything, since that makes everything much easier )

 

So now you convert the above into a quadratic equation, find the solution(s)

If they are <0 or >1 then they are outside the segment so ignore

If not, then test for (Av + t(Bv-Av)) = 0 since this also gives the
appearance of success when in fact it should fail.

So long as that is not the case, then you are left with a known t which
gives you a straight line which is known to pass through the point C, and so
you can find the time of impact with a simple linear equation.

 

You can probably do this last bit with a dot product too, since you don't
need to do real collision at this point - you know it must pass through the
point (barring fp inaccuracy) so just find :

 

(C - (A + t(B-A))) dot (Av + t(Bv-Av)) 

_____________________________

 

 (Av + t(Bv-Av)) dot (Av + t(Bv-Av))

 

To give the fraction of time along the line that you need to travel.

 

I'll leave the long winded expansion to quadratic for you to work out :-)

 

Regards

 

Robert

 

 

  _____  

From: gda...@li...
[mailto:gda...@li...] On Behalf Of metanet
software
Sent: 02 April 2006 19:09
To: gda...@li...
Subject: Re: [Algorithms] Moving Segment vs Moving Point Intersection (2D)

 

hi,
just in case anyone else is going to use this -- you actually can't naively
discard the later intersection, because the quadratic gives you the
intersection times of the _infinite_ line with the point.  

if you're interested in the segment-vs-point intersections (as i was), you
have look at both roots to see if either represents an intersection with the
lineseg; sometimes the earlier intersection is outside the lineseg, while
the later one is in/on the lineseg.

raigan


Nils Pipenbrinck <n.p...@cu...> wrote:

Dave Moore wrote:

>
> Small niggle: you get a quadratic equation in t not a linear one, 
> right? There are cases where you get 2 crossings.


Yes, but you're usually interested in the intersection that happends 
earliest. It's save to discard the greater one.

Nils






-------------------------------------------------------
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  <http://photos.yahoo.ca>
Yahoo! Canada Photos