title: Sort polygon's points for drawing
body: <p>I have a matrix (0 means nothing, 1 means terrain) that represents a level in my game. The matrix corresponds to a grid that my screen is broken up into, and indicates where my terrain goes.</p>
  <p>My terrain is actually composed of 4 points in the corners of each block within the grid. When you have multiple blocks that are connected, I use a merge-cell algorithm that removes the duplicate points and any interior points. The result is that I end up with a list of points representing only the outer edges of the polygon.</p>
  <p>To draw this polygon, I need the points to be in some sort of order (either clockwise or counter-clockwise) such that each point is followed by it's neighboring point. Obviously the first and last points need to be neighbors. Since this is all in a grid, I know the exact distance between neighboring points.</p>
  <p>The problem is that I am having trouble coming up with an algorithm that allows me to &quot;walk&quot; around the edge of the polygon while putting the points in order. I believe there should be a way to utilize the fact that I have the matrix representing the geometry, meaning there is only 1 possible way to draw the polygon (even if it is concave).</p>
  <p>I have tried several approaches using greedy-type algorithms, but can't seem to find a way to know, in every case, which direction I want to travel in. Given that any particular point can have up to 3 neighbors (the fourth isn't included because it is the &quot;starting&quot; point, meaning that I have already sorted it) I need a way of knowing which way to move.</p>
  <h1>Update</h1>
  <p>Another approach that I have been trying is to sort the points by their X (with tiebreaker of Y) which gives me the topmost/leftmost edge. It also guarantees that I am starting on an outer edge. However, I'm still struggling to find an algorithm that guarantees that I stay on the outside without crossing over.</p>
  <p>Here is an example matrix:</p>
  <p>0 0 0 0 0 0 0 0 0 0</p>
  <p>0 0 0 1 1 1 0 0 0 0</p>
  <p>0 0 0 0 0 1 0 0 0 0</p>
  <p>0 0 0 0 0 1 1 1 0 0</p>
  <p>Which corresponds to this (black dots represent my points):
  <img src="https://i.stack.imgur.com/Q00Y0.png" alt="Polygon" /></p>