Convex hull algorithm

Main Mirror Site http://www.jdxyw.com/?p=767

In computational geometry, a basic problem is finding the convex hull for a given finite nonempty set of points in the plane. You will meet this problem in Collision detection,Visual pattern matching,Mapping,image processing, statistics and GIS. For the definition about the convex hull,you can refer the page on the wikipedia.

There are already a lot of algorithms to construct a convex hull from a given finite set of points in a plan, such as Jarvis march, Graham scan, Divide and conquer, Optimal output-sensitive algorithms . Here I will use the Graham scan published in 1972 (O(n log n) time complexity). If the points are already sorted by one of the coordinates or by the angle to a fixed vector, then the algorithm takes O(n) time.

When I am learning the algorithms about the convex hull, I found an excellent article written by Mark  Nelson. I would use some materials from that article.

Process of the Graham scan algorithm (Refer to Mark Nelson's article)
Sort all points in S based on their position on the X axis
Designate point left as the leftmost point
Designate point right as the rightmost point
Remove left and right from S
While there are still points in S
remove Point from S
if Point is above the line from left to right
add Point to the end of array upper
else
add Point to the end of array lower

Add left to lower_hull
While lower is not empty
add lower[0] to the end of lower_hull
remove lower[0] from lower
while size(lower_hull >= 3 and the last 3 points lower_hull are not convex
remove the next to last element from lower_hull

Add left to upper_hull
While upper is not empty
add upper[0] to the end of upper_hull
remove upper[0] from upper
while size(upper_hull >= 3 and the last 3 points upper_hull are not convex
remove the next to last element from upper_hull
Merge upper_hull and lower_hull to form hull
return hull

Below is my implementation for constructing a convex bull. I get all the lower hull points and upper hull points. But I does not merge them.

class Point
{
public:
    Point(int _x,int _y)
        :x(_x),y(_y)
    {}
    int x,y;

    friend bool operator<(const Point &p1,const Point &p2)
    {
        return p1.x
<0)
            return true;
    else
        return false;
}

bool pointLowerLine(Point p1,Point p2,Point p3)
{
    int deltaX=p3.x-p1.x;
    int deltaY=p3.y-p1.y;

    if(((deltaY/deltaX)*(p2.x-p1.x)+(p1.y-p2.y))>0)
            return true;
    else
        return false;
}

int _tmain(int argc, _TCHAR* argv[])
{
    ifstream in(".\\data.txt");

    int numPoint;
    in>>numPoint;
    vector points;
    for(int i=0;i>x>>y;
        points.push_back(Point(x,y));
    }
    in.close();
    sort(points.begin(),points.end());

    Point minPoint=points.front();
    Point maxPoint=points.back();

    vector upperPoint;
    vector lowerPoint;
    vector upperHull;
    vector lowerHull;

    int deltaX=maxPoint.x-minPoint.x;
    int deltaY=maxPoint.y-minPoint.y;

    for(int i=1;i<0)
            upperPoint.push_back(p);
        else if(((deltaY/deltaX)*(p.x-minPoint.x)+(minPoint.y-p.y))>0)
            lowerPoint.push_back(p);
    }

    upperPoint.push_back(maxPoint);
    lowerPoint.push_back(maxPoint);

    upperHull.push_back(minPoint);
    lowerHull.push_back(minPoint);

    for(int i=0;i=3 && pointLowerLine(upperHull[size-3],upperHull[size-2],upperHull[size-1]))
        {
            vector::iterator it=upperHull.begin();
            it+=(size-2);
            upperHull.erase(it);
            size=upperHull.size();
        }
    }

    for(int i=0;i=3 && pointUpperLine(lowerHull[size-3],lowerHull[size-2],lowerHull[size-1]))
        {
            vector::iterator it=lowerHull.begin();
            it+=(size-2);
            lowerHull.erase(it);
            size=lowerHull.size();
        }
    }

    system("pause");
    return 0;
}