CODEWITHSUNDEEP
c++algorithmsortingmath
JUAN ALVARES
JUAN ALVARES

Reputation: 75

How order coordinate pairs?

Does anyone know how I can order a pair of coordinates (x,y) in C++?

For example that first are the coordinates of the first quadrant, then the coordinates of the second quadrant, etc.

I already tried the algorithm library with the sort method but it doesn't work.

bool com(Coordenada a, Coordenada b){
    return a.getX() < b.getX() || a.getY() < b.getY();
}

void mapa::sortVertices(){
    std::sort (ver.begin(), ver.end(), com);
}

For example, before:

x=-1;y=-1
x=1;y=1
x=1;y=-1
x=-1;y=1

after:

x=1;y=1
x=1;y=-1
x=-1;y=-1
x=-1;y=1

Upvotes: 0

Views: 550

Answers (3)

phuclv
phuclv

Reputation: 41774

Are you sure your expected result is correct? Because they're not sorted in quadrants I, II, III, IV in order

x=1;y=1   → I
x=1;y=-1  → IV
x=-1;y=-1 → III
x=-1;y=1  → II

according to the quadrant definition the result should be

x=1;y=1   → I
x=-1;y=1  → II
x=-1;y=-1 → III
x=1;y=-1  → IV

quadrants

There are various solutions to sort:

Here's a solution from Akshat

bool operator<(Point p1, Point p2) 
{
    if (p1.getY() == 0 && p1.getX() > 0) 
        return true;  // angle of p1 is 0, thus p2 > p1

    if (p2.getY() == 0 && p2.getX() > 0) 
        return false; // angle of p2 is 0 , thus p1 > p2

    if (p1.getY() > 0 && p2.getY() < 0) 
        return true; // p1 is between 0 and 180, p2 between 180 and 360

    if (p1.getY() < 0 && p2.getY() > 0) 
         return false;
    // return true if p1 is clockwise from p2
    return p1.getX() * p2.getY() - p1.getY() * p2.getX() > 0;
}

If Peter Ruderman's suggestion is what you want then you can use std::tie for the comparison function

std::sort (ver.begin(), ver.end(), std::tie(a.getX(), a.getY()) < std::tie(b.getX(), b.getY()));

Upvotes: 0

Francisco Geiman
Francisco Geiman

Reputation: 400

You have 2 options. You can overload the < operator for your struct Coordenada, or you can define a custom comparison function and pass it as a sort parameter. I have done the latter.

Here you can see the code for it.

#include <vector>
#include <algorithm>
#include <iostream>

struct Coordenada {
    int x, y;
};

int findQuad(const Coordenada& a) {
    if(a.x >= 0 && a.y >= 0) return 1;
    if(a.x < 0 && a.y >= 0) return 2;
    if(a.x < 0 && a.y < 0) return 3;
    return 4;
}

bool cmp(const Coordenada& a, const Coordenada& b) {
    return findQuad(a) < findQuad(b);
}

int main() {

    std::vector<Coordenada> vetor(10);

    for(int i = 0; i < 10; ++i) {
        vetor[i].x = rand() - rand();
        vetor[i].y = rand() - rand();
    }

    std::sort(vetor.begin(), vetor.end(), cmp);

    for(int i = 0; i < 10; ++i) {
        std::cout << vetor[i].x << " " << vetor[i].y << " quad = " << findQuad(vetor[i]) << std::endl;
    }

    return 0;
}

Upvotes: 0

Peter Ruderman
Peter Ruderman

Reputation: 12485

The problem is that you haven't defined a valid ordering with your predicate. If you want to define a total order for coordinates, you could use something like this: 

bool CoordinateLess(Coordenada a, Coordenada b)
{
  return a.getX() < b.getX() || (a.getX() == b.getX() && a.getY() < b.getY());
}

Upvotes: 2

Related Questions