title: Sorting algorithm for mesh slicing
body: <p>I got a problem with the sorting algorithms for a 3D printer software. I get the xyz Data of the slices of a given .stl File as a vector with three columns and n rows, where n is the number of points for each slice.</p>
  
  <p>So the code for the vector looks like this:</p>
  
  <pre><code>        x=matrix[n][0];
          y=matrix[n][1];
          z=matrix[n][2];
  </code></pre>
  
  <p>So matrix is my vector containing all coordinates for all points in the mesh.</p>
  
  <p>When I print out the coordinates of the points I get an unsorted list. So the following list shows the points of the first layer/slice of a cube, with the dimensions of 10x10x10mm.</p>
  
  <pre><code>X=-5.000000, Y=2.000000, Z=-2.000000
  X=-5.000000, Y=-5.000000, Z=-2.000000
  X=5.000000, Y=5.000000, Z=-2.000000
  X=5.000000, Y=-2.000000, Z=-2.000000
  X=5.000000, Y=-2.000000, Z=-2.000000
  X=5.000000, Y=-5.000000, Z=-2.000000
  X=5.000000, Y=5.000000, Z=-2.000000
  X=2.000000, Y=5.000000, Z=-2.000000
  X=2.000000, Y=5.000000, Z=-2.000000
  X=-5.000000, Y=5.000000, Z=-2.000000
  X=5.000000, Y=-5.000000, Z=-2.000000
  X=-2.000000, Y=-5.000000, Z=-2.000000
  X=-2.000000, Y=-5.000000, Z=-2.000000
  X=-5.000000, Y=-5.000000, Z=-2.000000
  </code></pre>
  
  <p>So the result of this is shown in this figur.
  <a href="https://i.stack.imgur.com/NXZWn.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/NXZWn.png" alt="Unsorted points"></a></p>
  
  <p>My first approach was to sort the points, but the result is far away from what I need to have.
  <a href="https://i.stack.imgur.com/8KtGL.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/8KtGL.png" alt="sorted"></a> </p>
  
  <p>The sorted list looks like this</p>
  
  <pre><code>X=5.000000, Y=5.000000, Z=-2.000000 
  X=5.000000, Y=5.000000, Z=-2.000000 
  X=5.000000, Y=-2.000000, Z=-2.000000 
  X=5.000000, Y=-2.000000, Z=-2.000000 
  X=5.000000, Y=-5.000000, Z=-2.000000 
  X=5.000000, Y=-5.000000, Z=-2.000000 
  X=2.000000, Y=5.000000, Z=-2.000000 
  X=2.000000, Y=5.000000, Z=-2.000000 
  X=-2.000000, Y=-5.000000, Z=-2.000000 
  X=-2.000000, Y=-5.000000, Z=-2.000000 
  X=-5.000000, Y=5.000000, Z=-2.000000 
  X=-5.000000, Y=2.000000, Z=-2.000000 
  X=-5.000000, Y=-5.000000, Z=-2.000000 
  X=-5.000000, Y=-5.000000, Z=-2.000000 
  </code></pre>
  
  <p>The only idea, how I could sort the points is to start in the first quadrant of a Cartesian coordinate system and then move to the following quadrants. As I'm computing layer by layer the z-coodrinate can be ignored. But for this, I don't know how to start the code. Does someone have a hint for me? </p>
  
  <p>What I want to achieve is to sort the list of points in the following way:</p>
  
  <pre><code>X=-5.000000, Y=5.000000, Z=-2.000000
  X=-5.000000, Y=2.000000, Z=-2.000000
  X=-5.000000, Y=-5.000000, Z=-2.000000
  X=-5.000000, Y=-5.000000, Z=-2.000000
  X=-2.000000, Y=-5.000000, Z=-2.000000
  X=-2.000000, Y=-5.000000, Z=-2.000000
  X=5.000000, Y=-5.000000, Z=-2.000000
  X=5.000000, Y=-5.000000, Z=-2.000000
  X=5.000000, Y=-2.000000, Z=-2.000000
  X=5.000000, Y=-2.000000, Z=-2.000000
  X=5.000000, Y=5.000000, Z=-2.000000
  X=5.000000, Y=5.000000, Z=-2.000000
  X=2.000000, Y=5.000000, Z=-2.000000
  X=2.000000, Y=5.000000, Z=-2.000000
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/CTH02.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/CTH02.png" alt="enter image description here"></a></p>