Closest-pair problem: Difference between revisions
Content added Content deleted
PatGarrett (talk | contribs) (→{{header|Microsoft Small Basic}}: Section added) |
(Add Swift) |
||
Line 4,310: | Line 4,310: | ||
=={{header|Smalltalk}}== |
=={{header|Smalltalk}}== |
||
See [[Closest-pair problem/Smalltalk]] |
See [[Closest-pair problem/Smalltalk]] |
||
=={{header|Swift}}== |
|||
<lang swift>import Foundation |
|||
struct Point { |
|||
var x: Double |
|||
var y: Double |
|||
func distance(to p: Point) -> Double { |
|||
let x = pow(p.x - self.x, 2) |
|||
let y = pow(p.y - self.y, 2) |
|||
return (x + y).squareRoot() |
|||
} |
|||
} |
|||
extension Collection where Element == Point { |
|||
func closestPair() -> (Point, Point)? { |
|||
let (xP, xY) = (sorted(by: { $0.x < $1.x }), sorted(by: { $0.y < $1.y })) |
|||
return Self.closestPair(xP, xY)?.1 |
|||
} |
|||
static func closestPair(_ xP: [Element], _ yP: [Element]) -> (Double, (Point, Point))? { |
|||
guard xP.count > 3 else { return xP.closestPairBruteForce() } |
|||
let xl = Array(xP.prefix(xP.count / 2)) |
|||
let xr = Array(xP.suffix(xP.count / 2)) |
|||
let xm = xP.last!.x |
|||
let (yl, yr) = yP.reduce(into: ([Element](), [Element]()), {cur, el in |
|||
if el.x > xm { |
|||
cur.1.append(el) |
|||
} else { |
|||
cur.0.append(el) |
|||
} |
|||
}) |
|||
guard let (distanceL, pairL) = closestPair(Array(xl), yl) else { return nil } |
|||
guard let (distanceR, pairR) = closestPair(Array(xr), yr) else { return nil } |
|||
let (dMin, pairMin) = distanceL > distanceR ? (distanceR, pairR) : (distanceL, pairL) |
|||
let ys = yP.filter({ abs(xm - $0.x) < dMin }) |
|||
var (closest, pairClosest) = (dMin, pairMin) |
|||
for i in 0..<ys.count { |
|||
let p1 = ys[i] |
|||
for k in i+1..<ys.count { |
|||
let p2 = ys[k] |
|||
guard abs(p2.y - p1.y) < dMin else { break } |
|||
let distance = abs(p1.distance(to: p2)) |
|||
if distance < closest { |
|||
(closest, pairClosest) = (distance, (p1, p2)) |
|||
} |
|||
} |
|||
} |
|||
return (closest, pairClosest) |
|||
} |
|||
func closestPairBruteForce() -> (Double, (Point, Point))? { |
|||
guard count >= 2 else { return nil } |
|||
var closestPoints = (self.first!, self[index(after: startIndex)]) |
|||
var minDistance = abs(closestPoints.0.distance(to: closestPoints.1)) |
|||
guard count != 2 else { return (minDistance, closestPoints) } |
|||
for i in 0..<count-1 { |
|||
for j in i+1..<count { |
|||
let (iIndex, jIndex) = (index(startIndex, offsetBy: i), index(startIndex, offsetBy: j)) |
|||
let (p1, p2) = (self[iIndex], self[jIndex]) |
|||
let distance = abs(p1.distance(to: p2)) |
|||
if distance < minDistance { |
|||
minDistance = distance |
|||
closestPoints = (p1, p2) |
|||
} |
|||
} |
|||
} |
|||
return (minDistance, closestPoints) |
|||
} |
|||
} |
|||
var points = [Point]() |
|||
for _ in 0..<10_000 { |
|||
points.append(Point( |
|||
x: .random(in: -10.0...10.0), |
|||
y: .random(in: -10.0...10.0) |
|||
)) |
|||
} |
|||
print(points.closestPair()!)</lang> |
|||
{{out}} |
|||
<pre>(Point(x: 5.279430517795172, y: 8.85108182685002), Point(x: 5.278427575530877, y: 8.851990433099456))</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |