Convex Hull problem

[Flixter]

#include <iostream>
#include <vector>

using namespace std;

class Pair {
public:
Pair(int a, int b)
{x=a; y=b;};
int get_x()
{return x;};
int get_y()
{return y;};
private:
int x;
int y;};

int main()
{vector<Pair> set;

\\input of the set of points, with 50 points
Pair* a1 = new Pair(70, 64); set.push_back(*a1);
Pair* a2 = new Pair(3, 11); set.push_back(*a2); 
Pair* a3 = new Pair(43, 35); set.push_back(*a3);
Pair* a4 = new Pair(67, 97); set.push_back(*a4);
Pair* a5 = new Pair(95, 71); set.push_back(*a5);
Pair* a6 = new Pair(53, 70); set.push_back(*a6);
Pair* a7 = new Pair(79, 13); set.push_back(*a7);
Pair* a8 = new Pair(53, 66); set.push_back(*a8);
Pair* a9 = new Pair(47, 81); set.push_back(*a9);
Pair* a10 = new Pair(69, 42); set.push_back(*a10);
Pair* a11 = new Pair(66, 96); set.push_back(*a11);
Pair* a12 = new Pair(87, 2); set.push_back(*a12);
Pair* a13 = new Pair(57, 9); set.push_back(*a13);
Pair* a14 = new Pair(74, 41); set.push_back(*a14);
Pair* a15 = new Pair(19, 33); set.push_back(*a15);
Pair* a16 = new Pair(44, 53); set.push_back(*a16);
Pair* a17 = new Pair(32, 85); set.push_back(*a17);
Pair* a18 = new Pair(41, 75); set.push_back(*a18);
Pair* a19 = new Pair(63, 89); set.push_back(*a19);
Pair* a20 = new Pair(47, 20); set.push_back(*a20);
Pair* a21 = new Pair(68, 98); set.push_back(*a21);
Pair* a22 = new Pair(58, 53); set.push_back(*a22); 
Pair* a23 = new Pair(95, 12); set.push_back(*a23);
Pair* a24 = new Pair(51, 80); set.push_back(*a24);
Pair* a25 = new Pair(19, 33); set.push_back(*a25);
Pair* a26 = new Pair(25, 3); set.push_back(*a26);
Pair* a27 = new Pair(78, 5); set.push_back(*a27);
Pair* a28 = new Pair(29, 48); set.push_back(*a28);
Pair* a29 = new Pair(1, 54); set.push_back(*a29);
Pair* a30 = new Pair(45, 6); set.push_back(*a30);
Pair* a31 = new Pair(30, 59); set.push_back(*a31);
Pair* a32 = new Pair(20, 92); set.push_back(*a32);
Pair* a33 = new Pair(80, 80); set.push_back(*a33);
Pair* a34 = new Pair(17, 67); set.push_back(*a34);
Pair* a35 = new Pair(79, 24); set.push_back(*a35);
Pair* a36 = new Pair(10, 84); set.push_back(*a36);
Pair* a37 = new Pair(45, 3); set.push_back(*a37);
Pair* a38 = new Pair(6, 10); set.push_back(*a38);
Pair* a39 = new Pair(12, 16); set.push_back(*a39);
Pair* a40 = new Pair(60, 17); set.push_back(*a40);
Pair* a41 = new Pair(85, 53); set.push_back(*a41);
Pair* a42 = new Pair(70, 36); set.push_back(*a42);
Pair* a43 = new Pair(53, 98); set.push_back(*a43);
Pair* a44 = new Pair(94, 4); set.push_back(*a44);
Pair* a45 = new Pair(46, 48); set.push_back(*a45);
Pair* a46 = new Pair(56, 85); set.push_back(*a46);
Pair* a47 = new Pair(63, 35); set.push_back(*a47);
Pair* a48 = new Pair(41, 56); set.push_back(*a48);
Pair* a49 = new Pair(39, 74); set.push_back(*a49);
Pair* a50 = new Pair(50, 14); set.push_back(*a50);

vector<Pair> hull;

\\checking for every combination of two points wheter they are a part of the convex hull
for (int p=0; p<set.size(); p++){
    for (int q=0; q<set.size(); q++){
\\forming coordinates of the pair of points 
        int px=set[p].get_x(); int py=set[p].get_y();
        int qx=set[q].get_x(); int qy=set[q].get_y();
\\proceed only if the two points are different
        if (!((px==qx) && (py==qy))) {int cnt=0;
\\performing a check for every single point in the set whether it is below 
\\the line formed by the 2 points (this means that the two points are a part of the hull)
                     for (int i=0; i<set.size(); i++){
                         int p2x=set[i].get_x(); int p2y=set[i].get_y();
\\performing a coordinate translation so that the first point is at 0,0
                         px=px-qx; py=py-qy; p2x=p2x-qx; p2y=p2y-qy; qx=0; qy=0;
\\finding the determinant
                         double det = ((px-qx)*(p2y-qy)) - ((p2x-qx)*(py-qy));
\\if the determinant is lower then zero, that means that the point is above the line formed by the 2 points
                         if (det<0) cnt++;}
\\in case all of the points are above the line, the counter cnt will be 50
                         if (cnt==50) {int tcntx=0, tcnty=0;
\\checking if the points are already added to the hull
                                      for (int i=0; i<hull.size(); i++){
                                      int ix=set[i].get_x(); int iy=set[i].get_y(); 
                                      if ((px==ix) && (py==iy)) tcntx++;
                                      if ((qx==ix) && (qy==iy)) tcnty++;}
\\if not we add them
                                      if (tcntx==0) hull.push_back(set[p]); 
                                      if (tcnty==0) hull.push_back(set[q]);}
        }}}
        

\\printing the result        
for (int p=0; p<hull.size(); p++){cout<<"("<<hull[p].get_x()<<", "<<hull[p].get_y()<<")"<<endl;}  

cout<<endl<<hull.size()<<endl;      
  
  
\\check for validity of algorithm, connecting 2 points and counting how many points are below and how many above the line
int x1=1,x2=3,y1=54,y2=10, up=0,down=0;  
   for (int i=0; i<set.size(); i++){
                         int p2x=set[i].get_x(); int p2y=set[i].get_y();
                         x1=x1-x2; y1=y1-y2; p2x=p2x-x2; p2y=p2y-y2; x2=0; y2=0;
                         double det = ((x1-x2)*(p2y-y2)) - ((p2x-x2)*(y1-y2));
                         if (det>=0) down++; else up ++;}                  
                         
                         cout<<endl<<up<<endl<<down<<endl<<up+down<<endl;

system("PAUSE");
return 0;
}

Please take a look at the code, it should find the convex hull of 50 given points. I tried to use a simple approach which algorithm is something like this:
CODE:

1. for all points p in S
2. for all points q in S
3. if p != q
4. draw a line from p to q
5. if all points in S except p and q lie to the left of the line add the directed vector pq to the solution set

I just try to collect the convex hull points and if possible to sort them in order. I have a logical problem in the program, the syntax should be correct and the code is compilable.
Please help if you can, every hint is of great importance.

[Ancient Dragon]

I don't know about the math you described, but the program is wrong

{vector<Pair> set;

\\input of the set of points, with 50 points
Pair* a1 = new Pair(70, 64); set.push_back(*a1);

you don't need all those memory allocations. Its probably causing a huge memory leek and just overcomplicating your program. All you need is a single Pair object, set the values and push onto the vector. Just add a Set() method that takes the same two parameters as the constructor.

{vector<Pair> set;

\\input of the set of points, with 50 points
Pair a1;
a1.set(70,64); set.push_back(a1);
a1.set(3,11); set.push_back(a1);
// etc etc

And you can save yourself a lot more typing by just creating a simple array instead of that vector

int set[][2] = {
    {70,64},
    {3,11},
    {43,35},
    {67,97},
    {95,71}
    // etc, etc
};

[Flixter]

I don't know about the math you described, but the program is wrong

{vector<Pair> set;

\\input of the set of points, with 50 points
Pair* a1 = new Pair(70, 64); set.push_back(*a1);

you don't need all those memory allocations. Its probably causing a huge memory leek and just overcomplicating your program. All you need is a single Pair object, set the values and push onto the vector. Just add a Set() method that takes the same two parameters as the constructor.

{vector<Pair> set;

\\input of the set of points, with 50 points
Pair a1;
a1.set(70,64); set.push_back(a1);
a1.set(3,11); set.push_back(a1);
// etc etc

And you can save yourself a lot more typing by just creating a simple array instead of that vector

int set[][2] = {
    {70,64},
    {3,11},
    {43,35},
    {67,97},
    {95,71}
    // etc, etc
};

Yeah but this didin't helps me .
Someone else to help me ?

[vijayan121]

1. for all points p in S
2. for all points q in S
3. if p != q
4. draw a line from p to q
5. if all points in S except p and q lie to the left of the line add the directed vector pq to the solution set

this does not seem be right. why don't you try it out by hand (paper and pencil) on a small set of 5 or so points?

if you want something simple, take a look at the gift wrapping algorithm (Jarvis march): http://en.wikipedia.org/wiki/Gift_wrapping_algorithm

[Flixter]

Here a made another code

#include <iostream>
#include "math.h"
#include <algorithm>
#include <vector>
using namespace std;

class Point
{
private:
	float x;
	float y;
public:
	// Contructors
	Point();
	Point(float x, float y);
	Point(const Point &copy);

	// Getters and setters
	float GetX();
	void SetX(float x);
	float GetY();
	void SetY(float y);

	// Operators
	Point& operator=(const Point & b);
	bool operator==(Point b);
	bool operator<(Point b);

	// Methods - member functions
	float DistanceBetween(Point & p);

	// Destructors
	~Point();
};


Point::Point()
{
	x = 0;
	y = 0;
}

Point::Point(float x, float y)
{
	this->x = x;
	this->y = y;
}

Point::Point(const Point & copy)
{
	this->x = copy.x;
	this->y = copy.y;
}

float Point::GetX()
{
	return x;
}

void Point::SetX(float x)
{
	this->x = x;
}

float Point::GetY()
{
	return y;
}

void Point::SetY(float y)
{
	this->y = y;
}

Point& Point::operator=(const Point & b)
{
	this->x = b.x;
	this->y = b.y;

	return *this;
}

bool Point::operator==(Point b)
{
	if (this->x == b.x && this->y == b.y)
	{
		return true;
	}
	return false;
}

bool Point::operator<(Point b)
{
	if (this->x < b.x || (this->x == b.x && this->y < b.y))
	{
		return true;
	}
	return false;
}

float Point::DistanceBetween(Point &p)
{
	return sqrt(pow(this->GetX() - p.GetX(), 2) + pow(this->GetY() - p.GetY(), 2));
}

Point::~Point()
{
	// do nothing, because there is nothing to release, no pointers or other objects inside this object
}



// 2D cross product.
// Return a positive value, if OAB makes a counter-clockwise turn,
// negative for clockwise turn, and zero if the points are collinear.
float Cross(Point &O, Point &A, Point &B)
{
	return (A.GetX() - O.GetX()) * (B.GetY() - O.GetY()) - (A.GetY() - O.GetY()) * (B.GetX() - O.GetX());
}

// Implementation of Monotone Chain Convex Hull algorithm.
// Returns a list of points on the convex hull in counter-clockwise order.
// Note: the last point in the returned list is the same as the first one.
vector<Point> ConvexHull(vector<Point> P)
{
	int n = P.size(), k = 0;

	vector<Point> H(2 * n);
 
	// Sort points lexicographically
	sort(P.begin(), P.end());
 
	// Build lower hull
	for (int i = 0; i < n; i++)
	{
		while (k >= 2 && Cross(H[k - 2], H[k - 1], P[i]) <= 0)
			k--;
		H[k++] = P[i];
	}
 
	// Build upper hull
	for (int i = n - 2, t = k + 1; i >= 0; i--)
	{
		while (k >= t && Cross(H[k - 2], H[k - 1], P[i]) <= 0)
			k--;
		H[k++] = P[i];
	}
 
	H.resize(k);
	return H;
}

void PrintPoints(vector<Point> points)
{
	for (vector<Point>::iterator iter = points.begin(); iter != points.end(); iter++)
	{
		cout << "(" << iter->GetX() << ", " << iter->GetY() << ")" << endl;
	}
}

Point Centroid(vector<Point> points)
{
	int n = points.size();
	float sumX, sumY;
	sumX = sumY = 0;

	for (vector<Point>::iterator iter = points.begin(); iter != points.end(); iter++)
	{
		sumX += iter->GetX();
		sumY += iter->GetY();
	}

	return Point(sumX / n, sumY / n);
}

float TriangleArea(Point A, Point B, Point C)
{
	float a = sqrt(pow(C.GetX() - B.GetX(), 2) + pow(C.GetY() - B.GetY(), 2));
	float b = sqrt(pow(A.GetX() - C.GetX(), 2) + pow(A.GetY() - C.GetY(), 2));
	float c = sqrt(pow(B.GetX() - A.GetX(), 2) + pow(B.GetY() - A.GetY(), 2));
	float s = (a + b + c) / 2;

	return sqrt(s * (s - a) * (s - b) * (s - c));
}

float Area(vector<Point> convexHullPoints)
{
	int n = convexHullPoints.size();
	Point centroid = Centroid(convexHullPoints);
	float area = 0;

	for (int i = 0; i < n - 1; i++)
	{
		area += TriangleArea(centroid, convexHullPoints[i], convexHullPoints[i + 1]);
	}
	return area;
}

void main()
{
	vector<Point> allPoints;
	allPoints.push_back(Point(67, 41));
	allPoints.push_back(Point(0, 34));
	allPoints.push_back(Point(24, 69));
	allPoints.push_back(Point(58, 78));
	allPoints.push_back(Point(64, 62));
	allPoints.push_back(Point(45, 5));
	allPoints.push_back(Point(27, 81));
	allPoints.push_back(Point(91, 61));
	allPoints.push_back(Point(42, 95));
	allPoints.push_back(Point(36, 27));
	allPoints.push_back(Point(4, 91));
	allPoints.push_back(Point(53, 2));
	allPoints.push_back(Point(82, 92));
	allPoints.push_back(Point(16, 21));
	allPoints.push_back(Point(95, 18));
	allPoints.push_back(Point(26, 47));
	allPoints.push_back(Point(38, 71));
	allPoints.push_back(Point(12, 69));
	allPoints.push_back(Point(99, 67));
	allPoints.push_back(Point(94, 35));
	allPoints.push_back(Point(11, 3));
	allPoints.push_back(Point(33, 22));
	allPoints.push_back(Point(64, 73));
	allPoints.push_back(Point(11, 41));
	allPoints.push_back(Point(68, 53));
	allPoints.push_back(Point(44, 47));
	allPoints.push_back(Point(57, 62));
	allPoints.push_back(Point(59, 37));
	allPoints.push_back(Point(41, 23));
	allPoints.push_back(Point(78, 29));
	allPoints.push_back(Point(35, 16));
	allPoints.push_back(Point(42, 90));
	allPoints.push_back(Point(6, 88));
	allPoints.push_back(Point(42, 40));
	allPoints.push_back(Point(48, 64));
	allPoints.push_back(Point(5, 46));
	allPoints.push_back(Point(29, 90));
	allPoints.push_back(Point(50, 70));
	allPoints.push_back(Point(1, 6));
	allPoints.push_back(Point(48,93));
	allPoints.push_back(Point(23, 29));
	allPoints.push_back(Point(54, 84));
	allPoints.push_back(Point(40, 56));
	allPoints.push_back(Point(76, 66));
	allPoints.push_back(Point(8, 31));
	allPoints.push_back(Point(39, 44));
	allPoints.push_back(Point(23, 26));
	allPoints.push_back(Point(38, 37));
	allPoints.push_back(Point(82, 18));
	allPoints.push_back(Point(41, 29));

	vector<Point> convexHullPoints = ConvexHull(allPoints);
	PrintPoints(convexHullPoints);

	cout << "The area of the convex hull amounts: " << Area(convexHullPoints) << endl;
}

But here

void main()
{
vector<Point> allPoints;....
...

give me error message :S
Can someone help me?

[VernonDozier]

But here

void main()
{
vector<Point> allPoints;....
...

give me error message :S
Can someone help me?

That's not the problem. You can comment out your entire main function and you'll still get an error. If you comment out this line:

sort(P.begin(), P.end());

your program should compile. The program is complaining about const modifiers. I think you need to go through your program and take a few of the const modifiers out, or at least one of them. I haven't debugged it completely, but removing at least one of them seemed to get it to compile a little farther.

[William Hemsworth]

This might not help with your exact problem, but don't use void main() as Salem's avatar will clearly show you :)

[Flixter]

No I still can't solve the proble :S