IN C++

In this lab exercise, you will use spatial hashing to find the closest pair among 1 million points spread uniformly across a unit square in the 2D plane. Although this problem is easily solved in (n2) time by comparing all pairs of points, this solution is too slow for input sizes n on the order of 100,000 to 1 million, as is the case here.

Download the starter code which includes two text files each containing a list of points. You will implement the function closestPair() which takes a string parameter for the file with the list of points to open. This function will open and read the file then find the distance between the closest pair of points which will be returned as a double type value.

The two text files included: points100.txt and points250k.txt contain 100 and 250,000 points respectively. The general format is the first line contains the number of points in the file and the remaining lines will contain two space-separated real numbers per line giving the x and y coordinates of a point. All points (x, y) live strictly inside the unit square described by 0 x < 1 and 0 y < 1. Remember that the distance between two points (x1, y1) and (x2, y2) is given by sqrt ((x1 x2)^2 + (y1 y2)^2).

As a small caveat, the C++ library has a function named distance already defined (which does something other than computing geometric distance above), so you if you write a function to compute distance, you should probably give it a name other than distance or else obscure compiler errors might result.

To find the closest pair of points quickly, you will divide the unit square containing the points into a b b grid of square cells, each representing a 2D square of size 1/b 1/b. Each point should be hashed to the cell containing it. For example, if you are storing the x coordinate of a point in a double variable named x, then (int)(x * b) will scale the coordinate up by b and round down to the nearest integer; the result (in the range 0 . . . b 1) can be used as an one of the indices into your 2D array of cells. The other index is calculated the same way, only using the y coordinate.

After hashing, each point needs only to be compared to the other points within its cell, and the 8 cells immediately surrounding its cell this should result in many fewer comparisons than if we simply compared every point to every other point. You will need to select an appropriate value of b as part of this lab exercise. Keep in mind that the value of b should scale appropriately based on the number of points in the unit square, for example b will need to be a greater value when working with 250,000 points than working with 100 points. You may want to consider what are the dangers in setting b too low or too high.

Since b must scale with the number of points (giving b x b cells) and the number of points within a cell will vary from one cell to another, a dynamically allocated data structure must be used. You may use the STL vector class for this. One approach that can be used is to have a 2D vector (a vector of vectors) representing the cells with each cell having a vector of points (the resulting data type would be vector>>).

The closestPair() function should consist of the following major steps:

1. Open the file and read the number of points that will be listed to determine an appropriate value for b (the number of divisions along the x-axis and y-axis within the unit square for spatial hashing).

2. Initialize the b x b array of cells to each contain an empty set of points.

3. Read the remainder of the input file adding each point to the appropiate cell it maps to.

4. For each point compare it to all the points within its cell and the 8 adjacent cells; remember the smallest distance obtained during this process.

5. Return the minimum distance.

Part of this lab also involves figuring out a good choice for the value of b. Please include in a comment in your code a brief description of why you think your choice of b is a good one. Submit the file closestPair.cpp with the implemented closestPair() function.

closestPair.cpp

/* * Name: * Date Submitted: * Lab Section: * Assignment Name: */

#include #include #include #include #include

using namespace std;

struct point { double x; double y; };

/*Implement the following function Reads in a file specified by the parameter Format of file: #of points on first line remaining (#of points) lines: x-value and y-value of point one point per line x-value and y-value are double-precision values and bounded by the unit square 0.0 <= x,y < 1.0 Should use "spatial hashing" where the #of cells scales with the #of points and find the distance between the closest pair of points which will be returned as a double type value */ double closestPair(string filename);

int main() { double min; string filename; cout << "File with list of points within unit square: "; cin >> filename; min = closestPair(filename); cout << setprecision(16); cout << "Distance between closest pair of points: " << min << endl; return 0; }

points100.txt

