Help with Program to Compare distance of (x,y) coordinates

[aiiight]

http://ideone.com/Buum6a


So the goal of the program is to allow for the user to enter as many points as they want, and the program should print out the closest two and their distance. All I have right now is code that lets the user enter the points, and the points get stored into the vector. I am completely lost on how I should go about comparing all of the points, especially since we don't know how many the user will enter.


I tried making a PointPair class to hold references for two points, but I am unsure how that would help me. If anybody had any guidance on where I should move going from here, I would greatly appreciate it.

Thank you!

#include<iostream>
#include<vector>
using namespace std;

class Point
{
public:
	Point()
	{
		x = 0;
		y = 0;
	}
	Point(double x, double y)
	{
		this->x = x;
		this->y = y;
	}
	double getX()
	{
		return x;
	}
	double getY()
	{
		return y;
	}
	void setX(double x)
	{
		this->x = x;
	}
	void setY(double y)
	{
		this->y = y;
	}
private:
	double x;
	double y;
};

class PointPair : public Point
{
public:
	PointPair()
	{
		p1 = 0;
		p2 = 0;
		dist = 0;
	}
	Point * p1()
	{
		return p1;
	}
	Point * p2()
	{
		return p2;
	}
	void setP1(Point * p)
	{
		p1 = p;
	}
	void setP2(Point * p)
	{
		p2 = p;
	}
	void setDistance(double d)
	{
		dist = d;
	}
private:
	Point* p1;
	Point* p2;
	double dist;
};

int main()
{
	double x;
	double y;
//	int count = 0;
	vector<Point> plotPoints;
	
	do
	{
		cout << "Enter (x,y) Coordinates ((-1, -1) to stop): ";
		cin >> x >> y;
		cout << x  << " " << y << endl;
		if ((x == -1) || (y == -1))
		{
			cout << "-1 -1 Entered. Calculating closest points..." << endl;
			break;
		}
		else
		{
			plotPoints.push_back(Point(x, y));
		}

	} while (x != -1 || y != -1);


	cout << plotPoints.size() << " number of points entered. "<< endl;


	system("pause");
}

[keskiverto]

we don't know how many the user will enter.

But you do. You clearly do know on line 99.

Discard the PointPair. You only need one pair of integers to index the closest pair.

 ABCDE
A
B.
C..
D...
E....

The A-E are 5 points. The dots indicate pairs that you have to compute a distance for.

Two loops (nested) over the vector is enough to do the computations. On each case the distance is either less than previous nearest or not. If less, then update the pair.

You do not need to compute the actual distances within the loop; their squares are sufficient, because:

a^2 < b^2
=>
a < b

Show the actual distance for the result.

[gunnerfunner]

Define the (Euclidean) distance fn b/w 2 pts and use std::map<double, std::pair<Point,Point>> where the map's key is the distance b/w the pair of points:

#include <iostream>
#include <cmath>
#include <vector>
#include <tuple>
#include <map>
using std::cin;
using std::cout;

class Point
{
public:
	Point() : _x(0), _y(0){}

	Point(const double& x, const double& y) : _x(x), _y(y) {}

	double getX() const {return _x;}

	double getY() const {return _y;}

	void setX(const double& x) { _x = x;}

	void setY(const double& y)  {_y = y;}
	friend std::ostream& operator << (std::ostream& os, const Point& p);

private:
	double _x;
	double _y;
};
double distance (const Point& lhs, const Point& rhs);

int main()
{
	std::vector<Point> Points;
	std::map<double, std::pair<Point, Point>> myMap;
    double x;
    double y;
	do
	{
		cout << "Enter (x,y) Coordinates ((-1, -1) to stop): ";

		cin >> x >> y;
		cout << x  << " " << y << '\n';
		if ((x == -1) || (y == -1))
		{
			cout << "-1 -1 Entered. \nCalculating Distance and closest points..." << '\n';
			break;
		}
		else
		{
			Point temp;
            temp.setX(x);
            temp.setY(y);
			Points.push_back(temp);
		}

	} while (x != -1 || y != -1);
	for (size_t i = 0; i < Points.size(); ++i)
    {
        for (size_t j = i + 1; j < Points.size(); ++j)
        {
            myMap[distance(Points[i], Points[j])] = std::make_pair(Points[i], Points[j]);
        }
    }

    auto itr = myMap.begin();

    std::cout << itr -> first << " " << itr ->second.first << " " << itr -> second.second << '\n';
}
double distance (const Point& lhs, const Point& rhs)
{
    return pow(std::pow(lhs.getX() - rhs.getX(), 2) + std::pow(lhs.getY() - rhs.getY(), 2), 0.5);
}
std::ostream& operator << (std::ostream& os, const Point& p)
{
    os << "(" << p._x << ", " << p._y << ")" << " ";
    return os;
}

