Closest-pair problem: Difference between revisions
PascalABC.NET
Alpha bravo (talk | contribs) (Added AutoHotkey) |
(PascalABC.NET) |
||
(24 intermediate revisions by 14 users not shown) | |||
Line 1:
[[Category:Geometry]]
{{task|Classic CS problems and programs}}
{{Wikipedia|Closest pair of points problem}}
Line 67 ⟶ 68:
* [http://www.cs.iupui.edu/~xkzou/teaching/CS580/Divide-and-conquer-closestPair.ppt Closest pair (IUPUI)]
<br><br>
=={{header|360 Assembly}}==
<
CLOSEST CSECT
USING CLOSEST,R13 base register
Line 197:
PG DS CL80
YREGS
END CLOSEST</
{{out}}
<pre>
Line 205:
[ 0.925092, 0.818220]
</pre>
=={{header|Ada}}==
Dimension independent, but has to be defined at procedure call time
Line 212 ⟶ 211:
closest.adb: (uses brute force algorithm)
<
with Ada.Text_IO;
Line 278 ⟶ 277:
Ada.Text_IO.Put_Line ("P2: " & Float'Image (Second_Points (2) (1)) & " " & Float'Image (Second_Points (2) (2)));
Ada.Text_IO.Put_Line ("Distance: " & Float'Image (Distance (Second_Points (1), Second_Points (2))));
end Closest;</
{{out}}
Line 289 ⟶ 288:
P2: 9.25092E-01 8.18220E-01
Distance: 7.79101E-02</pre>
=={{header|AutoHotkey}}==
<
if (points.count() <= 3)
return bruteForceClosestPair(points)
Line 356 ⟶ 354:
return res
}
;---------------------------------------------------------------</
Examples:<
MsgBox % ClosestPair(points)</
{{out}}
<pre>1.000000</pre>
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f CLOSEST-PAIR_PROBLEM.AWK
BEGIN {
Line 390 ⟶ 387:
exit(0)
}
</syntaxhighlight>
{{out}}
<pre>
Line 396 ⟶ 393:
</pre>
=={{header|
==={{header|BASIC256}}===
'''Versión de fuerza bruta:
<syntaxhighlight lang="basic256">
Dim x(9)
x = {0.654682, 0.409382, 0.891663, 0.716629, 0.477721, 0.925092, 0.624291, 0.211332, 0.293786, 0.839186}
Line 413 ⟶ 411:
Print "El par más cercano es "; minDisti; " y "; minDistj; " a una distancia de "; Sqr(minDist)
End
</syntaxhighlight>
{{out}}
<pre>
Line 419 ⟶ 417:
</pre>
==={{header|BBC BASIC}}===
To find the closest pair it is sufficient to compare the squared-distances,
it is not necessary to perform the square root for each pair!
<
FOR I% = 0 TO 9
Line 448 ⟶ 446:
DATA 0.293786, 0.691701
DATA 0.839186, 0.728260
</syntaxhighlight>
{{out}}
<pre>Closest pair is 2 and 5 at distance 0.0779101913</pre>
=={{header|C}}==
See [[Closest-pair problem/C]]
=={{header|C sharp|C#}}==
We provide a small helper class for distance comparisons:
<
{
public Segment(PointF p1, PointF p2)
Line 478 ⟶ 474:
+ (P1.Y - P2.Y) * (P1.Y - P2.Y);
}
}</
Brute force:
<
{
int n = points.Count;
Line 491 ⟶ 487:
return result;
}</
And divide-and-conquer.
<
public static Segment MyClosestDivide(List<PointF> points)
{
Line 546 ⟶ 542:
return result;
}
</syntaxhighlight>
However, the difference in speed is still remarkable.
<
var points = Enumerable.Range( 0, 10000).Select( i => new PointF( (float)randomizer.NextDouble(), (float)randomizer.NextDouble())).ToList();
Stopwatch sw = Stopwatch.StartNew();
Line 559 ⟶ 555:
sw2.Stop();
Debugger.Log(1, "", string.Format("Time used (Divide & Conquer): {0} ms",sw2.Elapsed.TotalMilliseconds));
Assert.Equal(r1.Length(), result2.Length());</
{{out}}
Line 566 ⟶ 562:
Non Linq Brute Force:
<
Segment Closest_BruteForce(List<PointF> points)
{
Line 587 ⟶ 583:
return result;
}</
Targeted Search: Much simpler than divide and conquer, and actually runs faster for the random points. Key optimization is that if the distance along the X axis is greater than the best total length you already have, you can terminate the inner loop early. However, as only sorts in the X direction, it degenerates into an N^2 algorithm if all the points have the same X.
<
Segment Closest(List<PointF> points)
{
Line 626 ⟶ 622:
return result;
}
</syntaxhighlight>
=={{header|C++}}==
<
Author: Kevin Bacon
Date: 04/03/2014
Line 743 ⟶ 738:
print_point(answer.second.second);
return 0;
}</
{{out}}
<pre>Min distance (brute): 6.95886 (932.735, 1002.7), (939.216, 1000.17)
Min distance (optimized): 6.95886 (932.735, 1002.7), (939.216, 1000.17)</pre>
=={{header|Clojure}}==
<
(defn distance [[x1 y1] [x2 y2]]
(let [dx (- x2 x1), dy (- y2 y1)]
Line 788 ⟶ 782:
{yS true} (group-by (fn [[px _]] (< (Math/abs (- xm px)) dmin)) yP)]
(combine yS [dmin pmin1 pmin2])))))
</syntaxhighlight>
=={{header|Common Lisp}}==
Points are conses whose cars are x coördinates and whose cdrs are y coördinates. This version includes the optimizations given in the [http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairDQ.html McGill description] of the algorithm.
<
(destructuring-bind (x1 . y1) p1
(destructuring-bind (x2 . y2) p2
Line 848 ⟶ 841:
(multiple-value-bind (pair distance)
(cp (sort (copy-list points) '< :key 'car))
(values pair distance))))</
=={{header|Crystal}}==
=={{header|D}}==
===Compact Versions===
<
std.random, std.traits, std.range, std.complex;
Line 927 ⟶ 918:
writeln("bruteForceClosestPair: ", points.bruteForceClosestPair);
writeln(" closestPair: ", points.closestPair);
}</
{{out}}
<pre>[5+9i, 9+3i, 2+0i, 8+4i, 7+4i, 9+10i, 1+9i, 8+2i, 0+10i, 9+6i]
Line 937 ⟶ 928:
===Faster Brute-force Version===
<
std.traits;
Line 975 ⟶ 966:
writefln("Closest pair: Distance: %f p1, p2: %f, %f",
abs(pts[ij[0]] - pts[ij[1]]), pts[ij[0]], pts[ij[1]]);
}</
{{out}}
<pre>Closest pair: Distance: 0.019212 p1, p2: 9.74223+119.419i, 9.72306+119.418i</pre>
About 0.12 seconds run-time for brute-force version 2 (10_000 points) with with LDC2 compiler.
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Closest-pair_problem#Pascal Pascal].
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight>
# bruteforce
numfmt 4 0
x[] = [ 0.654682 0.409382 0.891663 0.716629 0.477721 0.925092 0.624291 0.211332 0.293786 0.839186 ]
y[] = [ 0.925557 0.619391 0.888594 0.996200 0.946355 0.818220 0.142924 0.221507 0.691701 0.728260 ]
n = len x[]
min = 1 / 0
for i to n - 1
for j = i + 1 to n
dx = x[i] - x[j]
dy = y[i] - y[j]
dsq = dx * dx + dy * dy
if dsq < min
min = dsq
mini = i
minj = j
.
.
.
print "distance between (" & x[mini] & " " & y[mini] & ") and (" & x[minj] & " " & y[minj] & ") is " & sqrt min
</syntaxhighlight>
=={{header|Elixir}}==
<
# brute-force algorithm:
def bruteForce([p0,p1|_] = points), do: bf_loop(points, {distance(p0, p1), {p0, p1}})
Line 1,039 ⟶ 1,055:
IO.inspect :timer.tc(fn -> Closest_pair.bruteForce(data2) end)
IO.puts "Recursive divide&conquer:"
IO.inspect :timer.tc(fn -> Closest_pair.recursive(data2) end)</
{{out}}
Line 1,060 ⟶ 1,076:
=={{header|F Sharp|F#}}==
Brute force:
<
let closest_pairs (xys: Point []) =
let n = xys.Length
Line 1,067 ⟶ 1,083:
yield xys.[i], xys.[j] }
|> Seq.minBy (fun (p0, p1) -> (p1 - p0).LengthSquared)
</syntaxhighlight>
For example:
<
closest_pairs
[|Point(0.0, 0.0); Point(1.0, 0.0); Point (2.0, 2.0)|]
</syntaxhighlight>
gives:
<
(0,0, 1,0)
</syntaxhighlight>
Divide And Conquer:
<
open System;
Line 1,171 ⟶ 1,187:
printfn "Closest Pair '%A'. Distance %f" closest (Length closest)
printfn "Took %d [ms]" takenMs
</syntaxhighlight>
=={{header|Fantom}}==
(Based on the Ruby example.)
<
class Point
{
Line 1,296 ⟶ 1,311:
}
}
</syntaxhighlight>
{{out}}
Line 1,311 ⟶ 1,326:
Time taken: 228ms
</pre>
=={{header|Fortran}}==
See [[Closest pair problem/Fortran]]
=={{header|FreeBASIC}}==
'''Versión de fuerza bruta:
<
Dim As Integer i, j
Dim As Double minDist = 1^30
Line 1,350 ⟶ 1,363:
Print "El par más cercano es "; mini; " y "; minj; " a una distancia de "; Sqr(minDist)
End
</syntaxhighlight>
{{out}}
<pre>
El par más cercano es 2 y 5 a una distancia de 0.07791019135517516
</pre>
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
_elements = 9
local fn ClosetPairProblem
long i, j
double minDist = 1000000
double dist, minDisti, minDistj
double x(_elements), y(_elements)
x(0) = 0.654682 : y(0) = 0.925557
x(1) = 0.409382 : y(1) = 0.619391
x(2) = 0.891663 : y(2) = 0.888594
x(3) = 0.716629 : y(3) = 0.996200
x(4) = 0.477721 : y(4) = 0.946355
x(5) = 0.925092 : y(5) = 0.818220
x(6) = 0.624291 : y(6) = 0.142924
x(7) = 0.211332 : y(7) = 0.221507
x(8) = 0.293786 : y(8) = 0.691701
x(9) = 0.839186 : y(9) = 0.728260
for i = 0 to 8
for j = i + 1 to 9
dist = ( x(i) - x(j) )^2 + ( y(i) - y(j) )^2
if dist < minDist then minDist = dist : minDisti = i : minDistj = j
next
next
print "The closest pair is "; minDisti; " and "; minDistj; " at a distance of "; sqr(minDist)
end fn
fn ClosetPairProblem
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
The closest pair is 2 and 5 at a distance of 0.07791019135517516
</pre>
=={{header|Go}}==
'''Brute force'''
<
import (
Line 1,403 ⟶ 1,458:
}
return
}</
'''O(n)'''
<
// http://www.cs.umd.edu/~samir/grant/cp.pdf
package main
Line 1,520 ⟶ 1,575:
}
return p1, p2
}</
=={{header|Groovy}}==
Point class:
<
final Number x, y
Point(Number x = 0, Number y = 0) { this.x = x; this.y = y }
Number distance(Point that) { ((this.x - that.x)**2 + (this.y - that.y)**2)**0.5 }
String toString() { "{x:${x}, y:${y}}" }
}</
Brute force solution. Incorporates X-only and Y-only pre-checks in two places to cut down on the square root calculations:
<
assert pointCol
List l = pointCol
Line 1,554 ⟶ 1,608:
}
answer
}</
Elegant (divide-and-conquer reduction) solution. Incorporates X-only and Y-only pre-checks in two places (four if you count the inclusion of the brute force solution) to cut down on the square root calculations:
<
assert pointCol
List xList = (pointCol as List).sort { it.x }
Line 1,604 ⟶ 1,658:
}
answer
}</
Benchmark/Test:
<
(1..4).each {
Line 1,634 ⟶ 1,688:
=========================================
"""
}</
Results:
Line 1,691 ⟶ 1,745:
Speedup ratio (B/E): 26.3500255493
=========================================</pre>
=={{header|Haskell}}==
BF solution:
<
import System.Random (newStdGen, randomRs)
Line 1,717 ⟶ 1,770:
foldl1'' = foldl1'
</syntaxhighlight>
{{out}}
<
([[0.8347201880148426,0.40774840545089647],[0.8348731214261784,0.4087113189531284]],9.749825850154334e-4)
(4.02 secs, 488869056 bytes)</
=={{header|Icon}} and {{header|Unicon}}==
This is a brute force solution.
It combines reading the points with computing the closest pair seen so far.
<
procedure main()
Line 1,750 ⟶ 1,802:
procedure dSquared(p1,p2) # Compute the square of the distance
return (p2.x-p1.x)^2 + (p2.y-p1.y)^2 # (sufficient for closeness)
end</
=={{header|IS-BASIC}}==
<
110 NUMERIC X(1 TO 10),Y(1 TO 10)
120 FOR I=1 TO 10
Line 1,776 ⟶ 1,827:
310 DATA 0.211332,0.221507
320 DATA 0.293786,0.691701
330 DATA 0.839186,0.728260</
=={{header|J}}==
Solution of the simpler (brute-force) problem:
<
dist =: <@:vecl@:({: -"1 }:)\ NB. calculate all distances among vectors
minpair=: ({~ > {.@($ #: I.@,)@:= <./@;)dist NB. find one pair of the closest points
closestpairbf =: (; vecl@:-/)@minpair NB. the pair and their distance</
Examples of use:
<
0.654682 0.925557
0.409382 0.619391
Line 1,801 ⟶ 1,851:
|0.891663 0.888594|0.0779104|
|0.925092 0.81822| |
+-----------------+---------+</
The program also works for higher dimensional vectors:
<
0.559164 0.482993 0.876 0.429769
0.217911 0.729463 0.97227 0.132175
Line 1,819 ⟶ 1,869:
|0.217911 0.729463 0.97227 0.132175|0.708555|
|0.316673 0.797519 0.745821 0.0598321| |
+------------------------------------+--------+</
=={{header|Java}}==
Line 1,826 ⟶ 1,875:
'''Code:'''
<
public class ClosestPair
Line 2,011 ⟶ 2,060:
System.out.println("MISMATCH");
}
}</
{{out}}
Line 2,018 ⟶ 2,067:
Brute force (1594 ms): (0.9246533850872104, 0.098709007587097)-(0.924591196030625, 0.09862206991823985) : 1.0689077146927108E-4
Divide and conquer (250 ms): (0.924591196030625, 0.09862206991823985)-(0.9246533850872104, 0.098709007587097) : 1.0689077146927108E-4</pre>
=={{header|JavaScript}}==
Using bruteforce algorithm, the ''bruteforceClosestPair'' method below expects an array of objects with x- and y-members set to numbers, and returns an object containing the members ''distance'' and ''points''.
<
var dx = Math.abs(p1.x - p2.x);
var dy = Math.abs(p1.y - p2.y);
Line 2,048 ⟶ 2,096:
};
}
}</
divide-and-conquer method:
<
var Point = function(x, y) {
Line 2,191 ⟶ 2,239:
console.log(JSON.stringify(closestPair(Px, Py))); // {"distance":65.06919393998976,"pair":[{"x":37134,"y":1963},{"x":37181,"y":2008}]}
</syntaxhighlight>
=={{header|jq}}==
{{works with|jq|1.4}}
Line 2,199 ⟶ 2,246:
'''Infrastructure''':
<
# Emit the first input that satisfied the condition
def until(cond; next):
Line 2,208 ⟶ 2,255:
# Euclidean 2d distance
def dist(x;y):
[x[0] - y[0], x[1] - y[1]] | map(.*.) | add | sqrt;</
<syntaxhighlight lang="jq">
# P is an array of points, [x,y].
# Emit the solution in the form [dist, [P1, P2]]
Line 2,262 ⟶ 2,309:
| .[1]
end;
closestPair( sort_by(.[0]); sort_by(.[1])) ;</
'''Example from the Mathematica section''':
<
[[0.748501, 4.09624],
[3.00302, 5.26164],
Line 2,276 ⟶ 2,323:
[1.45428, 0.087596] ];
data | closest_pair</
{{Out}}
$jq -M -c -n -f closest_pair.jq
[0.0894096443343775,[[7.46489,4.6268],[7.46911,4.71611]]]
=={{header|Julia}}==
{{works with|Julia|0.6}}
Brute-force algorithm:
<
N = length(P)
if N < 2 return (Inf, ()) end
Line 2,299 ⟶ 2,345:
end
closestpair([[0, -0.3], [1., 1.], [1.5, 2], [2, 2], [3, 3]])</
=={{header|Kotlin}}==
<
typealias Point = Pair<Double, Double>
Line 2,380 ⟶ 2,425:
println("Closest pair (optimized) is ${pair2.first} and ${pair2.second}, distance $dist2\n")
}
}</
{{out}}
Line 2,390 ⟶ 2,435:
Closest pair (optimized) is (0.891663, 0.888594) and (0.925092, 0.81822), distance 0.07791019135517516
</pre>
=={{header|Liberty BASIC}}==
NB array terms can not be READ directly.
<syntaxhighlight lang="lb">
N =10
Line 2,436 ⟶ 2,480:
data 0.839186, 0.72826
</syntaxhighlight>
Distance =0.77910191e-1 between ( 0.891663, 0.888594) and ( 0.925092, 0.81822)
=={{header|Maple}}==
<
local
Line 2,509 ⟶ 2,552:
end proc; #Recurse
end module; #ClosestPair</
{{out}}<
> L := RandomTools:-Generate(list(list(float(range=0..1),2),512)):
> ClosestPair(L);
0.002576770304, [[0.4265584800, 0.7443097852], [0.4240649736, 0.7449595321]]
</syntaxhighlight>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
'''O(''n''<sup>2</sup>)'''
<syntaxhighlight lang="mathematica">nearestPair[data_] :=
Block[{pos, dist = N[Outer[EuclideanDistance, data, data, 1]]},
pos = Position[dist, Min[DeleteCases[Flatten[dist], 0.]]];
data[[pos[[1]]]]]</
'''O(''n''<sup>2</sup>) output:'''
<
9.52232}, {7.46911, 4.71611}, {5.7819, 2.69367}, {2.34709,
8.74782}, {2.87169, 5.97774}, {6.33101, 0.463131}, {7.46489,
4.6268}, {1.45428, 0.087596}}]
{{7.46911, 4.71611}, {7.46489, 4.6268}}</
''' O(''n''log ''n'') '''
<syntaxhighlight lang="mathematica">closestPair[ptsIn_] :=
Module[{xP, yP,
pts},(*Top level function.Sorts the pts by x and by y and then \
calls closestPairR[]*)pts = N[ptsIn];
xP = Sort[pts, #1[[1]] < #2[[1]] &];
yP = Sort[pts, #1[[2]] < #2[[2]] &];
closestPairR[xP, yP]]
closestPairR[xP_, yP_] :=
Module[{n, mid, xL, xR, xm, yL, yR, dL, pairL, dmin, pairMin, yS, nS,
closest, closestP, k,
cDist},(*where xP is P(1).. P(n) sorted by x coordinate,
and yP is P(1).. P(n) sorted by y coordinate (ascending order)*)
n = Length[xP];
If[n <= 3,(*Brute Force*)
Piecewise[{{{\[Infinity], {}},
n < 2}, {{EuclideanDistance[xP[[1]], xP[[2]]], {xP[[1]],
xP[[2]]}},
n == 2}, {Last@
MinimalBy[{{EuclideanDistance[xP[[1]], xP[[2]]], {xP[[1]],
xP[[2]]}}, {EuclideanDistance[xP[[1]], xP[[3]]], {xP[[1]],
xP[[3]]}}, {EuclideanDistance[xP[[3]], xP[[2]]], {xP[[3]],
xP[[2]]}}}, First], n == 3}}], mid = Ceiling[n/2];
xL = xP[[1 ;; mid]];
xR = xP[[mid + 1 ;; n]];
xm = xP[[mid]];
yL = Select[yP, #[[1]] <= xm[[1]] &];
yR = Select[yP, #[[1]] > xm[[1]] &];
{dL, pairL} = closestPairR[xL, yL];
{dmin, pairMin} = closestPairR[xR, yR];
If[dL < dmin, {dmin, pairMin} = {dL, pairL}];
yS = Select[yP, Abs[#[[1]] - xm[[1]]] <= dmin &];
nS = Length[yS];
{closest, closestP} = {dmin, pairMin};
Table[k = i + 1;
While[(k <= nS) && (yS[[k, 2]] - yS[[i, 2]] < dmin),
cDist = EuclideanDistance[yS[[k]], yS[[i]]];
If[cDist <
closest, {closest, closestP} = {cDist, {yS[[k]], yS[[i]]}}];
k = k + 1], {i, 1, nS - 1}];
{closest, closestP}](*end if*)]
</syntaxhighlight>
''' O(''n''log''n'') output: '''
<syntaxhighlight lang="mathematica">closestPair[{{0.748501, 4.09624}, {3.00302, 5.26164}, {3.61878,
9.52232}, {7.46911, 4.71611}, {5.7819, 2.69367}, {2.34709,
8.74782}, {2.87169, 5.97774}, {6.33101, 0.463131}, {7.46489,
4.6268}, {1.45428, 0.087596}}]
{0.0894096, {{7.46489, 4.6268}, {7.46911, 4.71611}}}</syntaxhighlight>
=={{header|MATLAB}}==
This solution is an almost direct translation of the above pseudo-code into MATLAB.
<
N = numel(xP);
Line 2,604 ⟶ 2,700:
end %for
end %if (N <= 3)
end %closestPair</
{{out}}
<
distance =
Line 2,616 ⟶ 2,712:
pair =
[1x2 double] [1x2 double] %The pair is [1.5 2] and [2 2] which is correct</
=={{header|Microsoft Small Basic}}==
<
s="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,"
i=0
Line 2,663 ⟶ 2,758:
TextWindow.WriteLine("is between the points:")
TextWindow.WriteLine(" ["+pxy[ii][1]+","+pxy[ii][2]+"] and")
TextWindow.WriteLine(" ["+pxy[jj][1]+","+pxy[jj][2]+"]")</
{{out}}
<pre>
Line 2,671 ⟶ 2,766:
[0.925092,0.818220]
</pre>
=={{header|Nim}}==
<syntaxhighlight lang="nim">import math, algorithm
type
Point = tuple[x, y: float]
Pair = tuple[p1, p2: Point]
Result = tuple[minDist: float; minPoints: Pair]
#---------------------------------------------------------------------------------------------------
template sqr(x: float): float = x * x
#---------------------------------------------------------------------------------------------------
func dist(point1, point2: Point): float =
sqrt(sqr(point2.x - point1.x) + sqr(point2.y - point1.y))
#---------------------------------------------------------------------------------------------------
func bruteForceClosestPair*(points: openArray[Point]): Result =
doAssert(points.len >= 2, "At least two points required.")
result.minDist = Inf
for i in 0..<points.high:
for j in (i + 1)..points.high:
let d = dist(points[i], points[j])
if d < result.minDist:
result = (d, (points[i], points[j]))
#---------------------------------------------------------------------------------------------------
func closestPair(xP, yP: openArray[Point]): Result =
## Recursive function which takes two open arrays as arguments: the first
## sorted by increasing values of x, the second sorted by increasing values of y.
if xP.len <= 3:
return xP.bruteForceClosestPair()
let m = xP.high div 2
let xL = xP[0..m]
let xR = xP[(m + 1)..^1]
let xm = xP[m].x
var yL, yR: seq[Point]
for p in yP:
if p.x <= xm: yL.add(p)
else: yR.add(p)
let (dL, pairL) = closestPair(xL, yL)
let (dR, pairR) = closestPair(xR, yR)
let (dMin, pairMin) = if dL < dR: (dL, pairL) else: (dR, pairR)
var yS: seq[Point]
for p in yP:
if abs(xm - p.x) < dmin: yS.add(p)
result = (dMin, pairMin)
for i in 0..<yS.high:
var k = i + 1
while k < yS.len and ys[k].y - yS[i].y < dMin:
let d = dist(yS[i], yS[k])
if d < result.minDist:
result = (d, (yS[i], yS[k]))
inc k
#---------------------------------------------------------------------------------------------------
func closestPair*(points: openArray[Point]): Result =
let xP = points.sortedByIt(it.x)
let yP = points.sortedByIt(it.y)
doAssert(points.len >= 2, "At least two points required.")
result = closestPair(xP, yP)
#———————————————————————————————————————————————————————————————————————————————————————————————————
import random, times, strformat
randomize()
const N = 50_000
const Max = 10_000.0
var points: array[N, Point]
for pt in points.mitems: pt = (rand(Max), rand(Max))
echo "Sample contains ", N, " random points."
echo ""
let t0 = getTime()
echo "Brute force algorithm:"
echo points.bruteForceClosestPair()
let t1 = getTime()
echo "Optimized algorithm:"
echo points.closestPair()
let t2 = getTime()
echo ""
echo fmt"Execution time for brute force algorithm: {(t1 - t0).inMilliseconds:>4} ms"
echo fmt"Execution time for optimized algorithm: {(t2 - t1).inMilliseconds:>4} ms"</syntaxhighlight>
{{out}}
<pre>Sample contains 50000 random points.
Brute force algorithm:
(minDist: 0.1177082437919083, minPoints: (p1: (x: 3686.601318778875, y: 2187.261792916939), p2: (x: 3686.483703931143, y: 2187.257104820359)))
Optimized algorithm:
(minDist: 0.1177082437919083, minPoints: (p1: (x: 3686.483703931143, y: 2187.257104820359), p2: (x: 3686.601318778875, y: 2187.261792916939)))
Execution time for brute force algorithm: 2656 ms
Execution time for optimized algorithm: 63 ms</pre>
=={{header|Objective-C}}==
See [[Closest-pair problem/Objective-C]]
=={{header|OCaml}}==
<
type point = { x : float; y : float }
Line 2,802 ⟶ 3,008:
Printf.printf "(%f, %f) (%f, %f) Dist %f\n" a.x a.y b.x b.y (dist c)
</syntaxhighlight>
=={{header|Oz}}==
Translation of pseudocode:
<
fun {Distance X1#Y1 X2#Y2}
{Sqrt {Pow X2-X1 2.0} + {Pow Y2-Y1 2.0}}
Line 2,904 ⟶ 3,109:
{ForAll Points RandomPoint}
{Show Points}
{Show {ClosestPair Points}}</
=={{header|PARI/GP}}==
Naive quadratic solution.
<
my(r=norml2(v[1]-v[2]),at=[1,2]);
for(a=1,#v-1,
Line 2,919 ⟶ 3,123:
);
[v[at[1]],v[at[2]]]
};</
=={{header|Pascal}}==
Brute force only calc square of distance, like AWK etc...
As fast as [[Closest-pair_problem#Faster_Brute-force_Version | D ]] .
<
{$IFDEF FPC}
{$MODE Delphi}
Line 2,990 ⟶ 3,193:
Writeln('P[',i:4,']= x: ',PointLst[i].ptX:0:8,
' y: ',PointLst[i].ptY:0:8);
end.</
//without randomize always same results
//32-Bit
Line 3,006 ⟶ 3,209:
//32-Bit
PointCnt = { 10000*sqrt(10) } 31623;-> real 0m1.112s 10x times runtime</pre>
=={{header|PascalABC.NET}}==
Brute forse algorithm.
<syntaxhighlight lang="delphi">
type Point = auto class
x,y: real;
function Distance(p: Point): real := Sqrt((x-p.x)**2 + (y-p.y)**2);
end;
function Pnt(x,y: real) := new Point(x,y);
function RandomPoint: Point := Pnt(RandomReal(0,10),RandomReal(0,10));
function ClosestPair(points: array of Point): (Point,Point);
begin
var pairs := points.Combinations(2);
var pair := pairs.MinBy(pair -> pair[0].Distance(pair[1]));
Result := (pair[0],pair[1]);
end;
begin
var points := ArrGen(10,i -> RandomPoint);
points.Println;
var ClPair := ClosestPair(points);
Println(ClPair,ClPair[0].Distance(ClPair[1]));
end.
</syntaxhighlight>
{{out}}
<pre>
(3.37,1.75) (3.87,9.48) (6.21,7.71) (7.52,7.95) (6.94,2.07) (1.72,5.92) (6.04,0.66) (3.46,0.93) (6.09,1.97) (4.95,0.19)
((3.37,1.75),(3.46,0.93)) 0.824924238945614
</pre>
=={{header|Perl}}==
The divide & conquer technique is about 100x faster than the brute-force algorithm.
<syntaxhighlight lang
use
use POSIX qw(ceil);
sub dist {
my ($a, $b) = @_;
return
}
sub closest_pair_simple {
my @points = @{ shift @_ };
my ($a, $b, $d) = ( $points[0], $points[1], dist($points[0], $points[1]) );
my $
($a, $b, $d) = ($p, $l, $t) if $t < $d;
}
}
sub closest_pair {
my @r = @{ shift @_ };
closest_pair_real( [sort { $a->[0] <=> $b->[0] } @r], [sort { $a->[1] <=> $b->[1] } @r] )
}
sub closest_pair_real {
my ($rx, $ry) = @_;
my(@yR,
my $N = @$rx;
my $midx = ceil($N/2)-1;
my @PL = @$rx[ 0 .. $midx];
my @
my
$_->[0] <= $xm ? push @yR, $_ : push @yL, $_ for @$ry;
my ($al, $bl, $dL) = closest_pair_real(\@PL, \@yR);
my ($ar, $br, $dR) = closest_pair_real(\@PR, \@yL);
my ($w1, $w2, $closest) = $dR > $dL ? ($al, $bl, $dL) : ($ar, $br, $dR);
abs($xm - $_->[0]) < $closest and push @yS, $_ for @$ry;
for my
while ( $k <= $#yS and ($yS[$k]->[1] - $yS[$i]->[1]) < $closest ) {
my
($w1, $w2, $closest) = ($yS[$k], $yS[$i], $d) if $d < $closest;
}
}
$w1, $w2, $closest
}
my @points;
push @points, [rand(20)-10, rand(20)-10] for 1..5000;
printf "%.8f between (%.5f, %.5f), (%.5f, %.5f)\n", $_->[2], @{$$_[0]}, @{$$_[1]}
for [closest_pair_simple(\@points)], [closest_pair(\@points)];</syntaxhighlight>
{{out}}
<pre>0.00259322 between (-1.95541, -4.29695), (-1.95351, -4.29871)
0.00259322 between (-1.95541, -4.29695), (-1.95351, -4.29871)</pre>
=={{header|Phix}}==
Brute force and divide and conquer (translated from pseudocode) approaches compared
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">bruteForceClosestPair</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">dy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">mind</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dx</span><span style="color: #0000FF;">+</span><span style="color: #000000;">dy</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dy</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">minp</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">x2</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dx</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;"><</span><span style="color: #000000;">mind</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">dy</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">-</span><span style="color: #000000;">y2</span>
<span style="color: #000000;">dx</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">dy</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dy</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">dx</span><span style="color: #0000FF;"><</span><span style="color: #000000;">mind</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">mind</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">dx</span>
<span style="color: #000000;">minp</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">mind</span><span style="color: #0000FF;">),</span><span style="color: #000000;">minp</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">testset</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sq_rnd</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">({</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">},</span><span style="color: #000000;">10000</span><span style="color: #0000FF;">))</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">points</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">bruteForceClosestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testset</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (Sorting the final point pair makes brute/dc more likely to tally. Note however
-- when >1 equidistant pairs exist, brute and dc may well return different pairs;
-- it is only a problem if they decide to return different minimum distances.)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">points</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Closest pair: {%f,%f} {%f,%f}, distance=%f (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">X</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">Y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">2</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">xP</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testset</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">byY</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p2</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p1</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">],</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">[</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">yP</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">custom_sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">routine_id</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"byY"</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">testset</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">distsq</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p1</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p2</span>
<span style="color: #000000;">x1</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">x2</span>
<span style="color: #000000;">y1</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">y2</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">x1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">x1</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">y1</span><span style="color: #0000FF;">*</span><span style="color: #000000;">y1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yP</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- where xP is P(1) .. P(N) sorted by x coordinate, and
-- yP is P(1) .. P(N) sorted by y coordinate (ascending order)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">N</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xP</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">midN</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">N</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">assert</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">N</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">N</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">3</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">bruteForceClosestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xP</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">xL</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">midN</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">xR</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">midN</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">N</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">yL</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{},</span>
<span style="color: #000000;">yR</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">xm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">xP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">midN</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">N</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">]<=</span><span style="color: #000000;">xm</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">yL</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yL</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">yR</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yR</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">dL</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pairL</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yL</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">dR</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pairR</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xR</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">yR</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">dmin</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pairMin</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">min</span><span style="color: #0000FF;">({</span><span style="color: #000000;">dL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pairL</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">dR</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pairR</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">yS</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xm</span><span style="color: #0000FF;">-</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">X</span><span style="color: #0000FF;">])<</span><span style="color: #000000;">dmin</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">yS</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nS</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{</span><span style="color: #004080;">atom</span> <span style="color: #000000;">closest</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">cPair</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">dmin</span><span style="color: #0000FF;">*</span><span style="color: #000000;">dmin</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pairMin</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nS</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">k</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">nS</span> <span style="color: #008080;">and</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">]-</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">Y</span><span style="color: #0000FF;">])<</span><span style="color: #000000;">dmin</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">distsq</span><span style="color: #0000FF;">(</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;"><</span><span style="color: #000000;">closest</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">closest</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cPair</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">yS</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]}}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">closest</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">cPair</span><span style="color: #0000FF;">}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">points</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">closestPair</span><span style="color: #0000FF;">(</span><span style="color: #000000;">xP</span><span style="color: #0000FF;">,</span><span style="color: #000000;">yP</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">{{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y1</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">}}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">points</span><span style="color: #0000FF;">))</span> <span style="color: #000080;font-style:italic;">-- (see note above)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Closest pair: {%f,%f} {%f,%f}, distance=%f (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">x1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">y2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 3,228 ⟶ 3,418:
Closest pair: {0.0328051,0.0966250} {0.0328850,0.0966250}, distance=0.000120143 (0.14s)
</pre>
=={{header|PicoLisp}}==
<
(let Min T
(use (Pt1 Pt2)
Line 3,243 ⟶ 3,432:
Min )
(setq Min N Pt1 P Pt2 Q) ) ) )
(list Pt1 Pt2 (sqrt Min)) ) ) )</
Test:
<pre>: (scl 6)
Line 3,261 ⟶ 3,450:
(0.839186 . 0.728260) ) )
-> ((891663 . 888594) (925092 . 818220) 77910)</pre>
=={{header|PL/I}}==
<syntaxhighlight lang="text">
/* Closest Pair Problem */
closest: procedure options (main);
Line 3,296 ⟶ 3,484:
end;
end closest;
</syntaxhighlight>
=={{header|Prolog}}==
'''Brute force version, works with SWI-Prolog, tested on version 7.2.3.
<syntaxhighlight lang="prolog">
% main predicate, find and print closest point
do_find_closest_points(Points) :-
Line 3,331 ⟶ 3,518:
closest(points(P1,P2,Dist), points(_,_,Dist2), points(P1,P2,Dist)) :-
Dist =< Dist2.
</syntaxhighlight>
To test, pass in a list of points.
<
point(0.654682, 0.925557),
point(0.409382, 0.619391),
Line 3,345 ⟶ 3,532:
point(0.839186, 0.728260)
]).
</syntaxhighlight>
{{out}}
<pre>
Line 3,354 ⟶ 3,541:
false.
</pre>
=={{header|PureBasic}}==
'''Brute force version
<
Protected N=ArraySize(P()), i, j
Protected mindistance.f=Infinity(), t.d
Line 3,376 ⟶ 3,562:
ProcedureReturn mindistance
EndProcedure
</syntaxhighlight>
Implementation can be as
<
x.d
y.d
Line 3,407 ⟶ 3,593:
Data.d 0.716629, 0.996200, 0.477721, 0.946355, 0.925092, 0.818220
Data.d 0.624291, 0.142924, 0.211332, 0.221507, 0.293786, 0.691701, 0.839186, 0.72826
EndDataSection</
{{out}}
<pre>Mindistance= 0.077910
Line 3,414 ⟶ 3,600:
Press ENTER to quit</pre>
=={{header|Python}}==
<
Compute nearest pair of points using two algorithms
Line 3,502 ⟶ 3,687:
times()
times()
times()</
{{out}} followed by timing comparisons<br>
Line 3,558 ⟶ 3,743:
Time for closestPair 0.119326618327
>>> </pre></div>
=={{header|R}}==
{{works with|R|2.8.1+}}
Brute force solution as per wikipedia pseudo-code
<
xy = cbind(x,y)
cp = bruteforce(xy)
Line 3,591 ⟶ 3,775:
else bruteforce(pmatrix,n+1,pd)
}
}</
Quicker brute force solution for R that makes use of the apply function native to R for dealing with matrices. It expects x and y to take the form of separate vectors.
<
{
distancev <- function(pointsv)
Line 3,613 ⟶ 3,797:
"\n\tDistance: ",minrow[3],"\n",sep="")
c(distance=minrow[3],x1.x=x[minrow[1]],y1.y=y[minrow[1]],x2.x=x[minrow[2]],y2.y=y[minrow[2]])
}</
This is the quickest version, that makes use of the 'dist' function of R. It takes a two-column object of x,y-values as input, or creates such an object from seperate x and y-vectors.
<
# takes two-column object(x,y-values), or creates such an object from x and y values
if(!is.null(y)) x <- cbind(x, y)
Line 3,635 ⟶ 3,819:
x2=x[point.pair[2],1],y2=x[point.pair[2],2],
distance=min.dist)
}</
Example<
y = (sample(-1000.00:1000.00,length(x)))
cp = closest.pairs(x,y)
Line 3,674 ⟶ 3,858:
0.17 0.00 0.19
</syntaxhighlight>
Using dist function for brute force, but divide and conquer (as per pseudocode) for speed:
<
{
if (!is.null(y))
Line 3,765 ⟶ 3,949:
print(closest.pairs.bruteforce(x,y))
cat(sprintf("That took %.2f seconds.\n",proc.time()[3] - tstart))
</syntaxhighlight>
{{out}}
<pre>
Line 3,799 ⟶ 3,983:
That took 6.38 seconds.
</pre>
=={{header|Racket}}==
The brute force solution using complex numbers
to represent pairs.
<
#lang racket
(define (dist z0 z1) (magnitude (- z1 z0)))
Line 3,819 ⟶ 4,002:
(displayln (~a "Closest points: " result))
(displayln (~a "Distance: " (dist* result)))
</syntaxhighlight>
The divide and conquer algorithm using a struct to represent points
<
#lang racket
(struct point (x y) #:transparent)
Line 3,920 ⟶ 4,103:
(match-define (list (point p1x p1y) (point p2x p2y)) (closest-pair points))
(printf "Closest points on a quadratic curve (~a,~a) (~a,~a)\n" p1x p1y p2x p2y)
</syntaxhighlight>
{{out}}
<
Closest points: (0+1i 1+2i)
Distance: 1.4142135623730951
Closest points on a quadratic curve (0,0) (1,1)
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
Line 3,935 ⟶ 4,117:
{{trans|Perl 5}}
Using concurrency, the 'simple' routine beats the (supposedly) more efficient one for all but the smallest sets of input.
<syntaxhighlight lang="raku" line>sub MAIN ($N = 5000) {
my @points = (^$N).map: { [rand × 20 - 10, rand × 20 - 10] }
my @candidates = @points.sort(*.[0]).rotor( 10 => -2, :partial).race.map: { closest-pair-simple(@$_) }
say
@candidates = @points.sort(*.[0]).rotor( 10 => -2, :partial).race.map: { closest-pair(@$_) }
say 'real ' ~ (@candidates.sort: *.[2]).head(1).gist;
}
sub dist-squared(
sub
return
my ($a, $b, $d) =
while
my
for @
}
}
}
sub
}
sub closest-pair-real(@rx, @ry) {
my \N = @rx;
my
my @PL := @rx[ 0 .. midx];
my @
my
(.[0] ≤ xm ?? my @yR !! my @yL).push: @$_ for @ry;
my (\al, \bl, \dL) = closest-pair-real(@PL, @yR);
my (\ar, \br, \dR) = closest-pair-real(@PR, @yL);
my ($w1, $w2, $closest) = dR < dL ?? (ar, br, dR) !! (al, bl, dL);
my @yS = @ry.grep: { (xm - .[0]).abs < $closest }
for 0 ..^ @yS -> \i {
for i+1 ..^ @yS -> \k {
next unless @yS[k;1] - @yS[i;1] < $closest;
($w1, $w2, $closest) = |@yS[k, i], $_ if $_ < $closest given dist-squared(|@yS[k, i]).sqrt;
}
}
$w1, $w2, $closest
}</syntaxhighlight>
{{out}}
<pre>simple (([-1.1560800527301716 -9.214015073077793] [-1.1570263876019649 -9.213340680530798] 0.0011620477602117762))
real (([-1.1570263876019649 -9.213340680530798] [-1.1560800527301716 -9.214015073077793] 0.0011620477602117762))</pre>
=={{header|REXX}}==
Programming note: this REXX version allows two (or more) points to be identical, and will
<br>manifest itself as a minimum distance of zero (the variable <big> <tt> '''dd''' </tt> </big> on line 17).
<
parse arg N
if
if
if
if datatype(seed, 'W') then call random ,,seed /*seed for RANDOM (BIF) repeatability.*/
w= length(
/*╔══════════════════════╗*/ do j=1 for N /*generate N random points*/
/*║ generate N points. ║*/ @x.j= random(
/*╚══════════════════════╝*/ @y.j= random(
end /*j*/ /*X & Y make the point.*/
/* [↓] use of XJ & YJ speed things up.*/
do j=1 for N-1;
do k=j+1
if
end /*k*/ /* [↑] needn't take SQRT of
end /*j*/ /* [↑] when done, A & B are the points*/
$= 'For ' N " points, the minimum distance between the two points: "
say $ center("x", w, '═')" "
say left('', length($) - 1)
say left('', length($) - 1)
exit
/*──────────────────────────────────────────────────────────────────────────────────────*/
sqrt: procedure; parse arg x; if x=0 then return 0; d=digits(); m.=9; numeric form; h=d+6
numeric digits; parse value format(x,2,1,,0) 'E0' with g 'E' _ .; g= g *.5'e'_ % 2
do j=0 while h>9; m.j= h; h= h % 2 + 1; end /*j*/
do k=j+5 to 0 by -1; numeric digits m.k; g= (g+x/g)*.5; end /*k*/; return g</
{{out|output|text= when using the default input of: <tt> 100 </tt>}}
<pre>
For 100 points, the minimum distance between the two points: ══x══ ══y══ is: 219.228192
Line 4,054 ⟶ 4,210:
[ 7483, 1700]
</pre>
{{out|output|text= when using the input of: <tt> 200 </tt>}}
<pre>
For 200 points, the minimum distance between the two points: ══x══ ══y══ is: 39.408121
Line 4,060 ⟶ 4,216:
[17627, 19198]
</pre>
{{out|output|text= when using the input of: <tt> 1000 </tt>
}}
<pre>
Line 4,067 ⟶ 4,223:
[ 6263, 19108]
</pre>
=={{header|Ring}}==
<
decimals(10)
x = list(10)
Line 4,102 ⟶ 4,257:
next
see "closest pair is : " + mini + " and " + minj + " at distance " + sqrt(min)
</syntaxhighlight>
Output:
<pre>
closest pair is : 3 and 6 at distance 0.0779101914
</pre>
=={{header|RPL}}==
Brute-force approach, because it's unlikely that anyone would use a RPL calculator to process a large set of points.
« → points
« 0 0 0
1 points SIZE 1 - '''FOR''' j
j 1 + points SIZE '''FOR''' k
points j GET points k GET - ABS
'''IF''' DUP2 < '''THEN''' 4 ROLLD 3 DROPN j k ROT '''ELSE''' DROP '''END'''
'''NEXT NEXT''' ROT ROT
points SWAP GET points ROT GET
'''IF''' DUP2 RE SWAP RE < '''THEN''' SWAP '''END''' <span style="color:grey">@ sort by ascending x</span>
2 →LIST
» » '<span style="color:blue">CLOSEPR</span>' STO
{ (0,0) (1,0) (1,2) (3,4) (5,5) (7,5) (3,5) } <span style="color:blue">CLOSEPR</span>
{{out}}
<pre>
2: 8.60232526704
1: { (0,0) (7,5) }
</pre>
=={{header|Ruby}}==
<
def distance(p1, p2)
Line 4,161 ⟶ 4,336:
x.report("bruteforce") {ans1 = closest_bruteforce(points)}
x.report("recursive") {ans2 = closest_recursive(points)}
end</
'''Sample output'''
<pre>
Line 4,173 ⟶ 4,348:
=={{header|Run BASIC}}==
Courtesy http://dkokenge.com/rbp
<
dim x(n)
dim y(n)
Line 4,213 ⟶ 4,388:
data 0.211332, 0.221507
data 0.293786, 0.691701
data 0.839186, 0.72826</
=={{header|Rust}}==
<syntaxhighlight lang="rust">
//! We interpret complex numbers as points in the Cartesian plane, here. We also use the
//! [sweepline/plane sweep closest pairs algorithm][algorithm] instead of the divide-and-conquer
//! algorithm, since it's (arguably) easier to implement, and an efficient implementation does not
//! require use of unsafe.
//!
//! [algorithm]: http://www.cs.mcgill.ca/~cs251/ClosestPair/ClosestPairPS.html
extern crate num;
use num::complex::Complex;
use std::cmp::{Ordering, PartialOrd};
use std::collections::BTreeSet;
type Point = Complex<f32>;
/// Wrapper around `Point` (i.e. `Complex<f32>`) so that we can use a `TreeSet`
#[derive(PartialEq)]
struct YSortedPoint {
point: Point,
}
impl PartialOrd for YSortedPoint {
fn partial_cmp(&self, other: &YSortedPoint) -> Option<Ordering> {
(self.point.im, self.point.re).partial_cmp(&(other.point.im, other.point.re))
}
}
impl Ord for YSortedPoint {
fn cmp(&self, other: &YSortedPoint) -> Ordering {
self.partial_cmp(other).unwrap()
}
}
impl Eq for YSortedPoint {}
fn closest_pair(points: &mut [Point]) -> Option<(Point, Point)> {
if points.len() < 2 {
return None;
}
points.sort_by(|a, b| (a.re, a.im).partial_cmp(&(b.re, b.im)).unwrap());
let mut closest_pair = (points[0], points[1]);
let mut closest_distance_sqr = (points[0] - points[1]).norm_sqr();
let mut closest_distance = closest_distance_sqr.sqrt();
// the strip that we inspect for closest pairs as we sweep right
let mut strip: BTreeSet<YSortedPoint> = BTreeSet::new();
strip.insert(YSortedPoint { point: points[0] });
strip.insert(YSortedPoint { point: points[1] });
// index of the leftmost point on the strip (on points)
let mut leftmost_idx = 0;
// Start the sweep!
for (idx, point) in points.iter().enumerate().skip(2) {
// Remove all points farther than `closest_distance` away from `point`
// along the x-axis
while leftmost_idx < idx {
let leftmost_point = &points[leftmost_idx];
if (leftmost_point.re - point.re).powi(2) < closest_distance_sqr {
break;
}
strip.remove(&YSortedPoint {
point: *leftmost_point,
});
leftmost_idx += 1;
}
// Compare to points in bounding box
{
let low_bound = YSortedPoint {
point: Point {
re: ::std::f32::INFINITY,
im: point.im - closest_distance,
},
};
let mut strip_iter = strip.iter().skip_while(|&p| p < &low_bound);
loop {
let point2 = match strip_iter.next() {
None => break,
Some(p) => p.point,
};
if point2.im - point.im >= closest_distance {
// we've reached the end of the box
break;
}
let dist_sqr = (*point - point2).norm_sqr();
if dist_sqr < closest_distance_sqr {
closest_pair = (point2, *point);
closest_distance_sqr = dist_sqr;
closest_distance = dist_sqr.sqrt();
}
}
}
// Insert point into strip
strip.insert(YSortedPoint { point: *point });
}
Some(closest_pair)
}
pub fn main() {
let mut test_data = [
Complex::new(0.654682, 0.925557),
Complex::new(0.409382, 0.619391),
Complex::new(0.891663, 0.888594),
Complex::new(0.716629, 0.996200),
Complex::new(0.477721, 0.946355),
Complex::new(0.925092, 0.818220),
Complex::new(0.624291, 0.142924),
Complex::new(0.211332, 0.221507),
Complex::new(0.293786, 0.691701),
Complex::new(0.839186, 0.728260),
];
let (p1, p2) = closest_pair(&mut test_data[..]).unwrap();
println!("Closest pair: {} and {}", p1, p2);
println!("Distance: {}", (p1 - p2).norm_sqr().sqrt());
}
</syntaxhighlight>
{{out}}
<pre>
Closest pair: 0.891663+0.888594i and 0.925092+0.81822i
Distance: 0.07791013
</pre>
=={{header|Scala}}==
<
import scala.util.Random
Line 4,349 ⟶ 4,649:
}
}
</syntaxhighlight>
{{out}}
Line 4,357 ⟶ 4,657:
Divide and conquer (52 ms): (0.4198255166110827, 0.45044969701435)-(0.41984960343173994, 0.4499078600557793) : 5.423720721077961E-4
</pre>
=={{header|Seed7}}==
This is the brute force algorithm:
<
var float: x is 0.0;
var float: y is 0.0;
Line 4,393 ⟶ 4,692:
result := [] (points[savei], points[savej]);
end if;
end func;</
=={{header|Sidef}}==
{{trans|Raku}}
<
sqr(a[0] - b[0]) + sqr(a[1] - b[1])
}
Line 4,467 ⟶ 4,765:
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(' ')})"</
=={{header|Smalltalk}}==
See [[Closest-pair problem/Smalltalk]]
=={{header|Swift}}==
<
struct Point {
Line 4,573 ⟶ 4,869:
}
print(points.closestPair()!)</
{{out}}
<pre>(Point(x: 5.279430517795172, y: 8.85108182685002), Point(x: 5.278427575530877, y: 8.851990433099456))</pre>
=={{header|Tcl}}==
Each point is represented as a list of two floating-point numbers, the first being the ''x'' coordinate, and the second being the ''y''.
<
# retrieve the x-coordinate
Line 4,670 ⟶ 4,965:
set time [time {set ::dist($method) [closest_$method $points]} 1]
puts [format "%-10s %9d %9d %s" $method $::comparisons [lindex $time 0] [lindex $::dist($method) 0]]
}</
{{out}}
<pre>method compares time closest
Line 4,676 ⟶ 4,971:
recursive 14613 488094 0.0015652738546658382</pre>
Note that the <code>lindex</code> and <code>llength</code> commands are both O(1).
=={{header|Ursala}}==
The brute force algorithm is easy.
Line 4,686 ⟶ 4,980:
each remaining pair the sum of the squares of the differences
between corresponding coordinates.
<
clop = @iiK0 fleq$-&l+ *EZF ^\~& plus+ sqr~~+ minus~~bbI</
The divide and conquer algorithm following the specification
given above is a little more hairy but not much longer.
The <code>eudist</code> library function
is used to compute the distance between points.
<
#import flo
Line 4,700 ⟶ 4,994:
^(fleq-<&l,fleq-<&r); @blrNCCS ~&lrbhthPX2X+ ~&a^& fleq$-&l+ leql/8?al\^(eudist,~&)*altK33htDSL -+
^C/~&rr ^(eudist,~&)*tK33htDSL+ @rlrlPXPlX ~| fleq^\~&lr abs+ minus@llPrhPX,
^/~&ar @farlK30K31XPGbrlrjX3J ^/~&arlhh @W lesser fleq@bl+-</
test program:
<
<
Line 4,724 ⟶ 5,018:
#cast %eeWWA
example = clop test_data</
{{out}}
The output shows the minimum distance and the two points separated
Line 4,734 ⟶ 5,028:
(-1.745694e+00,3.276434e+00))
</pre>
=={{header|VBA}}==
<
Private Type MyPoint
Line 4,789 ⟶ 5,082:
Dist = Sqr((p1.X - p2.X) ^ 2 + (p1.Y - p2.Y) ^ 2)
End Function
</syntaxhighlight>
{{out}}
<pre>For 10 points, runtime : 0 sec.
Line 4,811 ⟶ 5,104:
dist : 2,445694
--------------------------------------------------</pre>
=={{header|Visual FoxPro}}==
<
CLOSE DATABASES ALL
CREATE CURSOR pairs(id I, xcoord B(6), ycoord B(6))
Line 4,834 ⟶ 5,126:
? "Closest pair is " + TRANSFORM(id1) + " and " + TRANSFORM(id2) + "."
? "Distance is " + TRANSFORM(SQRT(dist2))
</syntaxhighlight>
{{out}}
<pre>
Line 4,841 ⟶ 5,133:
Closest pair is 3 and 6.
Distance is 0.077910.
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-math}}
{{libheader|Wren-sort}}
<syntaxhighlight lang="wren">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")
}</syntaxhighlight>
{{out}}
<pre>
Closest pair (brute force) is [8, 4] and [7, 4], distance 1
Closest pair (optimized) is [7, 4] and [8, 4], distance 1
Closest pair (brute force) is [0.891663, 0.888594] and [0.925092, 0.81822], distance 0.077910191355175
Closest pair (optimized) is [0.891663, 0.888594] and [0.925092, 0.81822], distance 0.077910191355175
</pre>
Line 4,847 ⟶ 5,237:
and is perfectly adequate, even for a thousand points.
<
proc ClosestPair(P, N); \Show closest pair of points in array P
Line 4,883 ⟶ 5,273:
[0.839186, 0.728260]]; \9
ClosestPair(Data, 10);
]</
{{out}}
Line 4,890 ⟶ 5,280:
0.891663,0.888594 -- 0.925092,0.818220
</pre>
=={{header|Yabasic}}==
'''Versión de fuerza bruta:
<syntaxhighlight lang="yabasic">
minDist = 1^30
dim x(9), y(9)
x(0) = 0.654682 : y(0) = 0.925557
x(1) = 0.409382 : y(1) = 0.619391
x(2) = 0.891663 : y(2) = 0.888594
x(3) = 0.716629 : y(3) = 0.996200
x(4) = 0.477721 : y(4) = 0.946355
x(5) = 0.925092 : y(5) = 0.818220
x(6) = 0.624291 : y(6) = 0.142924
x(7) = 0.211332 : y(7) = 0.221507
x(8) = 0.293786 : y(8) = 0.691701
x(9) = 0.839186 : y(9) = 0.728260
for i = 0 to 8
for j = i+1 to 9
dist = (x(i) - x(j))^2 + (y(i) - y(j))^2
if dist < minDist then
minDist = dist
mini = i
minj = j
end if
next j
next i
print "El par mas cercano es ", mini, " y ", minj, " a una distancia de ", sqr(minDist)
end
</syntaxhighlight>
{{out}}
<pre>
El par mas cercano es 2 y 5 a una distancia de 3.68449e-05
</pre>
=={{header|zkl}}==
An ugly solution in both time and space.
<
fcn init(_x,_y){ var[const] x=_x, y=_y; }
fcn distance(p){ (p.x-x).hypot(p.y-y) }
Line 4,907 ⟶ 5,329:
if(d1 < d2) p1 else p2
});
}</
<
2.0, 0.0, 8.0, 4.0,
7.0, 4.0, 9.0, 10.0,
Line 4,922 ⟶ 5,344:
0.293786, 0.691701, 0.839186, 0.72826)
.pump(List,Void.Read,Point);
closestPoints(points).println();</
{{out}}
<pre>
Line 4,928 ⟶ 5,350:
L(Point(0.925092,0.81822),Point(0.891663,0.888594),0.0779102)
</pre>
=={{header|ZX Spectrum Basic}}==
{{trans|BBC_BASIC}}
<
20 FOR i=1 TO 10
30 READ x(i),y(i)
Line 4,953 ⟶ 5,374:
210 DATA 0.211332,0.221507
220 DATA 0.293786,0.691701
230 DATA 0.839186,0.728260</
|