0

I am not exactly sure what I am doing wrong in my current situation.

The goal of my program is to read in points from a text file and insert them into a grid, then find the shortest distance between the points. However, I am having an issue inserting the points into the grid.

I am supposed to use a multidimensional vector being vector<vector<vector>>, but when I try to insert values into my vector I get a segmentation fault.

Here is what I have:

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <cmath>

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){
    std::ifstream infile(filename);
    int num_points;
    double xval;
    double yval;
    double shortestDist=0;
   
    //finds number to create size of grid
    infile >> num_points;
    int b=sqrt(num_points);
    double interval=1/b;
    
    //creates grid
    vector<vector<vector<point>>> pointTable(b,vector<vector<point>>(b,vector<point>(b)));
    
    
    while(!infile.eof()){
        //reads in x and y value and creates point
        point insertPoint;
        infile >> xval;
        infile >> xval;
        insertPoint.x=xval;
        insertPoint.y=yval;
        
        //finds where to insert point on grid
        int xposition=xval/interval;
        int yposition=yval/interval;
        
        //inserts point into grid
        pointTable[xposition][yposition].push_back(insertPoint);
        


    }
    return shortestDist;
}

In the program, b is supposed to be the amount of 'cells' in the grid we are creating, and it is based off the number of points in the text file, which is read in as the first line of the file. The interval is the distance between each 'cell' since the grid is from 0 to 1, and all the point fit inside of this interval.

An example of a text file that would be read in:

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

Where 100 points would be read in.

I haven't attempted to implement the distance finding part of the algorithm yet because I need to have the points inserted before I do that.

Any help is appreciated, thanks!

ianspivey11
  • 43
  • 4
  • 1
    [`while(!infile.eof()){` is always a bug](https://stackoverflow.com/questions/5605125/why-is-iostreameof-inside-a-loop-condition-i-e-while-stream-eof-cons), so that's at least one fatal bug in the shown code. Then, the code fails to do any kind of bounds checking, so if the calculations are even slightly off, this will result in undefined behavior due to indexing of nonexistent vector members. Add debugging dumps, to verify that all indices are within bounds. – Sam Varshavchik Oct 20 '20 at 00:52
  • Does that example text file produce the fault? – Beta Oct 20 '20 at 01:37
  • @Beta yes, i think i resolved the issue. i fixed the eof bug and i think the problem was my interval variable wasnt a float so it was dividing by 0 for the values – ianspivey11 Oct 20 '20 at 01:53
  • `double interval=1/b` operates on two int values. It'll be 0 if `b` is larger than 1, and you'll get a division by zero later on. Turn on all compiler warnings and you'll see implicit truncation casts (e.g. double-to-int) for things like `int b = sqrt(num_points)`. – paddy Oct 20 '20 at 01:53

0 Answers0