Trying to compute the closest pair. Help?

[tit0n]

we are given

double d = p[a].distance(p[b]);

Im not sure how to make out this code. Can anyone explain? And how would I go about this?

[keskiverto]

Was that all that you were given?

The d is clearly a double, but what are the types of p, a, b?


You write "the closest pair" and the code has "distance". If something is "close", then "distance" is small?

"closest pair" implies that there are many "pairs" and you want to identify one particular pair. Perhasp you should look at each pair to check for something?



PS. Do not doublepost.

[tit0n]

Yeah sorry I am new here posted in wrong section. Okay so we are given 5 cluster files with coordinates X Y Z. We have to read the txt files and output the two closest pairs.
It is a project file with 5 total files, ill post the ones I think are relevant.

The complete main looks like this:

using namespace std;



int  main(){
     MyArray<point> p(100);

     int a=0, b=1;
     int number_point=0;
     ifstream in;
     ofstream out;
     char InputName[50];
     char OutputName[50];
     cout<< "Enter the input filename: ";
     cin>> InputName;
     in.open(InputName);
     cout<< "Enter the output filename: ";
     cin>> OutputName;
     out.open(OutputName);
     
     while (in){
           in>>p[number_point];
           if(!in)break;
           number_point++;
     }
     in.close();
     
     
     out<< "The file "<< InputName << " contains "<< number_point << " points" << endl;
    
     
     double d=p[a].distance(p[b]);
     
     //Insert your code here to compute the closest pair
     
     
     
     
     
     
     
    
     
     
     
     cout<< "End of program.";
    
     out.close();
     getch();
}  

POINT.CPP

#include <iostream>
#include <fstream>
#include "point.h"
#include <math.h>

//Constructor
point::point(){
	x = 0;
	y = 0;
	z = 0;


};

//Constructor
point:: point(double a, double b, double c ){
	x = a;
	y = b;
	z = c;



};

//Copy Constructor
point:: point(const point& p){

   x = p.x;
   y = p.y;
   z = p.z;

};

//Distance
double point::distance(point p){
	return sqrt(pow(x,2.0)+ pow(y,2.0)+ pow(z,2.0));


};

//Output stream
std::ostream& operator<<(std::ostream& out, const point& p){
	//Insert your code here
  out << p.x;
  out << p.y;
  out << p.z;


};

//Input stream
std::istream& operator>>(std::istream& in,  point& p){
        char skip;
        in>>skip >> p.x >> skip >> p.y >> skip >> p.z >> skip;
        return in;
};

POINT.H

#ifndef _point_h
#define _point_h

class point{
      protected:
             double x, y, z;
      public:
             point();
             point(double, double, double); 
             point (const point& );
             double distance (point );
             friend std::ostream& operator<<(std::ostream&, const point&);
             friend std::istream& operator>>(std::istream&, point&);

};


#endif 

[jonnin]

It looks like they want you to use the geometric linear distance formula across all the points in the file to find the 2 with the smallest distance.

the distance formula is

dist = sqrt( (p1.x - p2.x) * (p1.x - p2.x) + ... each dimension )

because p1.x and p2.x are just values, you can just subtract them first, you don't need to explode the multiplication or anything.

or, to put it in c...

double dx, dy, dz;
dx = p1.x - p2.x;
dy = p1.y - p2.y;
dz = p1.z - p2.z;

dx*=dx; //square them
dy*=dy;
dz*=dz;

dist = dx+dy+dx; //this is sufficient to compare
//IF the coordinates are bigger than 1.0, saving sqrt call

to be safe though...
dist = sqrt(dist);

so you probably want to wrap all that up into a function and then cross compare all the distances (I leave this for you to do) to find the smallest one.

hint:
in a loop somewhere
double smallest = 0;
if (result > smallest) smallest = result;

[tit0n]

Okay I have filled in the code on those other files, I am not sure if my out stream is right in POINT.CPP. Anyways I will keep rereading what you said and have a go. Seems a bit confusing to me still though. I am confused on how he define double d = p[a].distance(p[b]); Not sure what it means or how to implement. a = 0 and b = 1.


Thanks

[jonnin]

double d = p[a].distance(p[b]);
^^^^^^^

that looks like what he wants you to do is create a member function

double distance (point &p)
{
//what I said.
//being a class member, it operates on one point passed in and *this point.
}

[tit0n]

I am still having trouble. Could someone pseudo code what I need to do in the main so I can better picture it? That would be much appreciated.

[keskiverto]

Every point can "pair" with the other points. Each pair has a point to point distance. How would you list all pairs?

If you had N numbers, how would you find out the smallest of all values and which number has that value?

[tit0n]

Here is my new main I managed to get it to run two given points by myself. I am stuck again though. How would I make it run through a loop to find the two closest pairs in a txt file?

Example of one of the text files
(0,0,1)
(0,1,0)
(0,1,1)
(1,0,0)
(1,0,1)
(1,1,0)
(1,1,1)

using namespace std;

        double myDistance(point p,point p2){      // p = point. Function gets distance of points
        double dx, dy, dz;
        double result;
        double smallest;

        dx = p.x - p2.x;
        dy = p.y - p2.y;
        dz = p.z - p2.z;

       return sqrt(pow(p.x-p2.x,2.0)+ pow(p.y-p2.y,2.0)+ pow(p.z-p2.z,2.0));


//        for (int i; i < size; i++)

//
     //  if (result > smallest){

     //   smallest = result;
      //  }
    }

int  main(){
     MyArray<point> p(100);


     int a=0, b=1;
     int number_point=0;
     ifstream in;
     ofstream out;
     char InputName[50];
     char OutputName[50];
     cout<< "Enter the input filename: ";
     cin>> InputName;
     in.open(InputName);
     cout<< "Enter the output filename: ";
     cin>> OutputName;
     out.open(OutputName);

     while (in){
           in>>p[number_point];
           if(!in)break;
           number_point++;
     }
     in.close();


     out<< "The file "<< InputName << " contains "<< number_point << " points" << endl;


       double d = p[a].distance(p[b]);

//     Insert your code here to compute the closestpair




        point l(0,0,0);            // test to print two points
        point r(1,1,1);
        cout << myDistance(l,r);   //l=p and r=p2 just renamed to avoid conflict






     cout<< "End of program.";

     out.close();
     getch();
}

[gunnerfunner]

OK, you'll need a few different things to do this program properly:
- setting up the Point struct
- reading the file
- generating all possible combinations of two Point objects from however many Point objects that are in the file and calculating the distance b/w these two Point objects
- finding a way of saving the distance, two Point object pairs such that we can identify the pair of two Point objects with shortest distance

In this reply I'm not focussing on reading the file, assuming you can handle it:
- setting up the Point struct: in the program below the Point struct is set up with an overloaded ctor and there are 2 non-member functions to calculate distance b/w two Point objects and to print Point objects - fairly basic stuff
- generating all possible combinations of two Point objects from however many Point objects that are in the file and calculating the distance b/w the two Point objects: I'm focussing mainly on this bit - suppose you have 10 Point objects in your file, then you'd need to check 10c2 i.e 45 combinations of pairs of Point objects, calculate the distance b/w them and thus identify the two Point objects with the shortest distance. So you'll need:
(a) a function that generates the number of combinations of r from n:
int NchooseR(int n, int r );
(b) and a function that generates each of these actual combinations:
std::vector<std::vector<int>> allCombos (int n, int r );
(c) nice to have but not strictly necessary here is a function to print the results of (b):
void print_combos(const std::vector<std::vector<int>>& result, const int& x, const int& r);
- finding a way of saving the distance, two Point object pairs such that we can identify the pair of two Point objects with shortest distance: for this wer're going to use: std::map<double, std::pair<Point, Point>> distancePoints{}; and this being a map the element corresponding to distancePoints.cbegin() would have the shortest distance b/w two Point objects

Here's the program and a link to a set of sample output:

#include <iostream>
#include <vector>
#include <cmath>
#include <chrono>
#include <random>
#include <numeric>
#include <algorithm>
#include <map>
#include <tuple>

constexpr auto SIZE = 20;

struct Point
{
    double m_x = 0;
    double m_y = 0;
    double m_z = 0;

    Point(){}
    Point (const double& x, const double& y, const double& z)
    : m_x(x), m_y(y), m_z(z) {}
};
double pointDistance(const Point& lhs, const Point& rhs)
{
    return std::pow(lhs.m_x - rhs.m_x, 2) + std::pow(lhs.m_y - rhs.m_y, 2) + std::pow(lhs.m_z - rhs.m_z,2);
    //not math distance definition but monotonic with it and sufficient for here
}
std::ostream& operator << (std::ostream& os, const Point& p)
//for printing point objects
{
    os << "(" << p.m_x << "," << p.m_y << "," << p.m_z << ")";
    return os;
}
int NchooseR(int n, int r ); // number of combinations of r from n;
std::vector<std::vector<int>> allCombos (int n, int r ); // actual combinations of r from n;
void print_combos(const std::vector<std::vector<int>>& result, const int& x, const int& r);//printing actual combinations;


