We help IT Professionals succeed at work.
Get Started

How to order a std::vector of struct Point x,y and eliminate duplicates

217 Views
Last Modified: 2020-09-19
Following one of my last questions, I'm correctly able to import points (x,y) in a structure and store them in a std::vector.
This allows me to obtain a series of segments described by two coordinates points and use them as waypoint for my path planning software for my robot.

I need to make my robot move along all the vertical segments and then on all the horizontal segments (or viceversa), so I sort the std::vector by ordering its X values from low to high and then I check for segments that are parallel to the X axis
void parallel_x()

Open in new window

and then for those parallel to the Y axis
void parallel_y()

Open in new window


The algorithm seems to work fine, but the problem is that I should sort the vector in order to start from the lower X and also Y values.
I don't know how to sort the vector components by checking both X and Y values.

Moreover, I realized that sometimes some segments are sorted twice.

struct Coordinate
{
    double x0 = 0.0;
    double x1 = 0.0;
    double y0 = 0.0;
    double y1 = 0.0;

    Coordinate(double paramx0, double paramy0, double paramx1, double paramy1) : x0(paramx0), y0(paramy0), x1(paramx1), y1(paramy1) {}
    Coordinate(double paramx0, double paramy0) : x0(paramx0), y0(paramy0) {}
};

std::vector<Coordinate> coords;
std::vector<Coordinate> coords_x;
std::vector<Coordinate> coords_y;

bool compareByLength_x(const Coordinate &a, const Coordinate &b)
{
    return a.x0 < b.x0;
}

bool compareByLength_y(const Coordinate &a, const Coordinate &b)
{
    return a.y0 < b.y0;
}

bool num_equal(const Coordinate &a, const Coordinate &b)
{
    return (a.x0==b.x0)&&(a.y0==b.y0);
}

void parallel_y(int n, std::vector<Coordinate> test) {
   
  int counter = 0;
  for (int i=0; i<n; 2*i++){
  if ( test[i].x0 == test[i+1].x0 ){
  cout << "C: " << counter << " Y Index: " << 2*i << " X0, Y0: " << test[i].x0 << ", " << test[i].y0 << " X1, Y1: " << test[i+1].x0 << ", " << test[i+1].y0 << endl;
  coords_y.push_back(Coordinate(test[i].x0, test[i].y0));
  coords_y.push_back(Coordinate(test[i+1].x0, test[i+1].y0));
  }
  counter++;
  }
 
}

void parallel_x(int n, std::vector<Coordinate> test){

  int counter = 0;
  for (int i=0; i<n; 2*i++){
  if( test[i].y0 == test[i+1].y0 ){
  cout << "C: " << counter << " X Index: " << i << " X0, Y0: " << test[i].x0 << ", " << test[i].y0 << " X1, Y1: " << test[i+1].x0 << ", " << test[i+1].y0 << endl;
  coords_x.push_back(Coordinate(test[i].x0, test[i].y0));
  coords_x.push_back(Coordinate(test[i+1].x0, test[i+1].y0));
  }
  counter++;
  }

}

int main(){

std::sort(coords.begin(), coords.end(), compareByLength_x);

for (unsigned int i = 0; i < coords.size(); ++i)
{
   cout << i << " X[0]: " << coords[i].x0 << " Y[0]: " << coords[i].y0 << endl; 
}

cout << "\n" << endl;

parallel_y(coords.size(), coords);

cout << "\n" <<endl;


std::sort(coords.begin(), coords.end(), compareByLength_y);

for (unsigned int i = 0; i < coords.size(); ++i)
{
   cout << i << " X[0]: " << coords[i].x0 << " Y[0]: " << coords[i].y0 << endl; 
}

cout << "\n" << endl;

parallel_x(coords.size(), coords);

cout << "\n" <<endl;

std::sort(coords_x.begin(), coords_x.end(), compareByLength_x);
coords_x.erase(unique(coords_x.begin(),coords_x.end(),num_equal),coords_x.end());

for (unsigned int i = 0; i < coords_x.size(); ++i)
{
   cout << i << " X -  X[0]: " << coords_x[i].x0 << " Y[0]: " << coords_x[i].y0 << endl; 
}

cout << "\n" <<endl;

std::sort(coords_y.begin(), coords_y.end(), compareByLength_y);
coords_y.erase(unique(coords_y.begin(),coords_y.end(),num_equal),coords_y.end());

for (unsigned int i = 0; i < coords_y.size(); ++i)
{
   cout << i << " Y -  X[0]: " << coords_y[i].x0 << " Y[0]: " << coords_y[i].y0 << endl; 
}

}

Open in new window


This is the output generated by my code and related to this series of red segments/rectangles.
rects.PNG
Please, keep in mind that a segment is identified by two points in total and that each line in the list contains ONE point, so, for example, the first segment is identified by line #0 and #1 in the following list.

Origin of segment 1 - Point #0:  X[0]: 38163.8 Y[0]: 21432.3
End of segment 1 -    Point #1:  X[0]: 38163.8 Y[0]: 1432.32


