Find Nearest Points The GPS navigation system uses the graph and geometric algor

Question

Find Nearest Points

The GPS navigation system uses the graph and geometric algorithms to calculate distances and map a route. One of the geometric problems is the closest-pair problem. Given a set of points, the closest-pair problem is to find the two points that are nearest to each other. Write a program that computes the distances between all pair of points and find the one with the minimum distance as follows:

Ask the user to enter the number of points.

Ask the user to enter x and y positions for each point. Store the positions in a 2-D array. What should the dimensions of the 2-D array be?

Compute the distance between the first two points and initialize the variable that represents the shortest distance. Recall that the distance between the two points (x1, y1) and (x2, y2) is computed by taking the square root of the quantity (x1 - x2)^2 + (y1 - y2)^2.

Use a nested for loop to compute the distance for every two points and update the shortest distance and the two points with the shortest distance.

5. Display the shortest distance and the closest two points.

Explanation / Answer

// A divide and conquer program in C/C++ to find the smallest distance from a
// given set of points.

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

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

typedef struct Point Point;

/* Following two functions are needed for library function qsort().
Refer: http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ */

// Needed to sort array of points according to X coordinate
int compareX(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->x - p2->x);
}
// Needed to sort array of points according to Y coordinate
int compareY(const void* a, const void* b)
{
Point *p1 = (Point *)a, *p2 = (Point *)b;
return (p1->y - p2->y);
}

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

// 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_MAX;
int i,j;
for (i = 0; i < n; ++i)
for (j = i+1; j < n; ++j)
if (dist(P[i], P[j]) < min)
min = dist(P[i], P[j]);
return min;
}

// A utility function to find minimum of two float values
float min(float x, float y)
{
return (x < y)? x : y;
}

// A utility function to find the distance beween the closest points of
// strip of given size. All points in strip[] are sorted accordint to
// y coordinate. They 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 d)
{
float min = d; // Initialize the minimum distance as d
int i,j;

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

// Pick all points one by one and try the next points till the difference
// between y coordinates is smaller than d.
// This is a proven fact that this loop runs at most 6 times
for ( i = 0; i < size; ++i)
for (j = i+1; j < size && (strip[j].y - strip[i].y) < 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 array P contains
// all points sorted according to x 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 array strip[] that contains points close (closer than d)
// to the line passing through the middle point
Point strip[n];
int j = 0;
int i;
for (i = 0; i < n; i++)
if (abs(P[i].x - midPoint.x) < 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 mainly uses closestUtil()
float closest(Point P[], int n)
{
qsort(P, n, sizeof(Point), compareX);

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

// Driver program to test above functions
int main()
{
Point p[100];
int i,j;
int no_of_points;
printf("Enter the number of points : ");
scanf("%d",&no_of_points);
printf("Enter the co-ordinates of the points : ");
for(i = 0; i< no_of_points; i++)
{
scanf("%d %d",&(p[i].x), &(p[i].y));
}
printf("The smallest distance is %f ", closest(p, no_of_points));
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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