Make right hand turns

Question

I have a problem where I have a bunch of lengths and want to start at the origin (pretend I'm facing to the positive end of the y axis), I make a right and move positively along the x axis for the distance of length_i. At this time I make another right turn, walk the distance of length_i and repeat n times. I can do this but I think there's a more efficient way to do it and I lack a math background:

## Fake Data
set.seed(11)
dat <- data.frame(id = LETTERS[1:6], lens=sample(2:9, 6), 
    x1=NA, y1=NA, x2=NA, y2=NA)

##   id lens x1 y1 x2 y2
## 1  A    4 NA NA NA NA
## 2  B    2 NA NA NA NA
## 3  C    5 NA NA NA NA
## 4  D    8 NA NA NA NA
## 5  E    6 NA NA NA NA
## 6  F    9 NA NA NA NA

## Add a cycle of 4 column    
dat[, "cycle"] <- rep(1:4, ceiling(nrow(dat)/4))[1:nrow(dat)]

##For loop to use the information from cycle column
for(i in 1:nrow(dat)) {

    ## set x1, y1
    if (i == 1) {
       dat[1, c("x1", "y1")] <- 0
    } else {
       dat[i, c("x1", "y1")] <- dat[(i - 1), c("x2", "y2")]
    }

    col1 <- ifelse(dat[i, "cycle"] %% 2 == 0, "x1", "y1")
    col2 <- ifelse(dat[i, "cycle"] %% 2 == 0, "x2", "y2")
    dat[i, col2] <- dat[i, col1]

    col3 <- ifelse(dat[i, "cycle"] %% 2 != 0, "x2", "y2")
    col4 <- ifelse(dat[i, "cycle"] %% 2 != 0, "x1", "y1")
    mag <- ifelse(dat[i, "cycle"] %in% c(1, 4), 1, -1)
    dat[i, col3] <- dat[i, col4] + (dat[i, "lens"] * mag)

}

This gives the desired result:

> dat

  id lens x1 y1 x2 y2 cycle
1  A    4  0  0  4  0     1
2  B    2  4  0  4 -2     2
3  C    5  4 -2 -1 -2     3
4  D    8 -1 -2 -1  6     4
5  E    6 -1  6  5  6     1
6  F    9  5  6  5 -3     2

Here it is as a plot:

library(ggplot2); library(grid)
ggplot(dat, aes(x = x1, y = y1, xend = x2, yend = y2)) + 
    geom_segment(aes(color=id), size=3, arrow = arrow(length = unit(0.5, "cm"))) + 
    ylim(c(-10, 10)) + xlim(c(-10, 10))

This seems slow and clunky. I'm guessing there's a better way to do this than the items I do in the for loop. What's a more efficient way to keep making programatic rights?

Answer 1

(As suggested by @DWin) Here is a solution using complex numbers, which is flexible to any kind of turn, not just 90 degrees (-pi/2 radians) right angles. Everything is vectorized:

set.seed(11)
dat <- data.frame(id = LETTERS[1:6], lens = sample(2:9, 6),
                                     turn = -pi/2)

dat <- within(dat, { facing   <- pi/2 + cumsum(turn)
                     move     <- lens * exp(1i * facing)
                     position <- cumsum(move)
                     x2       <- Re(position)
                     y2       <- Im(position)
                     x1       <- c(0, head(x2, -1))
                     y1       <- c(0, head(y2, -1))
                   })

dat[c("id", "lens", "x1", "y1", "x2", "y2")]
#   id lens x1 y1 x2 y2
# 1  A    4  0  0  4  0
# 2  B    2  4  0  4 -2
# 3  C    5  4 -2 -1 -2
# 4  D    8 -1 -2 -1  6
# 5  E    6 -1  6  5  6
# 6  F    9  5  6  5 -3

The turn variable should really be considered as an input together with lens. Right now all turns are -pi/2 radians but you can set each one of them to whatever you want. All other variables are outputs.

---

Now having a little fun with it:

trace.path <- function(lens, turn) {
  facing   <- pi/2 + cumsum(turn)
  move     <- lens * exp(1i * facing)
  position <- cumsum(move)
  x        <- c(0, Re(position))
  y        <- c(0, Im(position))

  plot.new()
  plot.window(range(x), range(y))
  lines(x, y)
}

trace.path(lens = seq(0, 1,  length.out = 200),
           turn = rep(pi/2 * (-1 + 1/200), 200))

(My attempt at replicating the graph here: http://en.wikipedia.org/wiki/Turtle_graphics)

I also let you try these:

trace.path(lens = seq(1, 10, length.out = 1000),
           turn = rep(2 * pi / 10, 1000))

trace.path(lens = seq(0, 1,  length.out = 500),
           turn = seq(0, pi, length.out = 500))

trace.path(lens = seq(0, 1,  length.out = 600) * c(1, -1),
           turn = seq(0, 8*pi, length.out = 600) * seq(-1, 1, length.out = 200))

Feel free to add yours!

Answer 2

This is yet another method using complex numbers. You can rotate a vector "to the right" in the complex plane by multiplying by -1i. The code below makes the first traversal go in the positive X (the Re()-al axis) and each subsequent traversal would be rotated to the "right"

imVecs <- lengths*c(0-1i)^(0:3)
imVecs
# [1]  9+0i  0-5i -9+0i  0+9i  8+0i  0-5i -8+0i  0+7i  8+0i  0-1i -5+0i  0+3i  4+0i  0-7i -4+0i  0+2i
#[17]  3+0i  0-7i -5+0i  0+8i

cumsum(imVecs)
# [1] 9+0i 9-5i 0-5i 0+4i 8+4i 8-1i 0-1i 0+6i 8+6i 8+5i 3+5i 3+8i 7+8i 7+1i 3+1i 3+3i 6+3i 6-4i 1-4i
#[20] 1+4i
plot(cumsum(imVecs))
lines(cumsum(imVecs))

This is the approach to using complex plane rotations to do 45 degree turns to the right:

> sqrt(-1i)
[1] 0.7071068-0.7071068i
> imVecs <- lengths*sqrt(0-1i)^(0:7)
Warning message:
In lengths * sqrt(0 - (0+1i))^(0:7) :
  longer object length is not a multiple of shorter object length
> plot(cumsum(imVecs))
> lines(cumsum(imVecs))

And the plot:

Answer 3

This isn't a pretty plot, but I've included it to show that this 'vectorized' coordinate calculation produces correct results which shouldn't be too hard to adapt to your needs:

xx <- c(1,0,-1,0)
yy <- c(0,-1,0,1)

coords <- suppressWarnings(cbind(x = cumsum(c(0,xx*dat$lens)), 
                                 y = cumsum(c(0,yy*dat$lens))))
plot(coords, type="l", xlim=c(-10,10), ylim=c(-10,10))

Answer 4

It might be useful to think about this in terms of distance and bearing. Distance is given by dat$lens, and bearing is the angle of movement relative to some arbitrary reference line (say, the x-axis). Then, at each step,

x.new = x.old + distance * cos(bearing)
y.new = y.old + distance * sin(bearing)
bearing = bearing + increment

Here, since we start at the origin and move in the +x direction, (x,y)=(0,0) and bearing starts at 0 degrees. A right turn is simply a bearing increment of -90 degrees (-pi/2 radians). So in R code, using your definition of dat:

x <-0
y <- 0
bearing <- 0
for (i in 1:nrow(dat)){
  dat[i,c(3,4)] <- c(x,y)
  length <- dat[i,2]
  x <- x + length * cos(bearing)
  y <- y + length * sin(bearing)
  dat[i,c(5,6)] <- c(x,y)
  bearing <- bearing - pi/2
}

This produces what you had and has the advantage that you can update it very simply to make left turns, or 45 degree turns, or whatever. You can even add a bearing.increment column to dat to create a random walk.

Answer 5

Very similar to Josh's solution:

lengths <- sample(1:10, 20, repl=TRUE)
x=cumsum(lengths*c(1,0,-1,0))
y=cumsum(lengths*c(0,1,0,-1))
cbind(x,y)
      x  y
 [1,] 9  0
 [2,] 9  5
 [3,] 0  5
 [4,] 0 -4
 [5,] 8 -4
 [6,] 8  1
 [7,] 0  1
 [8,] 0 -6
 [9,] 8 -6
[10,] 8 -5
[11,] 3 -5
[12,] 3 -8
[13,] 7 -8
[14,] 7 -1
[15,] 3 -1
[16,] 3 -3
[17,] 6 -3
[18,] 6  4
[19,] 1  4
[20,] 1 -4

Base graphics:

plot(cbind(x,y))
arrows(cbind(x,y)[-20,1],cbind(x,y)[-20,2], cbind(x,y)[-1,1], cbind(x,y)[-1,2] )

This does highlight the fact that both Josh's and my solutions are "turning the wrong way", so you need to change the signs on our "transition matrices". And we probably should have started at (0,0), but You should have not trouble adapting this you your needs.