Jarvis's March Convex Hull

Question

I'm more concerned about the coding best practices and how it's written here than the actual algorithm and math. I'm concerned about stack constraints, passing arguments,..etc. If there is anything critically wrong in the way the code is written - I would really appreciate comments!

#include <iostream>
#include <vector>
#include <math.h>

using namespace std;

struct point{
    float x, y;
    point(){
        x=0; y=0;
    }
    point(float aX, float aY){
        x = aX; y = aY;
    }
};

float computePolarAngle(point convex_pt, point candidate_pt){
    //move origin to convex_pt
    float candidate_x = candidate_pt.x - convex_pt.x;
    float candidate_y = candidate_pt.y - convex_pt.y;
    float angle = (180/M_PI)*atan2(candidate_y,candidate_x);

    //incase the angle goes into the negative we always want to find the counterclockwise 
    //angle from x-axis centered at the selected point
    if(angle<0){
        angle = 360+angle;
    }
    return angle;
}

//implementation of Jarvis's March ("Gift Wrapping")
void convexHull(const vector<point>& points, vector<point>& convex_points, vector<int>& convex_points_indices){

    //checks
    if(points.size() <= 2){
        cout<<"points should consist of more than 2 points"<<endl;
    }

    cout<<"******************* points: *******************"<<endl;
    for(int index=0; index<int(points.size()) ; index++){
        cout<<(points.at(index)).x<<","<<(points.at(index)).y<<endl;//.x<<","<<points[index].y<<endl;
    }

    //compute lowest point (min y-coord)
    point lowestPt(points.at(0).x, points.at(0).y);
    int lowestIndex = -1;
    for(int index=0; index < int(points.size()) ; index++){
        if(points.at(index).y < lowestPt.y)
        {
            lowestPt.x = points.at(index).x;
            lowestPt.y = points.at(index).y;
            lowestIndex = index;
        }
    }

    //add lowest point to convex hull
    convex_points.push_back(points.at(lowestIndex));
    convex_points_indices.push_back(lowestIndex);

    //store remaining points (initially same as points) -> deep copy
    vector<point> remaining_points = points;

    //gift wrapping part loop while we have not reached the starting convex point again
    point convex_pt(lowestPt.x, lowestPt.y);
    bool flag_complete = false;
    float eps = 1e-10;

    while(!flag_complete){
        //compute polar angles of all points
        float minIndex = -1;
        float minAngle = 360;
        for(int index=0; index < int(remaining_points.size()) ; index++){

            float polarAngle = computePolarAngle(convex_pt, remaining_points.at(index));
            if(polarAngle < minAngle && polarAngle!=0){//second condition is so that we dont compare a point with itself
                minAngle = polarAngle;
                minIndex = index;
            }
        }

        bool flagX = fabs(lowestPt.x - remaining_points.at(minIndex).x)<eps;
        bool flagY = fabs(lowestPt.y - remaining_points.at(minIndex).y)<eps;

        if(flagX && flagY){
            flag_complete = true;
            continue;
        }
        else{
            convex_points.push_back(remaining_points.at(minIndex));
            convex_points_indices.push_back(minIndex);
            convex_pt.x = remaining_points.at(minIndex).x;
            convex_pt.y = remaining_points.at(minIndex).y;
            remaining_points.erase(remaining_points.begin()+minIndex);
        }
    }

    cout<<"******************* convex hull: *******************"<<endl;
    cout<<"found "<<convex_points.size()<<" points as the convex hull:"<<endl;
    for(auto it = convex_points.begin() ; it!=convex_points.end() ; it++){
        cout<<(*it).x<<", "<<(*it).y<<endl;
    }
}

