How order coordinate pairs?

Question

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

What have you tried to use with `sort`? Have you supplied a custom way of comparing in some form? — user3738870, Sep 22 '18 at 23:17
Your comparison will return True if either coordinate of a is less than b. Is that what you want? — stark, Sep 22 '18 at 23:20
what is mapa? https://stackoverflow.com/questions/19842035/stdmap-how-to-sort-by-value-then-by-key — kelalaka, Sep 22 '18 at 23:24
@kelalaka I suppose it's in Spanish or some similar language. — user3738870, Sep 22 '18 at 23:26

score 2 · Answer 1 · answered Sep 22 '18 at 23:28

2

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());
}

answered Sep 22 '18 at 23:28

Peter Ruderman

12,241
1
36
58

The OP's ordering is valid. It will sort points along a diagonal from lower left to upper right. – stark Sep 22 '18 at 23:45
1

@stark It's not, because its not asymetrical:`(5,2)<(2,5)` and `(2,5)<(5,2)` are both true. – Quimby Sep 22 '18 at 23:57
unfortunately this way (1; -1) in quadrant IV will be sorted before (-1; -1) in quadrant II – phuclv Sep 23 '18 at 01:44

score 0 · Answer 2 · answered Sep 23 '18 at 01:09

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;
}

score 0 · Accepted Answer · answered Sep 23 '18 at 01:42

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

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()));

How order coordinate pairs?

3 Answers3