玩完美的俄罗斯方块：如何使用缩放和平移来对齐和缩放两条曲线？ [英] Playing perfect Tetris: how to align and scale two curves using scaling and translation?

问题描述

给定y轴缩放参数和x轴平移（t）参数，当目的是最大化曲线叠加（而不是最小距离）时，如何缩放和对齐两条不重合的曲线？

/ p>

正如@DWin所指出的那样，这可能会被重新命名为如何与R完美地玩俄罗斯方块，尽管它的应用远远超越了俄罗斯方块游戏。

这个问题的一个变体可能涉及到任意数量的刚体转换（旋转，平移和缩放）。

给定曲线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）））
  

和曲线2

  curve2< -data.frame（x = c（4,5,5,6,6,7），
y = c（2,2,1,1 ，2,3））$ b $ （曲线2，plot（x = x，y = y，type =l，xlim = c（0,10），ylim = c（0,10）））
  

我希望找到使两条曲线之间的叠加最大化的s和t。理想情况下，在这个例子中，t = 3和s = 1/3，所以
$ b $在b中使用optim。

$ b

  t = 3 
s = 1/3 
 
 with（curve2，plot（x = x，y = y，type =l ，xlim = c（0,10），ylim = c（0,10）））
 
 with（curve1，lines（x = x + t，y = y * s，col =红色））
  

我一直在探索的路线：

最小化曲线之间的区域

重叠两条曲线的算法

使用形状包进行形状分析

迭代最近点（ICP） 如果某人在R中实现了它，或者可以移植其中一个C实现

使用最大可能性（假设错误分布正态分布）的方法的加分点。

解决方案

这将返回曲线1在y轴上缩放因子tfac并移动的点之间的距离在x轴上的量为s：

  as.matrix（dist（rbind（as.matrix（curve2） ，
（矩阵（c（rep（s，5），rep（1， 5）），ncol = 2）+＃x移位矩阵
 as.matrix（curve1））％*％
矩阵（c（1,0,0，tfac），ncol = 2）） ）＃y尺度矩阵
）[
＃最好不要用't'作为变量名称
  - （1：5）， - （6:11）]＃更容易在矩阵中返回相关距离
  

将函数放入函数应该是一件简单的事情最小化：

  dfunc < -  function（C1，C2，s，tfac）{sum（....）} 
  

我不确定这会返回您期望的结果，因为您所暗示的目标函数可能会不是距离的总和。您可能需要转向整数编程方法。优化CRAN任务视图将是在R中查找这些方法的好地方。如果出现此问题，我认为可以选择舍入s值并仅缩放到最接近2的幂。 b
$ b

  dfunc < - 函数（参数，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））％*％
矩阵（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 
  

使用这些值可以得到以下叠加：

因此，我可能尝试s = 3，tfac = 0.25。 （我回头看，我把t和s的角色从你所要求的转换过来，抱歉。）

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,10), ylim=c(0,10)))

with(curve1, lines(x=x+t, y=y*s, col="red"))

Note that to obtain such a fitting, regions that can have a consensus must have a higher weight on parametrization than regions that can not be superimposed and that the larger the consensus region the higher the weight.

Trails I have been exploring:

minimize area between curves

algorithm for superposing two curves

shape analysis using the shapes package

Iterative closest point (ICP) if someone has implemented it in R or can port one of the C implementations

Bonus points for a method using maximum likelihood (assuming normal distribution of error).

解决方案

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

这篇关于玩完美的俄罗斯方块：如何使用缩放和平移来对齐和缩放两条曲线？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！