int main(){

    //example set of points where the convex hull should be the 4 corners (a slightly deformed square)
    vector<point> points;
    points.push_back(point(1,1));
    points.push_back(point(1.1,-1));
    points.push_back(point(-1, 1));
    points.push_back(point(-1.1,-1.1));
    points.push_back(point(0.75,0.5));
    points.push_back(point(-0.5,0.3));
    points.push_back(point(0.25,-0.8));
    points.push_back(point(0.1,-0.9));

    vector<point> convex_points; 
    vector<int> convex_points_indices;

    convexHull(points, convex_points, convex_points_indices);
}

Answer 1

General C++ advice

There's a few general suggestions here that are for the most part independent of your algorithms.

using namespace std

using namespace std;

This is usually a code smell, generally speaking the only time you would really want to do this is when you are making some small throwaway program for testing a concept or making an example (or similar).

In that case the reduction in typing time actually has a positive ROI. But you don't want to do it in any production code because this pollutes the global namespace which is something you should try to avoid, any benefit from time saved typing is immediately wiped out the first time your program breaks because a name conflict.

See this Stack Overflow question for more info on that.

If the main purpose for doing this is to cut down typing std:: then you can selectively bring in just the names you need by doing:

using std::cout;
using std::cin;

an so on. This cuts down on typing without the downside of polluting the global namespace.

Prefer initialization list

In this code you are using assignment to initialize members:

struct point{
    float x, y;
    point(){
        x=0; y=0;
    }
    point(float aX, float aY){
        x = aX; y = aY;
    }
};

However using the member initializer list is usually a better way of initializing variables with the constructor.

struct point{
    float x, y;
    point():
        x(0),
        y(0)
    {
    }
    point(float aX, float aY):
        x(aX),
        y(aY)
    {
    }
}; 

Doing it this way ensures that members get correctly initialized and this format can also provide the compiler opportunities to optimize the code generated. For the inbuilt default types int, char, etc. there is no performance difference but for user defined types there can be.

See the C++ FAQ entry for more on this topic.

Prefer pass by reference to const

You have a function:

float computePolarAngle(point convex_pt, point candidate_pt){
    //function doesn't change convex_pt
}

It's preferable to instead pass these parameters by reference to const like so:

float computePolarAngle(point const& convex_pt, point coinst& candidate_pt){
    //function doesn't change convex_pt
}

There's 2 main reasons to do this:

1. You no longer need to make a unnecessary copy of the parameters for your function
2. You more clearly state your intent with the code, any change to bar will now throw an error at compile time. This can prevent undesirable things from happening. We all make mistakes, this just helps us catch one class of mistake sooner.

Typedefs

In many places in your code you have:

vector<point>

You might want to make a typedef for this type:

typedef std::vector<point> point_container_t;

Then use that typedef throughout your code. This makes it easier to make changes later on if you decide to change the data types you use. This isn't always a clear cut decision, choose based on the ROI for doing so in your project.

Initializer list

With C++11 we can condense this code:

vector<point> points;
points.push_back(point(1,1));
points.push_back(point(1.1,-1));
points.push_back(point(-1, 1));
points.push_back(point(-1.1,-1.1));
points.push_back(point(0.75,0.5));
points.push_back(point(-0.5,0.3));
points.push_back(point(0.25,-0.8));
points.push_back(point(0.1,-0.9));

to:

vector<point> points {
    point(1,1),
    point(1.1,-1),
    point(-1, 1),
    point(-1.1,-1.1),
    point(0.75,0.5),
    point(-0.5,0.3),
    point(0.25,-0.8),
    point(0.1,-0.9)
};

Once again, C++11 removes a bunch of boilerplate.

Documentation

You don't have any, you might want to consider adding some.

I'm a big fan of doxygen with C++, have a look into that.

Convex hull function

There's a few issues with this function so lets break them down.:

Function length

One of the main problems with this function is that for what it does it's way too long in terms of lines of code. You really should be breaking out some of this code into smaller functions. Specifically, there's a few times where you are not following the don't repeat yourself principle.

For example, things like this:

