Unexpected behaviour of convex hull algorithm

Question

I was trying to implement the algorithm to get the convex hull for a given set of points and visualise the result using opencv using the following code on c++:

#include "opencv2/opencv.hpp"
#include "StdAfx.h"
#include <vector>
#include <cv.h>
#include <cv.hpp>
#include <cxcore.h>
#include <highgui.h>
#include <iostream>
#include <utility>
#include <math.h>
#include <time.h>  
#include <algorithm>
#include <stack>
using namespace std; 
using namespace cv;

vector<pair<int,int> > testPoints;
pair<int , int> pivot;
stack< pair<int , int> > hull;
const int frameSize=600;
const double PI = 3.141592653589793238462;
vector< pair <int,int> > points;
Mat img=Mat::zeros(frameSize,frameSize, CV_8UC1);

void drawFilledCircle( Mat img, Point center ,int radius)
{
 int thickness = -1;
 int lineType = 8;

 circle( img,
     center,
     radius,
     255,
     thickness,
     lineType );
}

void drawLine( Mat img, Point start, Point end ,int shade,int thickness)
{
  int lineType = 8;
  shade=shade%256;
  line( img,
    start,
    end,
    shade,
    thickness,
    lineType );
}

float getAngle(pair<int,int> p1 , pair<int,int>p2){
     return atan2(static_cast<double>(p1.second-p2.second) , static_cast<double>       (p1.first-p2.first))*180/PI;
}

bool compareFunction(pair<int,int> p1 , pair<int,int> p2){
    return ( getAngle(p1,pivot)>getAngle(p2,pivot) );
}

void printPoints(vector< pair<int,int> > points){
    for(int i=0;i<points.size();i++)
            cout<<"( "<<(points[i].first-frameSize/2)<<" , "<<(points[i].second-    frameSize/2)<<" )  "<<getAngle(points[i],pivot)<<endl;
     cout<<endl;
}

void mouseEvent(int evt, int x, int y, int flags, void* param){
    if(evt==CV_EVENT_LBUTTONDOWN){
        cout<<"Click at : ( "<<(x-frameSize/2)<<" , "<<(y-frameSize/2)<<" ) , Polar Angle: "<<getAngle(make_pair(x,y),pivot)<<endl;
    }
}

void setUpFrame(){
    int n;
    cout<<"Enter number of points: ";
    cin>>n;

    for(int i=0;i<n;i++)
        points.push_back(make_pair((rand()%static_cast<int>(frameSize*0.75)     +frameSize*0.125) , (rand()%static_cast<int>(frameSize*0.75)  +frameSize*0.125)));

    for(int i=0;i<n;i++)
        drawFilledCircle( img, Point(points[i].first, points[i].second) ,2);
    drawLine(img , Point(frameSize/2,0) , Point(frameSize/2,frameSize),100,1);
    drawLine(img , Point(0,frameSize/2) , Point(frameSize,frameSize/2),100,1);

    cout<<"Settingup frame...\nPress enter to continue."<<endl;
}

void setPivot(){
    int max=-2*frameSize , index=0;
    for(int i=0;i<points.size();i++){
        if(points[i].second>max){
            max=points[i].second;
            index=i;
        }
    }
    pivot=points[index];
    points.erase(points.begin()+index);

    drawFilledCircle( img, Point(pivot.first, pivot.second) ,6);
    cout<<"Pivot chosen at: ( "<<(pivot.first-frameSize/2)<<" , "<<(pivot.second-    frameSize/2)<<" )\nPress enter to continue."<<endl;
}

void sortPoints(){
    cout<<"Sorting points on the basis of polar angles."<<endl;
    std::sort(points.begin(),points.end(),compareFunction);
}

void createHull(){
    pair<int,int> previous,next;
    for(int i=0;i<points.size();i++){
        previous= (hull.size()==0) ? pivot : hull.top();
        next= (i==points.size()-1) ? pivot : points[i+1];

        int x1=(previous.first-points[i].first);
        int x2=(points[i].first-next.first);
        int y1=(previous.second-points[i].second);
        int y2=(points[i].second-next.second);

        if( x1*y2-x2*y1 <0 ) 
                hull.push(points[i]);
        drawFilledCircle( img, Point(hull.top().first, hull.top().second) ,4);
    }

    int size=hull.size();
    pair<int,int> pt;

 drawLine(img,Point(pivot.first,pivot.second),Point(hull.top().first,hull.top().second),200,1);
    for(int i=1;i<size;i++){
        pt=hull.top();
        hull.pop();
        drawLine(img,Point(pt.first,pt.second),Point(hull.top().first,hull.top().second),200,1);
    }
    drawLine(img,Point(pivot.first,pivot.second),Point(hull.top().first,hull.top().second),200,    1);
}

int main(int, char**)
{
    srand (time(NULL));
    namedWindow("Output",1);
    cvSetMouseCallback("Output", mouseEvent, 0);

    setUpFrame();
    setPivot();
    sortPoints();
    createHull();

    imshow("Output", img);
    waitKey(0);
    return 0;
}

I know there are inbuilt libraries to do this, but I wanted to implement the algorithm myself. Things seem to work well when the number of points is less, for instance for 30 points but I start to get a weird shape as the number of points increases (like those shown below for 200 and 1000). The algorithm seems to select extra points (points that should not be included in the hull) amongst those lying diagonally opposite to the pivot point (indicated by the filled circle with maximum radius). Can anyone please help me figure out where I went wrong or suggest some modification that I can make in the code? enter image description here

enter image description here

tmyklebu tmyklebu · Accepted Answer · 2013-05-22T13:42:33

It looks like you wanted to implement Graham's scan, but you did so unsuccessfully.

Graham's scan is structured like this:

Find the bottom-most point, then sort the points clockwise around it.
Set hull to the first two points.
For each point, say p, from the third onward:
  While you make a left turn from the last edge of hull to the line from hull.back to p:
    popback(hull);
  push(hull, p)

Note the difference in initialisation --- Graham's scan starts with an edge, while you start with no points.

Note also the difference inside the loop --- you used the left turn criterion as some kind of rejection test that involved another point from points, while Graham's scan uses the new point to remove points that are no longer part of the hull.

Unexpected behaviour of convex hull algorithm

1 Answers