int main()
{
    std::vector<Point> vecPoints{};
    std::mt19937 mt(static_cast<unsigned int>(std::time(NULL)));
    std::uniform_int_distribution<int> dist(-100, 100);

    for (auto i = 0; i < SIZE; ++i )
    {
        vecPoints.push_back(Point(dist(mt), dist(mt), dist(mt)));
        //generating Point objects with random numbers range (-100,100)
    }

    std::map<double, std::pair<Point, Point>> distancePoints{};
    for (const auto& elem : allCombos(SIZE, 2))
    {
        distancePoints[pointDistance(vecPoints[elem[0]], vecPoints[elem[1]])]
            = std::make_pair(vecPoints[elem[0]], vecPoints[elem[1]]);
    //using the std::map constructor, LHS is the distance b/w two Point objects ...
    //RHS is the pair of the corresponding Point objects
    }
    for (auto citr = distancePoints.cbegin(); citr != distancePoints.cend(); ++citr)
    {
        //printing the map
        std::cout << citr -> first << " " << citr -> second.first
                    << " " << citr -> second.second << '\n';
    }
}

int NchooseR(int n, int r )//// number of combinations of r from n;
{
    if (r > n) return 0;
    if (r * 2 > n) r = n-r;
    if (r == 0) return 1;
    int result = n;
    for( int i = 2; i <= r; ++i ) {
        result *= (n-i+1);
        result /= i;
    }
    return result;
}
std::vector<std::vector<int>> allCombos (int n, int r )
{
	int x = NchooseR(n, r);
	std::vector<std::vector<int>> result(x,std::vector<int>(r));
	//2D vector, # inner vectors = number of combinations
	//size of inner vector = 2 (in this case)
	int j {}, k {};
	std::vector<bool> v(n);
    std::fill(v.begin() + n - r, v.end(), true);
    do
    {
        for (int i = 0; i < n; ++i)
        {
            if (v[i])
            {
                result[j][k++] = i + 1;
            }
        }
        k = 0, ++j;
    } while (std::next_permutation(v.begin(), v.end()));
    //some useful links:
    //http://stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation
    //http://stackoverflow.com/questions/12991758/creating-all-possible-k-combinations-of-n-items-in-c
    http://en.cppreference.com/w/cpp/algorithm/next_permutation
    return result;
}
void print_combos(const std::vector<std::vector<int>>& result, const int& x, const int& r)
{
    for (int i = 0; i < x; i++)
    {
        for (int j = 0; j < r; j++)
        {
            std::cout << result[i][j] << " ";
        }
        std::cout << '\n';
    }
}

[b]
Sample Output[b]
http://pasted.co/3d26bd7a

[tit0n]

I already have a file like this I only posted the relevant ones. Doesn't help my question

[jonnin]

you have to read the whole text file into a data structure, then cross compare all the values from the distance against each other.

so youll need to store d: p1,p2, d:p1,p3, d:p1,p4, ... and be careful not to check p1 vs p1 dist = 0.0. You can store them in a vector, or a list, or whatever data structure.

Then if you just want the one lowest point pair, you can keep a running lowest variable set and spit that out at the end.

so to sum all that up..
read file into data structure
compute all distances (about N*N of them.. begs a double for loop)
track the smallest distance as you go.

[gunnerfunner]

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

struct Point
{
    double m_x = 0;
    double m_y = 0;
    double m_z = 0;

    Point(){}
    Point (const double& x, const double& y, const double& z)
    : m_x(x), m_y(y), m_z(z) {}
};
double pointDistance(const Point& lhs, const Point& rhs)
{
    return std::pow(lhs.m_x - rhs.m_x, 2) + std::pow(lhs.m_y - rhs.m_y, 2) + std::pow(lhs.m_z - rhs.m_z,2);
    //not math distance definition but monotonic with it and sufficient for here
}
std::ostream& operator << (std::ostream& os, const Point& p)
//for printing point objects
{
    os << "(" << p.m_x << "," << p.m_y << "," << p.m_z << ")" << '\n';
    return os;
}

const double arr[]={0,1,2,3,4,5,6,7,8,9};

int main()
{
    std::vector<Point> vecPoints{};
    std::ifstream inFile("D:\\input2.txt");

    if(inFile)
    {
        std::string line{};
        while(getline(inFile, line))
        {
            Point temp;
            temp.m_x = arr[line[1] - '0'];
            temp.m_y = arr[line[3] - '0'];
            temp.m_z = arr[line[5] - '0'];
            if(inFile)
            {
                vecPoints.push_back(temp);
            }
        }
    }
    for (const auto& elem : vecPoints)
    {
        std::cout << elem ;
    }

}

Output

(0,0,1)
(0,1,0)
(0,1,1)
(1,0,0)
(1,0,1)
(1,1,0)
(1,1,1)