diff options
-rw-r--r-- | src/ClosestPair/ClosestPair.cs | 54 |
1 files changed, 23 insertions, 31 deletions
diff --git a/src/ClosestPair/ClosestPair.cs b/src/ClosestPair/ClosestPair.cs index e98f91d..2238275 100644 --- a/src/ClosestPair/ClosestPair.cs +++ b/src/ClosestPair/ClosestPair.cs @@ -68,16 +68,7 @@ namespace ClosestPair if (S.SortedByY.Length < 2) return qPair.Distance < rPair.Distance ? qPair : rPair; - PointPair sPair = new PointPair(S.SortedByY[0], S.SortedByY[1]); - double min = double.MaxValue; - for (int i = 0; i < S.SortedByY.Length; i++) - for (int j = i + 1; j < S.SortedByY.Length && j <= i + 7; j++) - if (S.SortedByY[i].DistanceTo(S.SortedByY[j]) < min) - { - min = S.SortedByY[i].DistanceTo(S.SortedByY[j]); - sPair = new PointPair(S.SortedByY[i], S.SortedByY[j]); - } - + PointPair sPair = BruteForce(S.SortedByY, 7); if (sPair.Distance < delta) return sPair; @@ -94,31 +85,32 @@ namespace ClosestPair // return (Point r0, Point r1) } - static PointPair BruteForce(Point[] P) + static PointPair BruteForce(Point[] points) + => BruteForce(points, points.Length); + + static PointPair BruteForce(Point[] points, int queueSize) { - double min = double.MaxValue; - PointPair pair = new PointPair(P[0], P[1]); - - for (int i = 0; i < P.Length; i++) - for (int j = i + 1; j < P.Length; j++) - if (P[i].DistanceTo(P[j]) < min) - { - min = P[i].DistanceTo(P[j]); - pair = new PointPair(P[i], P[j]); - } - return pair; + PointPair closestPair = new(new Point(0, 0), new Point(int.MaxValue, int.MaxValue)); + Queue<Point> pointQueue = new(); + + foreach (Point point in points) + { + pointQueue.Enqueue(point); + + if (pointQueue.Count < queueSize) + continue; + + Point current = pointQueue.Dequeue(); + + foreach (Point next in pointQueue) + if (current.DistanceTo(next) < closestPair.Distance) + closestPair = new(current, next); + } + + return closestPair; } - // public void Split<T>(T[] array, int index, out T[] first, out T[] second) - // { - // first = array.Take(index).ToArray(); - // second = array.Skip(index).ToArray(); - // } - // public void SplitMidPoint<T>(T[] array, out T[] first, out T[] second) - // { - // Split(array, array.Length / 2, out first, out second); - // } } } |