72 lines
1.7 KiB
Plaintext
72 lines
1.7 KiB
Plaintext
func dist_squared(a, b) {
|
|
sqr(a[0] - b[0]) + sqr(a[1] - b[1])
|
|
}
|
|
|
|
func closest_pair_simple(arr) {
|
|
arr.len < 2 && return Inf
|
|
var (a, b, d) = (arr[0, 1], dist_squared(arr[0,1]))
|
|
arr.clone!
|
|
while (arr) {
|
|
var p = arr.pop
|
|
for l in arr {
|
|
var t = dist_squared(p, l)
|
|
if (t < d) {
|
|
(a, b, d) = (p, l, t)
|
|
}
|
|
}
|
|
}
|
|
return(a, b, d.sqrt)
|
|
}
|
|
|
|
func closest_pair_real(rx, ry) {
|
|
rx.len <= 3 && return closest_pair_simple(rx)
|
|
|
|
var N = rx.len
|
|
var midx = (ceil(N/2)-1)
|
|
var (PL, PR) = rx.part(midx)
|
|
|
|
var xm = rx[midx][0]
|
|
|
|
var yR = []
|
|
var yL = []
|
|
|
|
for item in ry {
|
|
(item[0] <= xm ? yR : yL) << item
|
|
}
|
|
|
|
var (al, bl, dL) = closest_pair_real(PL, yR)
|
|
var (ar, br, dR) = closest_pair_real(PR, yL)
|
|
|
|
al == Inf && return (ar, br, dR)
|
|
ar == Inf && return (al, bl, dL)
|
|
|
|
var (m1, m2, dmin) = (dR < dL ? [ar, br, dR]...
|
|
: [al, bl, dL]...)
|
|
|
|
var yS = ry.grep { |a| abs(xm - a[0]) < dmin }
|
|
|
|
var (w1, w2, closest) = (m1, m2, dmin)
|
|
for i in (0 ..^ yS.end) {
|
|
for k in (i+1 .. yS.end) {
|
|
yS[k][1] - yS[i][1] < dmin || break
|
|
var d = dist_squared(yS[k], yS[i]).sqrt
|
|
if (d < closest) {
|
|
(w1, w2, closest) = (yS[k], yS[i], d)
|
|
}
|
|
}
|
|
}
|
|
|
|
return (w1, w2, closest)
|
|
}
|
|
|
|
func closest_pair(r) {
|
|
var ax = r.sort_by { |a| a[0] }
|
|
var ay = r.sort_by { |a| a[1] }
|
|
return closest_pair_real(ax, ay);
|
|
}
|
|
|
|
var N = 5000
|
|
var points = N.of { [1.rand*20 - 10, 1.rand*20 - 10] }
|
|
var (af, bf, df) = closest_pair(points)
|
|
say "#{df} at (#{af.join(' ')}), (#{bf.join(' ')})"
|