119 lines
2.9 KiB
Plaintext
119 lines
2.9 KiB
Plaintext
class Point
|
|
{
|
|
Float x
|
|
Float y
|
|
|
|
// create a random point
|
|
new make (Float x := Float.random * 10, Float y := Float.random * 10)
|
|
{
|
|
this.x = x
|
|
this.y = y
|
|
}
|
|
|
|
Float distance (Point p)
|
|
{
|
|
((x-p.x)*(x-p.x) + (y-p.y)*(y-p.y)).sqrt
|
|
}
|
|
|
|
override Str toStr () { "($x, $y)" }
|
|
}
|
|
|
|
class Main
|
|
{
|
|
// use brute force approach
|
|
static Point[] findClosestPair1 (Point[] points)
|
|
{
|
|
if (points.size < 2) return points // list too small
|
|
Point[] closestPair := [points[0], points[1]]
|
|
Float closestDistance := points[0].distance(points[1])
|
|
|
|
(1..<points.size).each |Int i|
|
|
{
|
|
((i+1)..<points.size).each |Int j|
|
|
{
|
|
Float trydistance := points[i].distance(points[j])
|
|
if (trydistance < closestDistance)
|
|
{
|
|
closestPair = [points[i], points[j]]
|
|
closestDistance = trydistance
|
|
}
|
|
}
|
|
}
|
|
|
|
return closestPair
|
|
}
|
|
|
|
// use recursive divide-and-conquer approach
|
|
static Point[] findClosestPair2 (Point[] points)
|
|
{
|
|
if (points.size <= 3) return findClosestPair1(points)
|
|
points.sort |Point a, Point b -> Int| { a.x <=> b.x }
|
|
bestLeft := findClosestPair2 (points[0..(points.size/2)])
|
|
bestRight := findClosestPair2 (points[(points.size/2)..-1])
|
|
|
|
Float minDistance
|
|
Point[] closePoints := [,]
|
|
if (bestLeft[0].distance(bestLeft[1]) < bestRight[0].distance(bestRight[1]))
|
|
{
|
|
minDistance = bestLeft[0].distance(bestLeft[1])
|
|
closePoints = bestLeft
|
|
}
|
|
else
|
|
{
|
|
minDistance = bestRight[0].distance(bestRight[1])
|
|
closePoints = bestRight
|
|
}
|
|
yPoints := points.findAll |Point p -> Bool|
|
|
{
|
|
(points.last.x - p.x).abs < minDistance
|
|
}.sort |Point a, Point b -> Int| { a.y <=> b.y }
|
|
|
|
closestPair := [,]
|
|
closestDist := Float.posInf
|
|
|
|
for (Int i := 0; i < yPoints.size - 1; ++i)
|
|
{
|
|
for (Int j := (i+1); j < yPoints.size; ++j)
|
|
{
|
|
if ((yPoints[j].y - yPoints[i].y) >= minDistance)
|
|
{
|
|
break
|
|
}
|
|
else
|
|
{
|
|
dist := yPoints[i].distance (yPoints[j])
|
|
if (dist < closestDist)
|
|
{
|
|
closestDist = dist
|
|
closestPair = [yPoints[i], yPoints[j]]
|
|
}
|
|
}
|
|
}
|
|
}
|
|
if (closestDist < minDistance)
|
|
return closestPair
|
|
else
|
|
return closePoints
|
|
}
|
|
|
|
public static Void main (Str[] args)
|
|
{
|
|
Int numPoints := 10 // default value, in case a number not given on command line
|
|
if ((args.size > 0) && (args[0].toInt(10, false) != null))
|
|
{
|
|
numPoints = args[0].toInt(10, false)
|
|
}
|
|
|
|
Point[] points := [,]
|
|
numPoints.times { points.add (Point()) }
|
|
|
|
Int t1 := Duration.now.toMillis
|
|
echo (findClosestPair1(points.dup))
|
|
Int t2 := Duration.now.toMillis
|
|
echo ("Time taken: ${(t2-t1)}ms")
|
|
echo (findClosestPair2(points.dup))
|
|
Int t3 := Duration.now.toMillis
|
|
echo ("Time taken: ${(t3-t2)}ms")
|
|
}
|
|
}
|