point lowestPt(points.at(0).x, points.at(0).y);
int lowestIndex = -1;
for(int index=0; index < int(points.size()) ; index++){
    if(points.at(index).y < lowestPt.y)
    {
        lowestPt.x = points.at(index).x;
        lowestPt.y = points.at(index).y;
        lowestIndex = index;
    }
}

should really be in their own functions:

int compute_lowest_index(vector<point> const& points){
    //calculate index
    return index;
}

This will help you out when you write unit tests for your code. Making as many of these small functions that are easily testable will let you greatly improve the confidence in the correctness of your code when paired with a good suite of unit tests.

Bail out early with bad input

You have this check for invalid input:

if(points.size() <= 2){
    cout<<"points should consist of more than 2 points"<<endl;
}

But then you don't do anything if the input is invalid. If you know you have bad input don't do any processing on it. When you know you have bad data return immediately at that point or throw an exception.

Loops

You have a few examples in your code like this:

for(int index=0; index<int(points.size()) ; index++){
    cout<<(points.at(index)).x<<","<<(points.at(index)).y<<endl;
}

I'm guessing you got a compilation warning for a comparison of signed with unsigned variable. If this is why you changed the code that's a good thing, it's always good to see people compiling with all warnings then taking those warnings seriously. However I'd fix that warning differently by using size_t and removing that ugly cast to int:

for(size_t index=0; index<points.size(); index++){
    cout<<(points.at(index)).x<<","<<(points.at(index)).y<<endl;
}

First, you probably want to take the check for points.size() outside the loop because you don't need to evaluate it every loop iteration:

size_t points_size = points.size();
for(size_t index=0; index<points_size ; index++){
    cout<<(points.at(index)).x<<","<<(points.at(index)).y<<endl;
}

Then if we were to do this in the c++11 way we could just use a range based for loop:

for(const point& pt : points){
    cout << pt.x <<","<< pt.y << endl;
}

This is much more terse and removes a lot of the boilerplate.

Going further though, you could just make an operator overload to print a point directly.

You need to add an overload for ostream's operator<< for the point class:

ostream& operator<<(ostream &os, const point &pt){
    os << pt.x << "," << pt.y; // print the point
    return os;
}

Then you have to change the point struct as follows to allow this:

struct point{
    //rest of point struct
    friend ostream& operator<<(ostream &os, const Account &dt);
}

You can then just call it like this:

cout << pt << endl;

Conversion from radians to degrees

Currently you are converting from radians to degrees:

float angle = (180/M_PI)*atan2(candidate_y,candidate_x);

But you only ever use the angle to determine if one angle is greater than another. Using degrees gives you no advantage over radians in this regard but you waste CPU cycles making the conversion you also waste accuracy because floats are not exact representations of decimals.

So not only does this waste CPU cycles it also makes your results less accurate. See this classic paper for more on that topic.

If you need to display the results somewhere as degrees make the conversion at that point in time. If you don't need to convert it then don't waste the overhead of the conversion.

Prefer returning values over references

In this function that computes the convex hull you are passing in a reference to store the convex hull points that you computed:

void convexHull(const vector<point>& points, vector<point>& convex_points, vector<int>& convex_points_indices);

Your display code is in this function too. This reduces flexibility for future users. What if someone just wants to compute the value and doesn't want to print out the results at the same time. Currently, you don't give them that option because you have the output tightly coupled with the function. Ideally you should have a very clear separation between UI and processing.

So generally speaking, it's a good idea to return the results instead of passing a reference, let the user of your function decide how to display it. Additionally, this makes your code closer to pure functional code and will greatly reduce the cognitive complexity for people who use your code later on.

You want your functions to be like a black box where you can provide parameters and get a result out of it. When you have the void functions that manipulate a reference you can no longer treat the function in that way as it's manipulating a variable you pass in to it. You now have to look into the internals of the function to see what it's doing to your variables. Fewer side effects leads to greater productivity which is why I would suggest just returning a value.

vector<point> convexHull(const vector<point>& points, vector<int>& convex_points_indices){
    //return the result
}