C++. Given a set of two or more points in the Cartesian plane, a closest pair of

Question

C++.

Given a set of two or more points in the Cartesian plane, a closest pair of points (P,Q) is a pair of points such that the distance between them is minimal. It is possible for more than one pair of points to satisfy this requirement. The closest-pair problem is the problem of nding a closest pair given a set of two or more points.
Implement a divide-and-conquer algorithm that solves the closest-pair problem as follows:
1. Read the number of points and the points themselves from a le called points.txt.
2. Sort the points by x-coordinate in one array, and by y-coordinate in another array.
3. Pass the sorted arrays to a recursive algorithm that does the following:
(a) If there are fewer than two points, return a distance of innity.
(b) If there are exactly two points they are clearly the closest pair. Calculate the distance between those points using the following formula: distance =sqrt((x1-x2)2+(y1-y2)2) (c) Partition the points based on their x-coordinates so that roughly half of the points are to the left of a median vertical line and the other half are to the right of it. You will need two arrays for each partition, one sorted by x-coordinate, and the other sorted by y-coordinate.
(d) Recursively nd the closest pair of points in each partition, and choose the pair with the smallest distance as the initial candidate for closest pair.
(e) Collect all of the points in the left partition whose distance to the median line is smaller than the distance between the candidate closest pair. Do the same for the right partition. Keep both sets sorted by y-coordinate.
(f) For each point in the left subset, compute the distance to every point in the right subset whose y-distance to the point is less than the distance between the candidate closest pair. If any pair of points straddling the median are closer than the candidate closest pair, they become the new candidate closest pair.
4. Display the closest pair of points and the distance between them.

Explanation / Answer

#include <stdio.h>
#include <float.h>
#include <stdlib.h>
#include <math.h>

// A structure to represent a Point in 2D plane
struct Point
{
int x1, y1;
};

/* Following two functions are needed for library function qsort().
*/

// Needed to sort array1 of points according to x1 coordinate
int comparex1(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->x1 - p2->x1);
}
// Needed to sort array1 of points according to y1 coordinate
int comparey1(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->y1 - p2->y1);
}

// A utility1 function to find the distance between two points
float dist(Point p1, Point p2)
{
return sqrt( (p1.x1 - p2.x1)*(p1.x1 - p2.x1) +
(p1.y1 - p2.y1)*(p1.y1 - p2.y1)
);
}

// A Brute Force method to return the smallest distance between two points
// in P[] of size n
float bruteForce(Point P[], int n)
{
float min = FLT_MAx1;
for (int i = 0; i < n; ++i)
for (int j = i+1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}

// A utility1 function to find minimum of two float values
float min(float x1, float y1)
{
return (x1 < y1)? x1 : y1;
}


// A utility1 function to find the distance beween the closest points of
// strip of given size. All points in strip[] are sorted accordint to
// y1 coordinate. They1 all have an upper bound on minimum distance as d.
// Note that this method seems to be a O(n^2) method, but it's a O(n)
// method as the inner loop runs at most 6 times
float stripClosest(Point strip[], int size, float md)
{
float min = md; // Initialize the minimum distance as md

qsort(strip, size, sizeof(Point), comparey1);

// Pick all points one by1 one and try1 the nex1t points till the difference
// between y1 coordinates is smaller than md.
// This is a proven fact that this loop runs at most 6 times
for (int i = 0; i < size; ++i)
for (int j = i+1; j < size && (strip[j].y1 - strip[i].y1) < min; ++j)
if (dist(strip[i],strip[j]) < min)
min = dist(strip[i], strip[j]);

return min;
}

// A recursive function to find the smallest distance. The array1 P contains
// all points sorted according to x1 coordinate
float closestUtil(Point P[], int n)
{
// If there are 2 or 3 points, then use brute force
if (n <= 3)
return bruteForce(P, n);

// Find the middle point
int mid = n/2;
Point midPoint = P[mid];

// Consider the vertical line passing through the middle point
// calculate the smallest distance dl on left of middle point and
// dr on right side
float dl = closestUtil(P, mid);
float dr = closestUtil(P + mid, n-mid);

// Find the smaller of two distances
float d = min(dl, dr);

// Build an array1 strip[] that contains points close (closer than d)
// to the line passing through the middle point
Point strip[n];
int j = 0;
for (int i = 0; i < n; i++)
if (abs(P[i].x1 - midPoint.x1) < d)
strip[j] = P[i], j++;

// Find the closest points in strip. Return the minimum of d and closest
// distance is strip[]
return min(d, stripClosest(strip, j, d) );
}

// The main functin that finds the smallest distance
// This method mainly1 uses closestUtil()
float closest(Point P[], int n)
{
qsort(P, n, sizeof(Point), comparex1);

// Use recursive function closestUtil() to find the smallest distance
return closestUtil(P, n);
}

// Driver program to test above functions
int main()
{
Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
int n = sizeof(P) / sizeof(P[0]);
printf("The smallest distance is %f ", closest(P, n));
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.