66 lines
1.7 KiB
AutoHotkey
66 lines
1.7 KiB
AutoHotkey
ClosestPair(points){
|
|
if (points.count() <= 3)
|
|
return bruteForceClosestPair(points)
|
|
split := xSplit(Points)
|
|
LP := split.1 ; left points
|
|
LD := ClosestPair(LP) ; recursion : left closest pair
|
|
RP := split.2 ; right points
|
|
RD := ClosestPair(RP) ; recursion : right closest pair
|
|
minD := min(LD, RD) ; minimum of LD & RD
|
|
xmin := Split.3 - minD ; strip left boundary
|
|
xmax := Split.3 + minD ; strip right boundary
|
|
S := strip(points, xmin, xmax)
|
|
if (s.count()>=2)
|
|
{
|
|
SD := ClosestPair(S) ; recursion : strip closest pair
|
|
return min(SD, minD)
|
|
}
|
|
return minD
|
|
}
|
|
;---------------------------------------------------------------
|
|
strip(points, xmin, xmax){
|
|
strip:=[]
|
|
for i, coord in points
|
|
if (coord.1 >= xmin) && (coord.1 <= xmax)
|
|
strip.push([coord.1, coord.2])
|
|
return strip
|
|
}
|
|
;---------------------------------------------------------------
|
|
bruteForceClosestPair(points){
|
|
minD := []
|
|
loop, % points.count()-1{
|
|
p1 := points.RemoveAt(1)
|
|
loop, % points.count(){
|
|
p2 := points[A_Index]
|
|
d := dist(p1, p2)
|
|
minD.push(d)
|
|
}
|
|
}
|
|
return min(minD*)
|
|
}
|
|
;---------------------------------------------------------------
|
|
dist(p1, p2){
|
|
return Sqrt((p2.1-p1.1)**2 + (p2.2-p1.2)**2)
|
|
}
|
|
;---------------------------------------------------------------
|
|
xSplit(Points){
|
|
xL := [], xR := []
|
|
p := xSort(Points)
|
|
Loop % Ceil(p.count()/2)
|
|
xL.push(p.RemoveAt(1))
|
|
while p.count()
|
|
xR.push(p.RemoveAt(1))
|
|
mid := (xL[xl.count(),1] + xR[1,1])/2
|
|
return [xL, xR, mid]
|
|
}
|
|
;---------------------------------------------------------------
|
|
xSort(Points){
|
|
S := [], Res :=[]
|
|
for i, coord in points
|
|
S[coord.1, coord.2] := true
|
|
for x, coord in S
|
|
for y, v in coord
|
|
res.push([x, y])
|
|
return res
|
|
}
|
|
;---------------------------------------------------------------
|