How to sort in counterclockwise all point of one vector with n elments

Question

I am searching a solution for following problem:

I planned to solve this with sort of vectors but It isn't a solution for all of my case.

I write before this post about, how to sort vector of points with (x, y, z).

I will explain here what the problem is.

I have this vector:

 Point [0] = [X: 3.00;Y: 0.00;Z: 0.00] 
 Point [1] = [X: 3.00;Y: 0.00;Z: 3.00] 
 Point [2] = [X: 3.00;Y: 5.00;Z: 0.00] 
 Point [3] = [X: 3.00;Y: 5.00;Z: 3.00] 
 Point [4] = [X: 0.00;Y: 5.00;Z: 0.00] 
 Point [5] = [X: 0.00;Y: 5.00;Z: 3.00] 
 Point [6] = [X: 0.00;Y: 0.00;Z: 0.00] 
 Point [7] = [X: 0.00;Y: 0.00;Z: 3.00]

First step sort by z: Then

std::sort(std::begin(vector_points), std::end(vector_points),
[](auto const& a, auto const& b) {return (a.z < b.z); });

 Point [0] = [X: 3.00;Y: 0.00;Z: 0.00] 
 Point [1] = [X: 3.00;Y: 5.00;Z: 0.00] 
 Point [2] = [X: 0.00;Y: 5.00;Z: 0.00] 
 Point [3] = [X: 0.00;Y: 0.00;Z: 0.00] 
 Point [4] = [X: 3.00;Y: 0.00;Z: 3.00] 
 Point [5] = [X: 3.00;Y: 5.00;Z: 3.00] 
 Point [6] = [X: 0.00;Y: 5.00;Z: 3.00] 
 Point [7] = [X: 0.00;Y: 0.00;Z: 3.00]

Second step sort by y: Then

 auto yComp = [](const auto& p1, const auto& p2){return p1.y < p2.y;};

 std::sort(vector_points.begin(), vector_points.begin() + 4, yComp);

 std::sort(vector_points.begin() + 4, vector_points.begin() + 8, yComp);

 Point [0] = [X: 3.00;Y: 0.00;Z: 0.00] 
 Point [1] = [X: 0.00;Y: 0.00;Z: 0.00] 
 Point [2] = [X: 3.00;Y: 5.00;Z: 0.00] 
 Point [3] = [X: 0.00;Y: 5.00;Z: 0.00] 
 Point [4] = [X: 3.00;Y: 0.00;Z: 3.00] 
 Point [5] = [X: 0.00;Y: 0.00;Z: 3.00] 
 Point [6] = [X: 3.00;Y: 5.00;Z: 3.00] 
 Point [7] = [X: 0.00;Y: 5.00;Z: 3.00]

Third step sort by x: Then

std::sort(vector_points.begin(), vector_points.begin() + 2, xComp);

std::sort(vector_points.begin() + 2, vector_points.begin() + 4, xComp);

std::sort(vector_points.begin() + 4, vector_points.begin() + 6, xComp);

std::sort(vector_points.begin() + 6, vector_points.begin() + 8, xComp);

 Point [0] = [X: 0.00;Y: 0.00;Z: 0.00] 
 Point [1] = [X: 3.00;Y: 0.00;Z: 0.00] 
 Point [2] = [X: 0.00;Y: 5.00;Z: 0.00] 
 Point [3] = [X: 3.00;Y: 5.00;Z: 0.00] 
 Point [4] = [X: 0.00;Y: 0.00;Z: 3.00] 
 Point [5] = [X: 3.00;Y: 0.00;Z: 3.00] 
 Point [6] = [X: 0.00;Y: 5.00;Z: 3.00] 
 Point [7] = [X: 3.00;Y: 5.00;Z: 3.00]

I would like a vector with the first half of the points sorted in a counterclockwise direction.

Would anyone help me?

Your tripple sorting doesn't sort correctly because `std::sort` is not [stable](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability). You would need to use `std::stable_sort` instead. A better way though would be to change the comparison function to `return std::tie(a.x, a.y, a.z) < std::tie(b.x, b.y, b.z);`. A clockwise sort works for 2D points, not sure how to generalize it to 3D points. — nwp, Mar 20 '17 at 16:36

score 0 · Answer 1 · answered Mar 20 '17 at 16:36

I'm not writing out the full soution, but you can pass a comparer to std::sort:

std::sort(std::begin(vector_points), std::end(vector_points), [](const auto& a, const auto& b)
{
   if (a.z < 0)
   {
      //compare x and y points and return true/false depending.
   }
   else
   {
      //compare x and y points and return false/true depending.
   }
});

How to sort in counterclockwise all point of one vector with n elments

1 Answers1