title: Erroneous points produced on convex hull despite following Graham scan
body: <p>I've essentially followed the <a href="http://en.wikipedia.org/wiki/Graham_scan" rel="nofollow noreferrer">wikipedia entry for Graham scan</a> every step of the way as I've coded this little convex hull visualizer. It generally works as intended, but at much higher input sizes there are often erroneous points.</p>
  
  <p>The program starts by filling an <code>ArrayList&lt;Point&gt;</code> with a given number of randomly generated <code>Point</code> objects. It then finds the <code>Point</code> with the lowest <code>y</code>. If multiple <code>Point</code> objects share the lowest value, then the one with the lowest <code>x</code> is used. </p>
  
  <p>Next, it generates an <code>ArrayList&lt;Double&gt;</code> of angles of every <code>Point</code> relative to the specific <code>Point</code> found above. It quicksorts these angles and their corresponding <code>Point</code> objects to produce an <code>ArrayList&lt;Point&gt;</code> with sorted values.</p>
  
  <p>The next step is where I believe my problem lies. First, I make a copy of the <code>ArrayList&lt;Point&gt;</code> and call it <code>edges</code> (note that if I was not using the original <code>ArrayList&lt;Point&gt;</code> for visualization, cloning would be unnecessary) For any three ordered <code>Point</code> objects in <code>edges</code> we'll call <code>A</code>, <code>B,</code> and <code>C</code>, if from <code>AB</code> to <code>BC</code> there is a right turn, then <code>B</code> should be excluded from the hull and is removed from <code>edges</code>. I determine whether the turn is right or left by taking the z-value of the cross product (negative z means <code>AB</code> to <code>BC</code> is a right turn). The program removes any points which causes right turns and carries on.</p>
  
  <pre><code>// loops through the orders points. any time a right turn is
  // encountered, the middle point is removed
  edges = new ArrayList&lt;Point&gt;();
  edges.addAll(points);
  boolean changed = true;
  while (changed) {
      changed = false;
      for (int i = 0; i &lt; edges.size() - 2; i++) {
          if (isRightTurn(edges.get(i), edges.get(i + 1),
                  edges.get(i + 2))) {
              edges.remove(i + 1);
              changed = true;
              i--;
          }
      }
      if (isRightTurn(edges.get(edges.size() - 2),
          edges.get(edges.size() - 1), edges.get(0))) {
          edges.remove(edges.size() - 1);
          changed = true;
      }
  }
  
  
  // uses the z-value of the cross product of AB and AC (ABxAC) to determine
  // the direction of the turn.
  public static boolean isRightTurn(Point a, Point b, Point c) {
      if ((b.getX() - a.getX()) * (c.getY() - a.getY())
              - (b.getY() - a.getY()) * (c.getX() - a.getX()) &lt; 0)
          return true;
      return false;
  }
  </code></pre>
  
  <p>I mainly added the <code>changed</code> variable for the sake of looping through multiple times just to verify in case something was skipped over. However, the error still persists. Sometimes, it works as intended. <img src="https://i.stack.imgur.com/XuH7x.png" alt="Successful convex hull"></p>
  
  <p>However, frequently there are at least a few incorrect <code>Point</code> objects.<img src="https://i.stack.imgur.com/C1rsd.png" alt="Unsuccessful convex hull"></p>
  
  <p>Now what I'm noticing is that up until the left turn occurs, there are multiple <code>Points</code> which properly turn left, but are still erroneous because they ultimately lie inside what should be the convex hull. Could this be an issue of backtracking? I feel like the repeated looping through should catch these cases.</p>