Announcement

Collapse
No announcement yet.

Equivalence of directions (a programming question)

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Equivalence of directions (a programming question)

    A direction is a sequence of turns separated by unit distances. A turn is expressed in multiples of pi/10, so a u-turn is +5 or -5. Positive values mean CCW turns.
    We start at origin, heading towards (1,0)
    If I use relative turns (think "turn left", not "go north"), how can I determine if two directions are equivalent (i.e. they lead to the same point)?
    For example, [+1, -2] and [-1, +2], lead to the same point (phi, 0)
    Or [+1, +2, +3] equals [+3] or [+5, -2, -3]
    I know that if I use unit distances I can simply trig my way down to the destination, round the values down to a single decimal and compare them directly, but what if I don't want to or can't use trigonometric functions at all?
    Will switching to absolute (i.e., always measure the turns from A+(1,0)) turns help?

    P.S. Extra geek cred to the one who can guess what task I need this for.
    Graffiti in a public toilet
    Do not require skill or wit
    Among the **** we all are poets
    Among the poets we are ****.

  • #2
    Offhand I'd say that you would probably benefit from using polar coordinates instead of cartesian coordinates, but I haven't used polar coordinates with enough regularity to come up with an algorithm off the top of my head.
    <p style="font-size:1024px">HTML is disabled in signatures </p>

    Comment


    • #3
      Well, yes, a direction is simply a list of polar coordinates, except the distance is always 1.
      Graffiti in a public toilet
      Do not require skill or wit
      Among the **** we all are poets
      Among the poets we are ****.

      Comment


      • #4
        There's no way to do this without trig

        The best way is via polar coords.

        consider a direction as an iterative series of actions (turn plus step) on the following triplex: d,a,h

        h is heading, d is distance from origin, a is angle of current position from x axis.

        I will write out form of iteration when not on phone. Two directions are equivalent if their final triplexes match in d and a (h doesn't matter). Iteration involves law of sines and law of cosines.
        12-17-10 Mohamed Bouazizi NEVER FORGET
        Stadtluft Macht Frei
        Killing it is the new killing it
        Ultima Ratio Regum

        Comment


        • #5
          The iterative step will involve a sqrt, an inverse sine, a sine and a cosine. All other opperations are arithmetic (sums, products). The algo is linear in the number of turns.
          12-17-10 Mohamed Bouazizi NEVER FORGET
          Stadtluft Macht Frei
          Killing it is the new killing it
          Ultima Ratio Regum

          Comment


          • #6
            So the non-trig way to do it with pi/4 turns is a special case, the because the results of trig are rational at every step!?
            Graffiti in a public toilet
            Do not require skill or wit
            Among the **** we all are poets
            Among the poets we are ****.

            Comment


            • #7
              Originally posted by onodera View Post
              P.S. Extra geek cred to the one who can guess what task I need this for.
              You're building a new bar pickup line?

              Comment


              • #8
                Originally posted by VetLegion View Post
                You're building a new bar pickup line?
                I'm happily married, thank you..
                Graffiti in a public toilet
                Do not require skill or wit
                Among the **** we all are poets
                Among the poets we are ****.

                Comment


                • #9
                  You could use a relative control model and translate it to an absolute model behind the scenes by tracking the pose (x, y, θ). Then you only have to store a lookup table implementing the motion model as translations in x and y (pre-computed using trigonometry). If at step t the pose is (xt, yt, θt) and the desired control primitive is dθ, then the resulting pose at time t+1 is (xt + lt[θt + dθ][x], yt + lt[θt + dθ][y], θt + dθ), assuming the rotation precedes a unit translation and that this is a noise-free simulation. In this example lt[θt + dθ][x] corresponds to the lookup table entry for the x component of the translation vector resulting from the motion primitive θt + dθ.

                  SP
                  I got the Jete from C.C. Sabathia. : Jon Miller

                  Comment

                  Working...
                  X