如何停止随机游走

Question

plot(0:70,0:70, type="n", xlab="X", ylab="Y") 

x<-40 
y<-40 

x2<-60 
y2<-60 

points(x, y, pch=16, col="red", cex=1.5) 
points(x2, y2, pch=16, col="green", cex=1.5) 

for (i in 1:10000){ 
    xi<-sample(c(1,0,-1),1) 
    yi<-sample(c(1,0,-1),1) 
    x2i<-sample(c(1,0,-1),1) 
    y2i<-sample(c(1,0,-1),1) 
    lines(c(x,x+xi),c(y,y+yi)) 
    lines(c(x2,x2+x2i),c(y2,y2+y2i), col="red") 
    x<-x+xi 
    y<-y+yi 
    x2<-x2+x2i 
    y2<-y2+y2i 
    if(x2==x && y==y2) { 
     break 
    } 
} 

我有两条线随机游走，当两条线相遇时我需要停下来。

首先，我画了一个空的情节和两条线的起点。然后我有这个for循环的线条移动，绘制他们的情节，并获得新的开始点，为下一次迭代。

我试图让它停在线使用时停下来：if(x2==x && y==y2) { break }但线只停止，如果他们在同一点上，并在同一时间（在同一迭代），我需要他们停止，如果其中之一穿过另一个。如果有人穿过任何已经为另一条线划出的点。我认为问题在于，已经绘制的点没有保存在任何地方，所以我无法将它们与点的线进行比较。也许我需要保存循环中的点？有人知道如何阻止它？

Answer 1

N  <- 10000 
D  <- 1 
coef.1 <- matrix(NA,N,2) 
coef.2 <- matrix(NA,N,2) 
path.1 <- matrix(NA,N,2) 
path.2 <- matrix(NA,N,2) 
path.1[1,] <- c(40,40) 
path.2[1,] <- c(60,60) 
d.start <- sqrt(sum((path.1[1,]-path.2[1,])^2)) 
ch <- "." 
set.seed(1) 
system.time({ 
    for (i in 2:N){ 
    if (i%%50==0) cat(ch) 
    path.1[i,] <- path.1[i-1,] + sample(-D:D,2) 
    path.2[i,] <- path.2[i-1,] + sample(-D:D,2) 
    coef.1[i,] <- get.line(path.1[(i-1):i,]) 
    coef.2[i,] <- get.line(path.2[(i-1):i,]) 
    r.1 <- sqrt(max(rowSums((path.1[1:i,]-path.1[1,])^2))) 
    r.2 <- sqrt(max(rowSums((path.2[1:i,]-path.2[1,])^2))) 
    if (r.1+r.2 < d.start) next # paths do not overlap 
    ch <- "1" 
    d.1 <- sqrt(min(rowSums((path.2[1:i,]-path.1[1,])^2))) 
    d.2 <- sqrt(min(rowSums((path.1[1:i,]-path.2[1,])^2))) 
    if (d.1>r.1 & d.2>r.2) next 
    ch <- "2" 
    cross <- sapply(2:i, 
       function(k){seg.intersect(path.2[(k-1):k,],path.1[(i-1):i,],k)}) 
    if (any(cross)) break 
    cross <- sapply(2:i, 
       function(k){seg.intersect(path.1[(k-1):k,],path.2[(i-1):i,],k)}) 
    if (any(cross)) break 
    } 
}) 
# 11111111112222222222222222222222 
# user system elapsed 
# 1016.82 0.13 1024.18 
print(paste("End at Step: ",i)) 
# [1] "End at Step: 1624" 
plot(0:100,0:100, type="n", xlab="X", ylab="Y") 
points(path.1[1,1],path.1[1,2], pch=16, col="red", cex=1.5) 
points(path.2[1,1],path.2[1,2], pch=16, col="green", cex=1.5) 
lines(path.1[1:i,]) 
lines(path.2[1:i,],col="red") 

