C++ std::sort with custom function

Question

I have a structure Point:

typedef struct Point
{
    double x;
    double y;

    Point operator-(const Point &b)
    {
        Point pt;
        pt.x = this->x - b.x;
        pt.y = this->y - b.y;
        return pt;
    }

    friend std::ostream& operator<<(std::ostream& os, const Point& pt)
    {
        return os << "X: " << pt.x << "\t\t\tY: " <<pt.y << std::endl; 
    }

    friend std::istream& operator>>(std::istream& is, Point& pt)
    {
        return is >> pt.x >> pt.y;
    }
}Point;

I am trying to find the minimum element from the vector<Point> and then sort based on angles against this minimum point.

Below is the respective code:

bool lex_yx(const Point &a, const Point &b)
{
    if(a.y < b.y)
        return true;

    if (a.y == b.y)
        return (a.x < b.x);

    return false;
}

bool CalcAngRad_Compare (const Point &p_min, Point &a, Point &b)
{
    Point subPt_1, subPt_2;
    double a_r, b_r, a_angle, b_angle;

    subPt_1 = a - p_min, subPt_2 = b - p_min;

    a_angle = atan2(subPt_1.y, subPt_1.x);
    b_angle = atan2(subPt_2.y, subPt_2.x);

    if (a_angle < b_angle) {return true;}
    if (a_angle > b_angle) {return false;}

    a_r = subPt_1.x * subPt_1.x * subPt_1.y * subPt_1.y; 
    b_r = subPt_2.x * subPt_2.x * subPt_2.y * subPt_2.y; 

    return (a_r < b_r); // return (a_r <= b_r); // Code crashes, saying invalid operator <. I do not know why. Pl tell me.
}

auto it  = std::min_element(V.begin(), V.end(), lex_yx);
std::sort(  V.begin(), V.end(), boost::bind(CalcAngRad_Compare, *it, _1, _2)); 

When I pass in a simple test input such as

2 2
3 3
4 4
1 1 // this should be first element in the sorted array
5 5

it works, I get the sorted array. But now take a look at this another simple input:

-0.5    -0.1
-0.1    -0.1
0       1
-1      -0.1 // this should be first element is sorted array. BUT IT IS NOT!!
5       5

I do not think I have done anything wrong. One issue might be that when y coordinate is equal, angle is 0 or pi. In that case, if radius is also equal, then I return false. I tried to change this to return (a_r <= b_r), but this seems not possible. Code crashes saying invalid operator <. (in the file xutility with true at this line: else if (_Pred(_Right, _Left)). I do not understand what is being tested, may be some precedence is checked.)

What I want you to answer:

1. How can I solve the issue and always get the (correctly) sorted vector
2. Is there any other way of achieving what I am doing?
3. I am very much interested in learning what is problem in my thinking/implementation style?

Answer 1

Your first sort criteria is angle calculated by atan2. In your case p_min is -1.0/-0.1. If a is -1.0/-0.1 and bis -0.5/-0.1, you will calcualte atan2( -0.1 + 0.1, -1.0 + 1.0 ); (a-p_min) and atan2( -0.1 + 0.1, -0.5 + 1.0 ); (b-p_min) which is 0.0 in both cases. You continue to compare 0.0 * 0.0 * 0.0 * 0.0 (a) with 0.5 * 0.5 * 0.0 * 0.0(b) which means 0.0 < 0.0. Consequently a (-1.0/-0.1) is not less than b(-0.5/-0.1).

To calculate angle between to vectors use DOT-product. |A| * |B| * cos(angle between A and B ) = Ax * Bx + Ay * By

double len_p_min = sqrt( p_min.x*p_min.x + p_min.y*p_min.y ); // lenght of p_min
double len_a = sqrt( a.x*a.x + a.y*a.y ); // lenght of a
double len_b = sqrt( b.x*b.x + b.y*b.y ); // lenght of b

Point normalizedMin{ p_min.x / len_p_min, p_min.y / len_p_min }; // direction of p_min ( lenght == 1.0)
Point normalizedA{ a.x / len_a, a.y / len_a }; // direction of a ( lenght == 1.0)
Point normalizedB{ b.x / len_b, b.y / len_b }; // direction of b ( lenght == 1.0)

double cosAmin = normalizedMin.x*normalizedA.x + normalizedMin.y*normalizedA.y; // cos of angle between a and p_min
double angleAmin = acos( cosAmin );

double cosBmin = normalizedMin.x*normalizedB.x + normalizedMin.y*normalizedB.y; // cos of angle between b and p_min
double angleBmin = acos( cosBmin );

To compare angles it is not necessary to calculate acos. It is sufficient to compare cos of angles

if ( fabs( cosAmin ) < fabs( cosBmin ) ) {return true;}
if ( fabs( cosAmin ) > fabs( cosbmin ) ) {return false;}

If you like to sort vector by length use |v| = sqrt( v.x * v.x + v.y * v.y ) If only have to compare length of vectors, you don't need to calculate sqrt, it will be sufficient to compare lentgth^2.

a_r = subPt_1.x * subPt_1.x + subPt_1.y * subPt_1.y; // |a|^2 (lenght of a pow 2)
b_r = subPt_2.x * subPt_2.x + subPt_2.y * subPt_2.y; // |b|^2 (lenght of b pow 2)

return (a_r < b_r);

Answer 2

How can I solve the issue and always get the (correctly) sorted vector Is there any other way of achieving what I am doing?

Not sure of the order you want, does less_yx do the job ?

I am very much interested in learning what is problem in my thinking/implementation style?

Assuming IEEE floating-point arithmetic (else you have domain error for 0, 0)

As your reference point is the lowest y, second arg passed to atan2 is positive or null.

- `atan2(0, 0) = 0`
- `atan2(+x, 0) = 0`
- `atan2(x, +y) > 0`

So any lowest y are equivalent according to atan2.

a_r = subPt_1.x * subPt_1.x * subPt_1.y * subPt_1.y;

is always 0 for subPt_1.y == 0. Do you mean

a_r = subPt_1.x * subPt_1.x + subPt_1.y * subPt_1.y;

instead ? (so it compare x even when y == 0)