Closest Points Computational Problem Using Divide and Conquer Algorithm

CS 320 Programming Project 2Closest Points Computational Problem
Using Divide and Conquer Algorithm
DUE DATE is posted on the BlackBoard web site for the course.
File Name Requirements and What to Submit:
•
•
•
•
•
•
The VS 2022 (Debug-x64 configuration) Solution-Project Name MUST be CS320P02YourLastName.
The zipped file name must be named: CS320P02YourLastName.zip.
The zipped file must contain the entire project folder containing your Visual Studio 2022 (Debug-x64
configuration) solution-project for Project 2. Also, any test cases (input and corresponding output) must
be included in that zip file. Be sure to show the input-output file correspondence through some consistent
naming convention.
Provide a word document describing the analysis of your algorithm. Use appropriate notation. That
should be in the submitted zip file also.
If your program does not work, please include a Word or notepad file explaining what works and what
doesn’t work.
The zip file should be submitted to the assessment icon on Blackboard.
Description of Closest Points Computational Problem:
Given a finite set S of n ≥ 2 points p = (x, y) where S ⊆ Χ x Υ, you are to find two points in S with the
minimum Euclidean distance between two points in S. In this project you will let X and Y be the set of
representable real numbers in the C++ data type, double. The distance between two points 𝑝𝑝1 = (𝑥𝑥1 , 𝑦𝑦1 )
and 𝑝𝑝2 = (𝑥𝑥2 , 𝑦𝑦2 ) is defined by the Euclidean distance metric:
𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷𝐷(𝑝𝑝1 , 𝑝𝑝2 ) = �(𝑥𝑥1 − 𝑥𝑥2 )2 + (𝑦𝑦1 − 𝑦𝑦2 )2
Example:
S = {p1 = (5.60, 0.01), p2 = (8.08, 1.93), p3 = (4.80, 5.85), p4 = (8.96, 3.50), p5 = (7.47, 8.22), p6 = (8.59, 1.74), p7 = (5.14, 7.11)}
Example File Format
Cartesian Plane Depiction
5.60 0.01
8.08 1.93
4.80 5.85
8.96 3.50
7.47 8.22
8.59 1.74
5.14 7.11
p5
p7
p3
p4
p2
p1
0.544243
p6
Closest points are: p2 = (8.08, 1.93) and p6 = (8.59, 1.74) with distance = 0.544243
NOTE: You need not implement the graph shown on the upper right. However, you might find it to be a useful tool
for examining your test data. This plot data was generated using
http://www.shodor.org/interactivate/activities/SimplePlot/.
Closest Points Problem Project Using a Divide and Conquer Approach
Page 1 of 4
Brute Force Algorithm:
Read all points (n points) into an array
for each input point pi = (xi, yi)
for each other point pj = (xj, yj)
compute distance between pi and pj
if ( distance < minimum distance ) minimum distance = distance Divide and Conquer Approach: See your textbook for this approach to solve the problem. (Assume a vector, P, of size n and components of type Point. Also assume that the points in P have been sorted by x coordinate.) This pseudo-code is based upon, but modified, from Geek-for-Geeks. This code only returns the smallest distance. Your implementation must return two Points: p = (x, y) and p’ = (x’, y’) such that p ≠ p’, distance(p, p’) ≤ distance(pi, pj) for all pi, pj and i≠j. Also, your program must also print the distance between the p and p’. https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm/ Note: The algorithm and data structures used below must be convert to C++11 code and meet the following constraints: you must use the supplied Point class and implement the sets of points as vector and you must return two Points representing the two points with the smallest distance between them rather than just the distance. 1) Find the middle point in the sorted array, we can take P[n/2] as middle point. 2) Divide the given array in two halves. The first subarray contains points from P[0] to P[n/2]. The second subarray contains points from P[n/2+1] to P[n-1]. 3) Recursively find the smallest distances in both subarrays. Let the distances be dl and dr. Find the minimum of dl and dr. Let the minimum be d. 4) From above 3 steps, we have an upper bound d of minimum distance. Now we need to consider the pairs such that one point in pair is from left half and other is from right half. Consider the vertical line passing through passing through P[n/2] and find all points whose x coordinate is closer than d to the middle vertical line. Build an array strip[] of all such points. 5) Sort the array strip[] according to y coordinates. This step is O(nlog(n)). It can be optimized to O(n) by recursively sorting and merging. You must use mergesort the points in your implementation and sort points in the strip based upon the y-coordinates. 6) Find the smallest distance in strip[]. From first look, it seems to be an O(n2) step, but it is actually O(n). It can be proved geometrically that for every point in strip, we only need to check at most 7 points after it. (Note that strip is sorted according to Y coordinate.) For more analysis, see http://people.csail.mit.edu/indyk/6.838old/handouts/lec17.pdf Here is sample pseudocode for steps 5 and 6: finding the min distance within strip and across midpoint. This is from https://www.youtube.com/watch?v=0W_m46Q4qMc. Also, see your textbook. double closestAcrossStrip(Point strip[], unsigned size, double d) { double min = d; sort(strip, sortOnYcoordinate); for(unsigned i = 0; i < size; i++) for(unsigned j = i + 1; j < size && (strip[j].y-strip[i].y) < min; j++) if(distance(strip[j],strip[i]) < min ) min = distance(strip[j], strip[i]); 7) Finally return the minimum of d and distance calculated in above step (step 6). This is the minimum of the left subset, right subset, and strip. NOTE: What is not clear from the above pseudo-code from steps 1-7 is the base case. Use the bruteforce nested loop approach when the amount the number of points in the subset is 4 points or less. Closest Points Problem Project Using a Divide and Conquer Approach Page 2 of 4 Driver Algorithm: 1) 2) 3) 4) Prompt the user for filename according to the prompt specifications shown below. Open file for reading. Use only text files (.txt file extensions). Read file of n > 1 unique points into a vector object.
Call closest() and have it return the closest pair, where the prototype of closest is:
pair closest(vector points)
5) Print each point returned from closest() and distance between them according to output specifications
shown below.
Input Specifications. Your program must read a .txt file containing the points as ordered pairs of literals
of type double each separated by whitespace. Program must prompt the user for a filename containing
the input points. The filename.txt must be replaced with an existing filename that represents a file
containing the points.
Enter Filename: filename.txt
The prompt must be exactly as shown. One space after the colon is required.
The file must contain n>1 ordered pairs of literals of type double. (See example above with the file of 7
points.) Although only whitespace is required, it easier to see the points in files with new lines after
point, i.e., after each pair of coordinates. You may assume that the input files have unique points — no
repetition of points.
Output Specifications. See below for format. Your output text and spaces must match exactly. Note
that balanced parentheses and comma are added for the output presentation of points.
Closest points are:(x1, y1) and (x2, y2) with distance =
Output Example. Using the above input example, the output from that problem instance is shown
below.
Closest points are: (8.08, 1.93) and (8.59, 1.74) with distance = 0.544243
Note: you will not be able to use the “>(ifstream & in, Point & p) {
#include
double x;
using namespace std;
double y;
class Point
in >> x;
{
in >> y;
public:
p.setX(x);
Point()
p.setY(y);
{
return in;
this->x = 0.0;
}
this->y = 0.0;
ostream & operatorx = p.x;
this->y = p.y;
}
const Point & operator=(const Point & rhs)
{
if (this != &rhs) {
x = rhs.x;
y = rhs.y;
}
return *this;
}
bool operator==(const Point p) const
{
return (this->x == p.x && this->y == p.y);
}
bool operator!=(const Point p) const
{
return (this->x != p.x || this->y != p.y);
}
double distance(Point p) const
{
return sqrt((this->x – p.getX())*(this->x – p.getX()) + (this->y – p.getY())*(this->y – p.getY()));
}
double getX() const {
return this->x;
}
double getY() const {
return this->y;
}
void setX(double x)
{
this->x = x;
}
void setY(double y)
{
this->y = y;
}
class CompareXCoordinate {
public:
bool operator()(const Point & p1, const Point & p2) const
{
return (p1.getX() < p2.getX()); } }; class CompareYCoordinate { public: bool operator()(const Point & p1, const Point & p2) const { return (p1.getY() < p2.getY()); } }; private: double x; Closest Points Problem Project Using a Divide and Conquer Approach double y; }; Page 4 of 4