85 lines
2.6 KiB
Text
85 lines
2.6 KiB
Text
import "./math" for Math
|
|
import "./sort" for Sort
|
|
|
|
var distance = Fn.new { |p1, p2| Math.hypot(p1[0] - p2[0], p1[1] - p2[1]) }
|
|
|
|
var bruteForceClosestPair = Fn.new { |p|
|
|
var n = p.count
|
|
if (n < 2) Fiber.abort("There must be at least two points.")
|
|
var minPoints = [p[0], p[1]]
|
|
var minDistance = distance.call(p[0], p[1])
|
|
for (i in 0...n-1) {
|
|
for (j in i+1...n) {
|
|
var dist = distance.call(p[i], p[j])
|
|
if (dist < minDistance) {
|
|
minDistance = dist
|
|
minPoints = [p[i], p[j]]
|
|
}
|
|
}
|
|
}
|
|
return [minDistance, minPoints]
|
|
}
|
|
|
|
var optimizedClosestPair // recursive so pre-declare
|
|
optimizedClosestPair = Fn.new { |xP, yP|
|
|
var n = xP.count
|
|
if (n <= 3) return bruteForceClosestPair.call(xP)
|
|
var hn = (n/2).floor
|
|
var xL = xP.take(hn).toList
|
|
var xR = xP.skip(hn).toList
|
|
var xm = xP[hn-1][0]
|
|
var yL = yP.where { |p| p[0] <= xm }.toList
|
|
var yR = yP.where { |p| p[0] > xm }.toList
|
|
var ll = optimizedClosestPair.call(xL, yL)
|
|
var dL = ll[0]
|
|
var pairL = ll[1]
|
|
var rr = optimizedClosestPair.call(xR, yR)
|
|
var dR = rr[0]
|
|
var pairR = rr[1]
|
|
var dmin = dR
|
|
var pairMin = pairR
|
|
if (dL < dR) {
|
|
dmin = dL
|
|
pairMin = pairL
|
|
}
|
|
var yS = yP.where { |p| (xm - p[0]).abs < dmin }.toList
|
|
var nS = yS.count
|
|
var closest = dmin
|
|
var closestPair = pairMin
|
|
for (i in 0...nS-1) {
|
|
var k = i + 1
|
|
while (k < nS && (yS[k][1] - yS[i][1] < dmin)) {
|
|
var dist = distance.call(yS[k], yS[i])
|
|
if (dist < closest) {
|
|
closest = dist
|
|
closestPair = [yS[k], yS[i]]
|
|
}
|
|
k = k + 1
|
|
}
|
|
}
|
|
return [closest, closestPair]
|
|
}
|
|
|
|
var points = [
|
|
[ [5, 9], [9, 3], [2, 0], [8, 4], [7, 4], [9, 10], [1, 9], [8, 2], [0, 10], [9, 6] ],
|
|
|
|
[
|
|
[0.654682, 0.925557], [0.409382, 0.619391], [0.891663, 0.888594],
|
|
[0.716629, 0.996200], [0.477721, 0.946355], [0.925092, 0.818220],
|
|
[0.624291, 0.142924], [0.211332, 0.221507], [0.293786, 0.691701],
|
|
[0.839186, 0.728260]
|
|
]
|
|
]
|
|
|
|
for (p in points) {
|
|
var dp = bruteForceClosestPair.call(p)
|
|
var dist = dp[0]
|
|
var pair = dp[1]
|
|
System.print("Closest pair (brute force) is %(pair[0]) and %(pair[1]), distance %(dist)")
|
|
var xP = Sort.merge(p) { |x, y| (x[0] - y[0]).sign }
|
|
var yP = Sort.merge(p) { |x, y| (x[1] - y[1]).sign }
|
|
dp = optimizedClosestPair.call(xP, yP)
|
|
dist = dp[0]
|
|
pair = dp[1]
|
|
System.print("Closest pair (optimized) is %(pair[0]) and %(pair[1]), distance %(dist)\n")
|
|
}
|