title: Decomposition to Convex Polygons
body: <p>This question is a little involved. I wrote an algorithm for breaking up a <a href="http://en.wikipedia.org/wiki/Simple_polygon" rel="nofollow noreferrer">simple polygon</a> into convex subpolygons, but now I'm having trouble proving that it's <em>not</em> optimal (i.e. minimal number of convex polygons using <em>Steiner points</em> (added vertices)). My prof is adamant that it can't be done with a greedy algorithm such as this one, but I can't think of a counterexample.</p>
  
  <p>So, if anyone can prove my algorithm is suboptimal (or optimal), I would appreciate it.</p>
  
  <p>The easiest way to explain my algorithm with pictures (these are from an older suboptimal version)</p>
  
  <p><img src="https://i.stack.imgur.com/jECBK.png" alt=""></p>
  
  <p>What my algorithm does, is extends the line segments around the point i across until it hits a point on the opposite edge.</p>
  
  <p>If there is no vertex within this range, it creates a new one (the red point) and connects to that:</p>
  
  <p><img src="https://i.stack.imgur.com/SQRpU.png" alt=""></p>
  
  <p>If there <em>is</em> one or more vertices in the range, it connects to the closest one. This <em>usually</em> produces a decomposition with the fewest number of convex polygons:</p>
  
  <p><img src="https://i.stack.imgur.com/Jj9Vh.png" alt=""></p>
  
  <p>However, in some cases it can fail -- in the following figure, if it happens to connect the middle green line first, this will create an extra unneeded polygon. To this I propose double checking all the edges (diagonals) we've added, and check that they are all still necessary. If not, remove it:</p>
  
  <p><img src="https://i.stack.imgur.com/SkGN8.png" alt=""></p>
  
  <p>In some cases, however, this is not enough. See this figure:</p>
  
  <p><img src="https://i.stack.imgur.com/Pqw5F.png" alt=""></p>
  
  <p>Replacing a-b and c-d with a-c would yield a better solution. In this scenario though, there's no edges to remove so this poses  a problem. In this case I suggest an order of preference: when deciding which vertex to connect a reflex vertex to, it should choose the vertex with the highest priority:</p>
  
  <p>lowest) closest vertex</p>
  
  <p>med) closest reflex vertex</p>
  
  <p>highest) closest reflex that is also in range when working backwards (hard to explain) --</p>
  
  <p>In <a href="http://www.sfu.ca/~mnb2/conv/case4.png" rel="nofollow noreferrer">this figure</a>, we can see that the reflex vertex 9 chose to connect to 12 (because it was closest), when it would have been better to connect to 5. Both vertices 5 and 12 are in the range as defined by the extended line segments 10-9 and 8-9, but vertex 5 should be given preference because 9 is within the range given by 4-5 and 6-5, but NOT in the range given by 13-12 and 11-12. i.e., the edge 9-12 elimates the reflex vertex at 9, but does NOT eliminate the reflex vertex at 12, but it CAN eliminate the reflex vertex at 5, so 5 should be given preference.</p>
  
  <p>It is possible that the edge 5-12 will still exist with this modified version, but it can be removed during post-processing.</p>
  
  <p>Are there any cases I've missed?</p>
  
  <hr>
  
  <p>Pseudo-code (requested by John Feminella) -- this is missing the bits under Figures 3 and 5</p>
  
  <pre><code>assume vertices in `poly` are given in CCW order
  let 'good reflex' (better term??) mean that if poly[i] is being compared with poly[j], then poly[i] is in the range given by the rays poly[j-1], poly[j] and poly[j+1], poly[j]
  
  for each vertex poly[i]
      if poly[i] is reflex
          find the closest point of intersection given by the ray starting at poly[i-1] and extending in the direction of poly[i] (call this lower bound)
          repeat for the ray given by poly[i+1], poly[i] (call this upper bound)
  
          if there are no vertices along boundary of the polygon in the range given by the upper and lower bounds
              create a new vertex exactly half way between the lower and upper bound points (lower and upper will lie on the same edge)
              connect poly[i] to this new point
          else
              iterate along the vertices in the range given by the lower and upper bounds, for each vertex poly[j]
                  if poly[j] is a 'good reflex'
                      if no other good reflexes have been found
                          save it (overwrite any other vertex found)
                      else
                          if it is closer then the other good reflexes vertices, save it
                  else
                      if no good reflexes have been found and it is closer than the other vertices found, save it
              connect poly[i] to the best candidate
          repeat entire algorithm for both halves of the polygon that was just split
  // no reflex vertices found, then `poly` is convex
  save poly
  </code></pre>
  
  <hr>
  
  <p>Turns out there is one more case I didn't anticipate: [Figure 5]</p>
  
  <p>My algorithm will attempt to connect vertex 1 to 4, unless I add another check to make sure it can. So I propose stuffing everything "in the range" onto a priority queue using the priority scheme I mentioned above, then take the highest priority one, check if it can connect, if not, pop it off and use the next. I <em>think</em> this makes my algorithm O(r n log n) if I optimize it right.</p>
  
  <hr>
  
  <p>I've put together <a href="https://mpen.ca/406/" rel="nofollow noreferrer">a website</a> that loosely describes my findings. I tend to move stuff around, so get it while it's hot.</p>