100 0.7977055242431441 0.2842945682533633 0.5069721442290844 0.1745915333250858 0.1056128118010866 0.4655386965548695 0.9452178666802381 0.02164071576711531 0.5801569883701514 0.9551154884313102 0.6541671729612641 0.2084066195646328 0.4077641701397764 0.7837305268045455 0.2547332841431741 0.3687404245068159 0.7625239646028334 0.570257171363553 0.4345602227588827 0.4766713469354918 0.8758058217633901 0.8956599204363177 0.4540800728184122 0.7208285300197294 0.8711559280702514 0.536922895657251 0.1021534045581789 0.771878369218414 0.6185958613568046 0.7020603220891695 0.6981983771672291 0.9621315492131957 0.1865078541824229 0.3070515027607176 0.5637630711621611 0.2438510076494884 0.6491395060966105 0.5066660223152767 0.8585106264720312 0.1199023899047327 0.0600441072577686 0.6150461804657272 0.6988214913343326 0.7960891955643983 0.5097768855624988 0.4483496969949777 0.9309130670360199 0.5282516738167281 0.7292677731628638 0.5479021724275256 0.3393807709292452 0.003890287751413675 0.8829435561472486 0.4772987024801743 0.7156142013609429 0.6912039389646717 0.1233573416452369 0.4487021816846383 0.04541853821191584 0.540391479686761 0.3092474220233765 0.3235793309017462 0.9948459977278354 0.1866285456731142 0.7028670474026075 0.9657450323016548 0.1403960326430837 0.01616213270912518 0.395228786861528 0.4511730891536054 0.0005250292810372374 0.7672538195418787 0.4019954291859458 0.5037331361194259 0.300899046225957 0.5364553339410142 0.2322728020395302 0.1291995057955369 0.2829452149723889 0.09990688821288636 0.8964731460260199 0.4296957294138094 0.88354716673185 0.3721796455648302 0.3448165421768987 0.7719868355641272 0.5397616138673501 0.960977114668446 0.8576729816418937 0.3748439928703319 0.01587571521586603 0.9612177187246145 0.85807076934989 0.009251258893498288 0.04189742852066721 0.9490485900162376 0.7979195608189488 0.2238295110884286 0.4138839481678814 0.2227626574805118 0.2685126960803549 0.3910966167919536 0.4480743462155022 0.00903502025858437 0.1413413559527783 0.687233051004089 0.003944033833923334 0.7217063159047046 0.007644920772106046 0.494993449104048 0.4677941415347082 0.8406062364168272 0.5827442760993863 0.971923193300241 0.3627436158361813 0.6380208140723526 0.1068433885235893 0.2147278109340591 0.3374245120060465 0.1441366181844157 0.5152255756653635 0.7832113906392959 0.3768756900597059 0.414903014898301 0.0831716569276937 0.8412665729051994 0.3378971752657954 0.8064782467967712 0.5514921673373047 0.9229925873712039 0.869690608785892 0.1730561899187551 0.04300025952576878 0.5554904648708102 0.8891479201967342 0.4394338943115931 0.8105219882168686 0.0740855374250977 0.4855996211984437 0.2545279376211175 0.7842506168465262 0.5764548255282985 0.164387451458446 0.5763315644153698 0.2361697204412225 0.1180082657985081 0.6077310700195284 0.7617195786496179 0.3885307421122812 0.1264514207585324 0.5568469694491793 0.9973139867494624 0.9927120549887148 0.3581485415862886 0.5749545732706109 0.4231943530717113 0.3231417765894459 0.2766736403705065 0.09550014414588147 0.2509692312616886 0.375269982535901 0.7582690781988621 0.1460203220913636 0.4963145602637588 0.482262443123908 0.955165945696268 0.9065154432412527 0.07576647661754354 0.1716642443843192 0.3675332203498513 0.6083719552374308 0.4199997860768524 0.3322290668016687 0.5528572995515384 0.2088834906672915 0.2752096248253539 0.6249832343541452 0.8734970013926511 0.6878844179846711 0.6941704442370946 0.563223240345754 0.981652884972277 0.227118081355082 0.5525452026161558 0.9439421685131286 0.4492602772331744 0.9482019850055539 0.5570931800800958 0.9901435104461384 0.2463619987312738 0.03351826846798376 0.7400359796814685 0.1908584546079176 0.3919955684159645 0.1151111511187454 0.4362393456504146 0.2095008877601214 0.05714334565113377 0.1160283136896126 0.3388707490617974