i_use_the_internet - 1 year ago 299

C++ Question

i wrote a program to arrange points on a graph in clockwise manner from 12 o'clock such that, a vector containing these points is sorted in that order. I am using atan2 to get the angle from 12 o'clock and then making adjustments based on the quadrant. i am trying to figure out where the bug is coming from as it is not ordering them correctly. So given 4 random points like those in the photo, it should order then in the containing vector as P1,P2,P3,P4

Here is my code:

`//sort_points.cpp`

#include <iostream>

#include <math.h>

#include <algorithm>

#include <vector>

using namespace std;

class Point

{

public:

double x;

double y;

Point(double xx, double yy) : x(xx), y(yy) {}

~Point();

inline friend ostream& operator<<(ostream& output, const Point& point)

{

output << "[" << point.x << ", " << point.y <<"]";

return output;

}

};

Point::~Point() {;}

/* get quadrant from 12 o'clock*/

int get_quadrant (const Point& p)

{

int result = 4; //origin

if (p.x > 0 && p.y > 0)

return 1;

else if(p.x < 0 && p.y > 0)

return 2;

else if(p.x < 0 && p.y < 0)

return 3;

//else 4th quadrant

return result;

}

double get_clockwise_angle(const Point& p)

{

double angle = 0.0;

int quadrant = get_quadrant(p);

/*making sure the quadrants are correct*/

cout << "Point: " << p << " is on the " << quadrant << " quadrant" << endl;

/*add the appropriate pi/2 value based on the quadrant. (one of 0, pi/2, pi, 3pi/2)*/

switch(quadrant)

{

case 1:

angle = atan2(p.x,p.y) * 180/M_PI;

break;

case 2:

angle = atan2(p.y, p.x)* 180/M_PI;

angle += M_PI/2;

break;

case 3:

angle = atan2(p.x,p.y)* 180/M_PI;

angle += M_PI;

break;

case 4:

angle = atan2(p.y, p.x)* 180/M_PI;

angle += 3*M_PI/2;

break;

}

return angle;

}

bool compare_points(const Point& a, const Point& b)

{

return (get_clockwise_angle(a) < get_clockwise_angle(b));

}

int main(int argc, char const *argv[])

{

std::vector <Point> points;

points.push_back( Point( 1, 3 ) );

points.push_back( Point( 2, 1 ) );

points.push_back( Point( -3, 2 ) );

points.push_back( Point( -1, -1 ) );

cout << "\nBefore sorting" << endl;

for (int i = 0; i < points.size(); ++i)

{

cout << points.at(i) << endl;

}

std::sort(points.begin(), points.end(),compare_points);

cout << "\nAfter sorting" << endl;

for (int i = 0; i < points.size(); ++i)

{

cout << points.at(i) << endl;

}

return 0;

}

Answer Source

You don't need the adjustment. `atan2`

will give you the angle from positive direction of x axis, counterclockwise in range of -PI to PI.

Firstly, to make the starting point positive direction of y axis, let me give parameter to `atan2`

as if negative direction of y axis is positive direction of x axis and positive direction of x axis is positive direction is y axis.

Then, this will make the angle counterclockwise, so negate the angle in order to reverse the order.

```
double get_clockwise_angle(const Point& p)
{
double angle = 0.0;
int quadrant = get_quadrant(p);
/*making sure the quadrants are correct*/
cout << "Point: " << p << " is on the " << quadrant << " quadrant" << endl;
/*calculate angle and return it*/
angle = -atan2(p.x,-p.y);
return angle;
}
```