Playing perfect Tetris: how to align and scale two curves using scaling and translation?

Question

Given parameters of scaling on the y axis (s) and translation on the x axis (t), how to scale and align two curves that do not coincide when the purpose is to maximize curve superposition (not minimize distance)? As indicated by @DWin, this could be rebranded "How to play Tetris perfectly with R", though it does have applications far beyond winning a Tetris game. A variation of this question could involve any number of rigid body transformations (rotation, translation and scaling). Given curve 1 ``` curve1<-data.frame(x=c(1,1,2,2,3), y=c(9,6,6,3,3)) with(curve1, plot(x=x, y=y, type="l", xlim=c(0,10), ylim=c(0,10))) ``` and curve 2 ``` curve2<-data.frame(x=c(4,5,5,6,6,7), y=c(2,2,1,1,2,3)) with(curve2, plot(x=x, y=y, type="l", xlim=c(0,10), ylim=c(0,10))) ``` I wish to find s and t that maximize superposition between the two curves. Ideally the method would be in R using optim. In this made up example, t=3 and s=1/3, so that ``` t=3 s=1/3 with(curve2, plot(x=x, y=y, type="l", xlim=c(0,…

Accepted Answer

This will return the distances between the points when curve1 is scaled on the y-axis by a factor "tfac" and moved on the x-axis by an amount "s":

```
 as.matrix( dist( rbind(as.matrix(curve2), 
                 ( matrix(c(rep(s, 5), rep(1,5)), ncol=2) +   # x-shift matrix
                                       as.matrix(curve1) ) %*% 
                   matrix(c( 1, 0, 0, tfac),ncol=2) ) ) # the y-scaling matrix
                )[ 
                           # better not to use 't' as a variable name
      -(1:5), -(6:11)]  # easier to return the relevant distances when in matrix
```

It should be a simple matter to put that in a function to be minimized:

```
 dfunc <- function(C1, C2, s, tfac) { sum( .... ) }
```

I'm not absolutely sure this will return the result you are expecting since the objective function you are implying may not be the sum of distances. You may need to turn to integer programming methods. The Optimization CRAN Task View would be a good place to look for those methods in R. I suppose an alternative if this problem arises might be to round the "s" value and scale only to the nearest power of 2.

```
dfunc <- function(param, D1=curve1, D2=curve2) { 
           sum( as.matrix(dist( 
                   rbind(as.matrix(D2), 
                         ( matrix(c(rep(param[1], 5), rep(1,5)), ncol=2) + 
                           as.matrix(D1) ) %*% 
                   matrix(c(1,0,0,param[2]),ncol=2) ) ) )[-(1:5), -(6:11)])}
optim(c(1,1), dfunc)
#$par
$[1] 3.3733977 0.2243866
# trimmed output
```

Using these values one obtains the following superposition:

I might, therefore, try s=3, tfac=0.25. (I see looking back that I switched the roles of t and s from what you asked for. Sorry.)

Playing perfect Tetris: how to align and scale two curves using scaling and translation?

Solution

Problem

Related problems