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

SourceForge Headquarters 1320 Columbia Street Suite 310 San Diego, CA 92101 +1 (858) 422-6466

hi,
  it's actually not a problem, as the wire is allowed to change  lengths/compress/stretch. "wire" may be a bit misleading, i just wanted  to distinguish it from the standard rope-as-chain-of-particles ;)

  raigan

Robert Dibley <bli...@go...> wrote:              v\:* {behavior:url(#default#VML);} o\:* {behavior:url(#default#VML);} w\:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);}      st1\:*{behavior:url(#default#ieooui) }                    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âm guessing will save you some work â not a  lot though J

    Incidentally, I donât 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 â but if you have a fast spinning wire, then perhaps it  should be.

    Robert

---------------------------------

    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)

    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). 

  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. 

  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 Ã¢â¬â 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 J

        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 Yahoo! Canada  Photos

---------------------------------

    Make Yahoo! Canada your Homepage Yahoo! Canada Homepage 

---------------------------------
Share your photos with the people who matter at Yahoo! Canada Photos