Closest-pair problem: Difference between revisions
Content deleted Content added
New method based on divide and conquer pseudocode. |
Optimised divide and conquer method by checking yp only after running through all of xp |
||
Line 1,859:
}
xp <- x[order(x[,"x"]),]
yp <- x[order(x[,"y"]),]▼
.cpdandc.rec <- function(xp,yp)
{
Line 1,871 ⟶ 1,870:
xl <- xp[1:floor(n/2),]
xr <- xp[(floor(n/2)+1):n,]
yr <- yp[which(yp[,"x"] > xm),]▼
cpl <- .cpdandc.rec(xl,yl)▼
if (cpl$d<cpr$d) cp <- cpl else cp <- cpr
}
nys <- dim(ys)[1]▼
if (!is.null(nys) && nys > 1)▼
▲ yp <- x[order(x[,"y"]),]
xm <- xp[floor(n/2),"x"]
{
{
▲ for (i in 1:(nys-1))
▲ {
▲ while (k <= nys && ys[i,"y"] - ys[k,"y"] < dmin)
▲ d <- sqrt((ys[k,"x"]-ys[i,"x"])^2 + (ys[k,"y"]-ys[i,"y"])^2)
▲ if (d < cp$d) cp <- list(p1=ys[i,],p2=ys[k,],d=d)
▲ k <- k + 1
▲ }
}
}
}
cp
}
| |||