// unsorted list of coordinates:
// 0,1 make a segment, 2,3 make another segment and so on
 
0 X[0]: 38163.8 Y[0]: 21432.3
1 X[0]: 38163.8 Y[0]: 1432.32
2 X[0]: 46163.8 Y[0]: 21432.3
3 X[0]: 46163.8 Y[0]: 1432.32
4 X[0]: 46163.8 Y[0]: 21432.3
5 X[0]: 49649.5 Y[0]: 21432.3
6 X[0]: 49649.5 Y[0]: 1432.32
7 X[0]: 57649.5 Y[0]: 21432.3
8 X[0]: 57649.5 Y[0]: 21432.3
9 X[0]: 57649.5 Y[0]: 1432.32
10 X[0]: 61649.5 Y[0]: 21432.3
11 X[0]: 61649.5 Y[0]: 13432.3
12 X[0]: 61649.5 Y[0]: 9432.32
13 X[0]: 61649.5 Y[0]: 1432.32
14 X[0]: 69649.5 Y[0]: 9432.32
15 X[0]: 69649.5 Y[0]: 21432.3
16 X[0]: 69649.5 Y[0]: 13432.3
17 X[0]: 69649.5 Y[0]: 21432.3
18 X[0]: 69649.5 Y[0]: 9432.32
19 X[0]: 69649.5 Y[0]: 1432.32

//segments along X axis generated by the parallel_x function
0 X -  X[0]: 38163.8 Y[0]: 1432.32
1 X -  X[0]: 38163.8 Y[0]: 21432.3
2 X -  X[0]: 46163.8 Y[0]: 1432.32
3 X -  X[0]: 46163.8 Y[0]: 21432.3
4 X -  X[0]: 49649.5 Y[0]: 1432.32
5 X -  X[0]: 49649.5 Y[0]: 21432.3
6 X -  X[0]: 57649.5 Y[0]: 21432.3
7 X -  X[0]: 57649.5 Y[0]: 1432.32
8 X -  X[0]: 61649.5 Y[0]: 21432.3
9 X -  X[0]: 61649.5 Y[0]: 13432.3
10 X -  X[0]: 61649.5 Y[0]: 1432.32
11 X -  X[0]: 61649.5 Y[0]: 21432.3   // <-- this is a duplicate!
12 X -  X[0]: 61649.5 Y[0]: 9432.32
13 X -  X[0]: 69649.5 Y[0]: 21432.3
14 X -  X[0]: 69649.5 Y[0]: 1432.32
15 X -  X[0]: 69649.5 Y[0]: 13432.3
16 X -  X[0]: 69649.5 Y[0]: 9432.32

// segments along of Y axis generated by the parallel_y function
0 Y -  X[0]: 38163.8 Y[0]: 1432.32
1 Y -  X[0]: 46163.8 Y[0]: 1432.32
2 Y -  X[0]: 69649.5 Y[0]: 1432.32
3 Y -  X[0]: 61649.5 Y[0]: 1432.32
4 Y -  X[0]: 57649.5 Y[0]: 1432.32
5 Y -  X[0]: 49649.5 Y[0]: 1432.32
6 Y -  X[0]: 69649.5 Y[0]: 9432.32
7 Y -  X[0]: 61649.5 Y[0]: 9432.32
8 Y -  X[0]: 69649.5 Y[0]: 9432.32  // <-- this is another duplicate!
9 Y -  X[0]: 69649.5 Y[0]: 13432.3
10 Y -  X[0]: 61649.5 Y[0]: 13432.3
11 Y -  X[0]: 46163.8 Y[0]: 21432.3
12 Y -  X[0]: 38163.8 Y[0]: 21432.3
13 Y -  X[0]: 46163.8 Y[0]: 21432.3
14 Y -  X[0]: 49649.5 Y[0]: 21432.3
15 Y -  X[0]: 69649.5 Y[0]: 21432.3
16 Y -  X[0]: 61649.5 Y[0]: 21432.3
17 Y -  X[0]: 69649.5 Y[0]: 21432.3
18 Y -  X[0]: 57649.5 Y[0]: 21432.3

Open in new window


The problem about the ordering is that the robot needs to move along coordinates that are placed one after the other without jumps, for example, in this case:

13 X -  X[0]: 69649.5 Y[0]: 21432.3
14 X -  X[0]: 69649.5 Y[0]: 1432.32
15 X -  X[0]: 69649.5 Y[0]: 13432.3
16 X -  X[0]: 69649.5 Y[0]: 9432.32

the order is wrong because the segments are: #14-16 and #15-13
I think this is due to the fact that I'm not able to order the vector by considering both X and Y values at the same time since I'm ordering it only by considering the X value.

How can i fix this?
Comment
Watch Question
This question hasn't been answered yet.
While you wait, find out how you can maximize your capability with the most trusted tool in IT.
Explore More Ask a Question
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE