graham scan

#include <iostream>
#include <list>
#include <vector>
#include <stack>
#include <string>
// basic file operations
#include <iostream>
#include <sstream>
#include <fstream>
#include <time.h>

using namespace std;
//,

void readFile();

struct point {   // Declare point struct type
   long double x;   // Declare member types
   long double y;
};
        int leftPtIndex = -1;
        long double leftMostPtX = 0;
        long double leftMostPtY = 0;

int totalPoints;
int jarvismarch(point *, int *);
int *grahamscan(point *pointList, int *outputOrderList,int totalPoints);
int pickleftmostpoint(point *pointList);

bool compareSlope( point p1, point p2 ) 
{
  return (p1.y-leftMostPtY)/(p1.x-leftMostPtX)<(p2.y-leftMostPtY)/(p2.x-leftMostPtX);
};

void Tokenize(const string& str,
                      vector<string>& tokens,
                      const string& delimiters = " ")
{
    // Skip delimiters at beginning.
    string::size_type lastPos = str.find_first_not_of(delimiters, 0);
    // Find first "non-delimiter".
    string::size_type pos     = str.find_first_of(delimiters, lastPos);

    while (string::npos != pos || string::npos != lastPos)
    {
        // Found a token, add it to the vector.
        tokens.push_back(str.substr(lastPos, pos - lastPos));
        // Skip delimiters.  Note the "not_of"
        lastPos = str.find_first_not_of(delimiters, pos);
        // Find next "non-delimiter"
        pos = str.find_first_of(delimiters, lastPos);
    }
}
bool stringToInt(const string &s, int &i)
{
  istringstream myStream(s);
  if (myStream>>i)
    return true;
  else
    return false;
}

bool stringToDouble(const string &s, double &i)
{
  istringstream myStream(s);
  if (myStream>>i)
    return true;
  else
    return false;
}

int readNodeFile (string fileName, point pointList[]) {
  int totalPoints;
  string line;
  ifstream myfile(fileName.c_str());
        int points = -1;
  if (myfile.is_open())
  {

        vector<string> lineTokens;
        int i;
    while (! myfile.eof() )
    {
        //line = "";
        getline (myfile,line);
        //cout << line << " - "<< points <<endl;
        if(points == -1)
        {

                if(!stringToInt(line, totalPoints))
                {
                        cout << "going to throw exception" << points <<endl;
                        throw "exception not a number";
                }
        }
        else{
                if(points>totalPoints-1)
                        break;
                lineTokens.clear();
                Tokenize(line, lineTokens, "\t");
                for(i=0;i<3;i++)
                {
                        //stringToDouble(lineTokens[1], pointList[points].x);
                        //stringToDouble(lineTokens[2], pointList[points].y);
                        pointList[points].x = atof(lineTokens[1].c_str());
                        pointList[points].y = atof(lineTokens[2].c_str());                        

                }
                        //cout << " pointList["<< points <<"].y ="<< pointList[points].y <<endl;
                //cout << " - "<< points <<endl;
        }
        points++;
    }
    myfile.close();
  }
  else cout << "Unable to open file"; 

  return points;
}

int main()
{               
 time_t seconds;

//  seconds = time (NULL);
clock_t endwait;


        totalPoints = 7;
        point pointList[10000];
        totalPoints = readNodeFile("r10000.node",pointList);
        
        //point pointList[totalPoints];

        
//        cout << " points: "<< totalPoints << endl;
        //for(int i=0; i<totalPoints;i++)
        //        cout << pointList[i].x << "," << pointList[i].y << endl; 

        int outputOrderList[totalPoints];
      grahamscan(&pointList[0], &outputOrderList[0], totalPoints);


        
//    int chpts = jarvismarch(&pointList[0], &outputOrderList[0]);
//     cout << "convex hull points"  << endl;
//      for(int i=0; i<chpts;i++)
//                cout << pointList[outputOrderList[i]].x << "," << pointList[outputOrderList[i]].y << endl; 
//double clocks = clock()/CLOCKS_PER_SEC;
  cout  << "clock tics elapsed since program ran: " <<  clock() << endl;
  cout << "CLOCKS_PER_SEC: " << CLOCKS_PER_SEC << endl;

        return 0;    
}

// | px py 1 |
// | qx qy 1 | = |px-rx py-ry|
// | rx ry 1 |   |qx-rx qy-ry|

long double orientationTest(struct point *p,struct point *q,struct point *r)
{
        //cout << "|"  << p->x  << p->y  << "1 |" << endl;
        //cout << "|"  << q->x  << q->y  << "1 |" << endl;
        //cout << "|"  << r->x  << r->y  << "1 |" << endl;
        //cout <<  "Orientation Test Result:" << (p->x - r->x)*(q->y - r->y) - (p->y - r->y)*(q->x - r->x) << endl;
        return (p->x - r->x)*(q->y - r->y) - (p->y - r->y)*(q->x - r->x);
}

