CODEWITHSUNDEEP
c++algorithmmathoptimizationconvex-hull
Shreyas Shetty
Shreyas Shetty

Reputation: 897

Given a pivot point, sort a set of points in increasing order of angle which they make with the pivot point

As said in the title we need to sort the points in increasing order of angles.

I am taking the cross product with pivot point and other points. If the cross product considering any two points with the pivot point is positive, it means that those two points are sorted in the increasing order.

I am unable to find the mistake in this idea but this does not work. The code is:

//Here,a[0] is the pivot point.

//pivot is a global variable assigned to a[0].

vector<pair<int, int>>a(n);

sort(a.begin() + 1, a.end(), comp);

int comp(pair<int, int> x, pair<int, int> y) {
    int cross_product = crpd(pivot, x, y);

    if (cross_product >= 0)
        return 1;

    return 0;
}

int crpd(pair<int, int> a, pair<int, int> b, pair<int, int> c) {
    //y2*x1 - y1*x2
    int y2 = a.second - c.second;
    int x2 = a.first - c.first;
    int y1 = a.second - b.second;
    int x1 = a.first - b.first;
    int ans = x1 * y2 - x2 * y1;
    return ans;
}

Sample Input:

Pivot: (0,-4)

Points: [ (-5,0) , (-5,1) , (-4,2) , (-3,3) , (-1,4) , (5,0) , (4,-3) , (0,-4) , (-4,-3) ] 
Expected Output: [ (4,-3) , (5,0) , (-1,4) , (-3,3) , (-4,2) , (-5,1) , (-5,0) , (-4,-3) ]
Displayed Output: [ (-5,0) , (4,-3) , (5,0) , (-1,4) , (-3,3) , (-4,2) , (-5,1) , (-4,-3) ]

If anyone finds any mistake anywhere please answer

Upvotes: 0

Views: 104

Answers (1)

MBo
MBo

Reputation: 80187

Cross-product "as-is" gives only sign of angle because your vectors are not normalized (unit length). Dividing by magnitudes of vectors is a step in correct direction but it gives possible range of angles -Pi/2..Pi/2

You can get comparable value - angle in full range -Pi..Pi using atan2

angle = atan2(x1 * y2 - x2 * y1, x1 * x2 + y1 * y2);

Upvotes: 2

Related Questions