如何停止隨機遊走

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