PS: you may wish to change your break condition for data entry, o/wise (-1, -1) can never be entered as a Point

[aiiight]

keskiverto, I think I get the gist of what you are saying but am confused as to why the loop would be nested - wouldn't I just need one loop (for int i = 0; i < plotPoints.size(); i++)? And inside that loop I would create a Temp point, compare the first to the second, to the third, etc..


Also, if I want to print the points and their distance from each other, how would I print the two closest points to the console? Wouldn't the distance only be stored?


Thank you - I appreciate it!(First time using vectors, excuse my ignorance)

[keskiverto]

Nested loops. I have a string here, but a string is very much like a vector of characters:

#include <iostream>
#include <string>

int main() {
  std::string foo = "ABCDE";
  if ( 1 < foo.size() ) {
    for ( size_t first = 0; first < foo.size(); ++first ) {
      for ( size_t other = first + 1; other < foo.size(); ++other ) {
        std::cout << foo[first] << " vs " << foo[other] << '\n';
      }
    }
  }
  return 0;
}

Does it print all unique pairs of characters, just like you should test all unique pairs of points?


Store two integers, for example "bestFirst" and "bestOther".

After the loops the plotPoints[bestFirst] and plotPoints[bestOther] should be the pair of points that you are looking for.


Have you done/seen a "find largest value in array" problem?

[aiiight]

I have done a problem like that, that seems easy in comparison to this =[


Here is what I have now.. I followed your nested loop and figured I'd have to overload the operator to cout the values.

#include<iostream>
#include<vector>
#include<sstream>
#include<string>
using namespace std;

class Point
{
public:
	Point()
	{
		x = 0;
		y = 0;
	}
	Point(double x, double y)
	{
		this->x = x;
		this->y = y;
	}
	double getX()
	{
		return x;
	}
	double getY()
	{
		return y;
	}
	void setX(double x)
	{
		this->x = x;
	}
	void setY(double y)
	{
		this->y = y;
	}
	friend ostream & operator << (ostream & out, const Point & p)
	{
		out << p.toString();
		return out;

	}
	void toString() const
	{
		cout << x << ", " << y << endl;
	}
private:
	double x;
	double y;
};

int main()
{
	double x;
	double y;
	int bestX, bestY;
//	int count = 0;
	vector<Point> plotPoints;
	
	do
	{
		cout << "Enter (x,y) Coordinates ((-1, -1) to stop): ";
		cin >> x >> y;
		cout << x  << " " << y << endl;
		if ((x == -1) || (y == -1))
		{
			cout << "-1 -1 Entered. Calculating closest points..." << endl;
			break;
		}
		else
		{
			plotPoints.push_back(Point(x, y));
		}

	} while (x != -1 || y != -1);


	cout << plotPoints.size() << " number of points entered. "<< endl;

	if (1 < plotPoints.size())
	{
		for (int i = 0; i < plotPoints.size(); i++)
		{
			for (int j = 1; j < plotPoints.size(); j++)
			{
				cout << plotPoints[i] << " vs " << plotPoints[j] << '\n';
			}
		}
	}


	system("pause");
}

However, I get compiler errors on lines 38, 81, and 83 - not sure why I get '<': signed mismatch

Thank you again.

[keskiverto]

What does happen on line 38?

You do write the value returned by function toString() into a stream. What value does toString() return? (Hint: Look at line 42.)


The operator<< does not need to be a friend.

Why whouldn't a standalone function like this work?

std::ostream & operator<< ( std::ostream & out, const Point & p )
{
  out << p.getX() << ", " << p.getY();
  return out;
}

Do the getX() and getY() change a Point? What is the meaning of word "const" on line 42?

signed mismatch

What is the type of 'j'? int
What is the type of plotPoints.size()? What does the documentation of vector say?

Lines 81 and 83 are warnings, not errors.
You could use size_t as the type of i and j.