Closest-pair problem: Difference between revisions

Content added Content deleted

Inline

@@ Line 1,859: / Line 1,859: @@
 	}
 	xp <- x[order(x[,"x"]),]
-	yp <- x[order(x[,"y"]),]
 	.cpdandc.rec <- function(xp,yp)
 	{
@@ Line 1,871: / Line 1,870: @@
 			xl <- xp[1:floor(n/2),]
 			xr <- xp[(floor(n/2)+1):n,]
-			xm <- xp[floor(n/2),"x"]
+			cpl <- .cpdandc.rec(xl)
-			yl <- yp[which(yp[,"x"] <= xm),]
+			cpr <- .cpdandc.rec(xr)
-			yr <- yp[which(yp[,"x"] > xm),]
-			cpl <- .cpdandc.rec(xl,yl)
-			cpr <- .cpdandc.rec(xr,yr)
 			if (cpl$d<cpr$d) cp <- cpl else cp <- cpr
-			dmin <- cp$d
+			cp
+		}
-			ys <- yp[which(abs(xm - yp[,"x"]) < dmin),]
+	}
-			nys <- dim(ys)[1]
+	.cpdandc.rec(xp)
-			if (!is.null(nys) && nys > 1)
+	yp <- x[order(x[,"y"]),]
+	xm <- xp[floor(n/2),"x"]
+	ys <- yp[which(abs(xm - yp[,"x"]) < cp$d),]
+	nys <- dim(ys)[1]
+	if (!is.null(nys) && nys > 1)
+	{
+		for (i in 1:(nys-1))
+		{
+			k <- i + 1
+			while (k <= nys && ys[i,"y"] - ys[k,"y"] < cp$d)
 			{
+				d <- sqrt((ys[k,"x"]-ys[i,"x"])^2 + (ys[k,"y"]-ys[i,"y"])^2)
-				for (i in 1:(nys-1))
+				if (d < cp$d) cp <- list(p1=ys[i,],p2=ys[k,],d=d)
-				{
-					k <- i + 1
+				k <- k + 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
 		}
 	}
+	cp
-	.cpdandc.rec(xp,yp)
 }