int jarvismarch(point *pointList, int *outputOrderList)
{
        int leftPtIndex = pickleftmostpoint(pointList);
        //cout << "left most point is:" << pointList[leftPtIndex].x << "-" << pointList[leftPtIndex].y << endl;
        outputOrderList[0] = leftPtIndex;
        //cout << "first point is:" << pointList[leftPtIndex].x << "," << pointList[leftPtIndex].y << endl;
        int i;
        for(i=1;;)
        {
                int tempRightPtIndex =-1;
                //finding the next right point
                for(int j=0;j<totalPoints;j++)
                {
                        if(j==outputOrderList[i-1])
                        {
                                continue;
                        }
                        if(tempRightPtIndex==-1)
                        {
                                tempRightPtIndex = j;
                                continue;
                        }
                        //cout << "Orientation test between:" << outputOrderList[i-1] << ", " << tempRightPtIndex << " and " << j << endl;
                        if(orientationTest(&pointList[outputOrderList[i-1]], &pointList[tempRightPtIndex], &pointList[j]) <= 0)
                        {
                                       //swap points
                                        tempRightPtIndex = j;
                        }
                        
                }
                outputOrderList[i] = tempRightPtIndex;
                //cout << "Next point is:" << pointList[tempRightPtIndex].x << "," << pointList[tempRightPtIndex].y << endl;
                if (outputOrderList[i]==outputOrderList[0])
                {
                        break;
                }
                i++;
        }
        //return outputOrderList;
        return i;
}

//returns index of the left most point.
int pickleftmostpoint(point *pointList)
{
        int leftPtIndex = 0;
        long double leftPtValue = pointList[0].x;
        long double leftPtYValue = pointList[0].y;
        for(int i=1;i<totalPoints;i++)
        {
               if (pointList[i].x <= leftPtValue)
                {       if(pointList[i].x == leftPtValue) // picking the lowest point among points on the same verticle line.
                        {
                                if (leftPtYValue>pointList[i].y)
                                {
                                        leftPtIndex = i;
                                        leftPtValue = pointList[i].x;
                                        leftPtYValue = pointList[i].y;
                                }   
                        }
                        else
                        {
                                leftPtIndex = i;
                                leftPtValue = pointList[i].x;
                                leftPtYValue = pointList[i].y;
                        }       
                }
        }
        return leftPtIndex;
};

int *grahamscan(point *pointList, int *outputOrderList,int totalPoints)
{ 
        vector<point> structVector;
        vector<int>::iterator it;
        leftPtIndex = pickleftmostpoint(pointList);
        leftMostPtX = pointList[leftPtIndex].x;
        leftMostPtY = pointList[leftPtIndex].y;
        cout << "left most point is:" << pointList[leftPtIndex].x << "-" << pointList[leftPtIndex].y << endl;
        for(int j=0; j<totalPoints;j++)
                structVector.push_back(pointList[j]);

        sort(structVector.begin(), structVector.end(), compareSlope);
        structVector.insert(structVector.begin(), pointList[leftPtIndex]);
        cout << "size of structVector: " << (int) structVector.size() << endl;
        stack<point> ptStack;  // empty stack using vector
        //stack<point,vector<point> > ptStack ;//(structVector);
        //for (int it=0; it< totalPoints; it++)
        //{
        //   cout << structVector[it].x << "," << structVector[it].y << endl;
        //    ptStack.push(structVector[it]);
        //    cout << ptStack.top();
        //}
        cout << "size of ptStack: " << (int) ptStack.size() << endl;
        point *coin1, *coin2, *coin3;
        vector<point>::iterator pt;
        pt = structVector.begin();
        
        ptStack.push(*pt);
        coin1 = &ptStack.top();

        ptStack.push(*(++pt));
        coin2 = &ptStack.top();
        //coin2 = *(++pt);
        //ptStack.push(coin2);

        ++pt;
        point tempCoin;
        while(pt < structVector.end())
        {
                coin3 = &*(pt);
                if(orientationTest(coin1, coin2, coin3) <= 0)
                {
                        //delete coin2
                        ptStack.pop();
                        tempCoin = ptStack.top();
                        ptStack.pop();
                        coin1 = &ptStack.top();
                        ptStack.push(tempCoin);
                        coin2 = &ptStack.top();
                        //coin
                }
                else
                {
                        coin1 = coin2;
                        ptStack.push(*pt);
                        coin2 = &ptStack.top();
                        pt++;       
                }
                //point *con = (point*)(void *)ptStack.pop();
                //coin = (point *)(void *)ptStack.pop();
                //cout << "coin is : " << ptStack.top()->x << endl;
                //coin3 = ptStack.pop();
        }
        
        cout << "size of ptStack: " << (int) ptStack.size() << endl;      
        while(!ptStack.empty())
        {
                tempCoin = ptStack.top();
                cout << tempCoin.x << "," << tempCoin.y << endl;
                ptStack.pop();
        }

        return outputOrderList;
};