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

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

Yes, the one advantage of mine is that the initial solution (of the =
quadratic) tells you if you are off the ends of the line segment =
immediately, which I=E2=80=99m guessing will save you some work =
=E2=80=93 not a lot though :-)

=20

Incidentally, I don=E2=80=99t know if you have thought about this at =
all, but your line segment is changing length when you do this sort of =
thing.

So if for example you really had a piece of wire spinning, it would have =
constant length, and each point on the wire would cover a curve.

Without modelling this, you will get cases where a point is missed =
because you are using straight line segments.

Whether that is a great concern or not is of course up to you =E2=80=93 =
but if you have a fast spinning wire, then perhaps it should be.

=20

Robert

=20

  _____ =20

From: gda...@li... =
[mailto:gda...@li...] On Behalf Of =
metanet software
Sent: 04 April 2006 03:25
To: gda...@li...
Subject: RE: [Algorithms] Moving Segment vs Moving Point Intersection =
(2D)

=20

hi,
weird, i'd never considered this, but it's seeming to make sense -- it's =
sort of the complement of the method jonathan suggested -- either way =
you solve a quadratic, which gives you a line containing the solution =
(the solution being the collision point at the time of collision).=20

the line either will either describe the movement of the collision point =
on the over the time interval [0,1] -- your suggestion, or the time of =
collision with the lineseg (which is an interval) -- jonathan's =
suggestion.=20

either way you can find the solution point by finding the intersection =
of the point's movement and the line which is known to contain the =
solution.

raigan
p.s - @ jonathan: you pretty much gave me the perfect working solution =
-- there was just a single tiny non-obvious caveat!! i think you're =
being hard on yourself ;)




Robert Dibley <bli...@go...> wrote:

How about taking the other view of this =C3=A2=E2=82=AC=E2=80=9C 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.

=20

So you are looking for t such that:

=20

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

=20

( Oh, I=C3=A2=E2=82=AC=E2=84=A2m assuming you have already subtracted =
the velocity of C from everything, since that makes everything much =
easier )

=20

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)) =3D 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.

=20

You can probably do this last bit with a dot product too, since you =
don=C3=A2=E2=82=AC=E2=84=A2t need to do real collision at this point =
=C3=A2=E2=82=AC=E2=80=9C you know it must pass through the point =
(barring fp inaccuracy) so just find :

=20

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

_____________________________

=20

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

=20

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

=20

I=C3=A2=E2=82=AC=E2=84=A2ll leave the long winded expansion to quadratic =
for you to work out :-)

=20

Regards

=20

Robert

=20

=20

  _____ =20

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)

=20

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. =20

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,=20
> right? There are cases where you get 2 crossings.


Yes, but you're usually interested in the intersection that happends=20
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=3Dlnk&kid=3D110944&bid=3D241720&dat=3D=
121642
_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
Archives:
http://sourceforge.net/mailarchive/forum.php?forum_id=3D6188

=20

  _____ =20

Share your photos with the people who matter at  =
<http://photos.yahoo.ca> Yahoo! Canada Photos

=20

  _____ =20

Make Yahoo! Canada your Homepage  <http://ca.yahoo.com/bin/set> Yahoo! =
Canada Homepage=20