diff options
| -rw-r--r-- | src/ClosestPair/ClosestPair.cs | 74 |
1 files changed, 34 insertions, 40 deletions
diff --git a/src/ClosestPair/ClosestPair.cs b/src/ClosestPair/ClosestPair.cs index fcc25b6..6b46398 100644 --- a/src/ClosestPair/ClosestPair.cs +++ b/src/ClosestPair/ClosestPair.cs @@ -18,74 +18,68 @@ namespace ClosestPair FindClosestPair calls recursive ClosestPair(Px, Py), which returns the closest points */ - // points[1] - // points.SortedByX[1] - // points.SortedByY[1] Point[] Px = points.SortByX(); Point[] Py = points.SortByY(); return ClosestPairRecursive(Px, Py); } - static PointPair ClosestPairRecursive(Point[] Px, Point[] Py) + static PointPair ClosestPairRecursive(Point[] sortedByX, Point[] sortedByY) { - if (Px.Length <= 3) - return BruteForce(Px); + if (sortedByX.Length <= 3) + return BruteForce(sortedByX); // Creates four lists, needs to be O(n log n) // lists: Qx, Qy (first half of Px and Py) // Rx, Ry (last half of Px and Py) - Px.Split(out Point[] Qx, out Point[] Rx); - Py.Split(out Point[] Qy, out Point[] Ry); + sortedByX.Split(out Point[] sortedByXLeft, out Point[] sortedByXRight); + sortedByY.Split(out Point[] sortedByYLeft, out Point[] sortedByYRight); // calls ClosestPairRecursive on (Qx, Qy), (Rx, Ry) returns closest points in each set - PointPair qPair = ClosestPairRecursive(Qx, Qy); - PointPair rPair = ClosestPairRecursive(Rx, Ry); + PointPair closestPairLeft = ClosestPairRecursive(sortedByXLeft, sortedByYLeft); + PointPair closestPairRight = ClosestPairRecursive(sortedByXRight, sortedByYRight); - double delta = Math.Min(qPair.Distance, rPair.Distance); + double delta = Math.Min(closestPairLeft.Distance, closestPairRight.Distance); // x value of midpoint - int L = Qx[Qx.Length - 1].X; - - //Sx = points in Px within distance delta of L - List<Point> Sx = new(); - foreach (Point p in Px) - if (p.DistanceToX(L) < delta) - Sx.Add(p); - else if (Sx.Count > 0) - break; - - + int midpointX = FindMidpointX(sortedByX); // Create Sy (Sx sorted by y) - Point[] Sy = Sx.ToArray().SortByY(); + Point[] withinDelta = PointsWithinDelta(sortedByX, delta, midpointX).SortByY(); + - // for each point s in Sy - // compute distance from s - // to each of next 15 points in Sy - // Let (Point s0, Point s1) be minimum distance pair - // All of this is O(n) - if (Sy.Length < 2) - return qPair.Distance < rPair.Distance ? qPair : rPair; + if (withinDelta.Length < 2) + return closestPairLeft.Distance < closestPairRight.Distance ? closestPairLeft : closestPairRight; - PointPair sPair = BruteForce(Sy, 7); + PointPair closestPairMiddle = BruteForce(withinDelta, 7); - if (sPair.Distance < delta) - return sPair; + if (closestPairMiddle.Distance < delta) + return closestPairMiddle; else - return qPair.Distance < rPair.Distance ? qPair : rPair; + return closestPairLeft.Distance < closestPairRight.Distance ? closestPairLeft : closestPairRight; + } - // if distance(Point s0, Point s1) < delta - // return (Point s0, Point s1) + static int FindMidpointX(Point[] points) + => points[points.Length / 2].X; - // else if (Point q0, Point q1) < (Point r0, Point r1) - // return (Point q0, Point q1) + // return the points within points that are within distance delta + static Point[] PointsWithinDelta(Point[] points, double delta, int midPoint) + { + List<Point> middle = new(); + foreach (Point point in points) + if (point.DistanceToX(midPoint) < delta) + middle.Add(point); + else if (middle.Count > 0) + break; - // else - // return (Point r0, Point r1) + return middle.ToArray(); } + // for each point s in Sy + // compute distance from s to each of next 15 points in Sy + // Let (Point s0, Point s1) be minimum distance pair + // All of this is O(n) static PointPair BruteForce(Point[] points) => BruteForce(points, points.Length); |