由于@CarlWitthoft所指出的，在每一个步骤必须检查所有之前的线段的交叉点。这产生了一个严重的问题，因为在每个新步骤i处，都有2*(i-1)测试过境。因此，如果您在步骤k处遇到道口，将会有2*k*(k+1)测试。如果k ~O(10000)，则可能有潜在的100MM测试。

为了提高效率，我们不仅存储每一步的两个新点，还存储新创建的线段的斜率和截距。这避免了重新计算每个步骤之前的所有线段的斜率和截距。另外，我们计算每一步每个路径的路径半径r。这是起点和距离起点最远的路径上的点之间的距离。如果路径起点与其他路径上最近点之间的距离大于路径半径，则不会出现交叉，我们可以跳过此步骤的单个段比较。

您的问题有其他原因。测试交叉口的正常方法是确定两条线之间的交点是否在任一段上。这很麻烦但直截了当。但是有很多特殊情况：线是否平行？如果是这样，它们是否重合？如果是的话，这些细分重叠？垂直线（斜率= Inf）如何？因为您将增量设置为[-1,1]上的随机整数，所有这些可能性很可能最终发生在具有10000步的路径中。所以上面的函数seg.intersect(...)必须考虑所有这些可能性。你会认为在R中有一个函数是这样的，但我找不到一个，所以这里是一个（凌乱的）版本：

get.line <- function(l) {  # returns slope and intercept 
    if (diff(l)[1]==0) return(c(Inf,NA)) 
    m <- diff(l)[2]/diff(l)[1] 
    b <- l[1,2]-m*l[1,1] 
    return(c(m,b)) 
} 
is.between <- function(x,vec) { # test if x is between values in vec 
    return(x>=range(vec)[1] & x<=range(vec)[2]) 
} 
special.cases = function(l1,l2, coeff) { 
    # points coincide: not a line segment! 
    if (rowSums(diff(l1)^2)==0 | rowSums(diff(l2)^2)==0) return(c(NA,FALSE)) 
    # both lines vertical 
    if (is.infinite(coeff[1,1]) & is.infinite(coeff[2,1])) { 
    if (l1[1,1]!=l2[1,1]) return(c(NA,FALSE)) 
    t1 <- is.between(l1[1,2],l2[,2]) | is.between(l1[2,2],l2[,2]) 
    t2 <- is.between(l2[1,2],l1[,2]) | is.between(l2[2,2],l1[,2]) 
    return(c(NA,t1|t2)) 
    } 
    # only l1 is vertical 
    if (is.infinite(coeff[1,1]) & is.finite(coeff[2,1])) { 
    x <- l1[1,1] 
    y <- c(x,1) %*% coeff[2,] 
    return(c(x,y)) 
    } 
    # only l2 is vertical 
    if (is.finite(coeff[1,1]) & is.infinite(coeff[2,1])) { 
    x <- l2[1,1] 
    y <- c(x,1) %*% coeff[1,] 
    return(c(x,y)) 
    } 
    # parallel, non-coincident lines 
    if (diff(coeff[,1])==0 & diff(coeff[,2])!=0) return(c(NA,FALSE)) 
    # parallel, coincident lines 
    if (diff(coeff[,1])==0 & diff(coeff[,2])==0) { 
    x <- l1[1,1] 
    y <- l1[1,2] 
    return(c(x,y)) 
    } 
    # base case: finite slopes, not parallel 
    x <- -diff(coeff[,2])/diff(coeff[,1]) 
    y <- c(x,1) %*% coeff[1,] 
    return(c(x,y)) 
} 
seg.intersect <- function(l1,l2,i){ 
    pts <- list(l1,l2) 
    coeff <- rbind(coef.1[i,],coef.2[i,]) 
    z <- special.cases(l1,l2, coeff) 
    if (is.na(z[1])) return (z[2]) 
    # print(coeff) 
    # print(z) 
    found <- do.call("&", 
    lapply(pts,function(x){is.between(z[1],x[,1]) & is.between(z[2],x[,2])})) 
    return(found) 
}