title: How do I efficiently determine if a polygon is convex, non-convex or complex?
body: <p>From the man page for <a href="https://tronche.com/gui/x/xlib/graphics/filling-areas/XFillPolygon.html" rel="noreferrer"><code>XFillPolygon</code></a>:</p>
  
  <blockquote>
    <ul>
    <li><p>If <code>shape</code> is <strong>Complex</strong>, the path may self-intersect.  Note that contiguous coincident points in the path are not treated as self-intersection.</p></li>
    <li><p>If <code>shape</code> is <strong>Convex</strong>, for every pair of points inside the polygon, the line segment connecting them does not intersect the path. If known by the client, specifying <strong>Convex</strong> can improve performance. If you specify <strong>Convex</strong> for a path that is not convex, the graphics results are undefined.</p></li>
    <li><p>If <code>shape</code> is <strong>Nonconvex</strong>, the path does not self-intersect, but the shape is not wholly convex. If known by the client, specifying <strong>Nonconvex</strong> instead of <strong>Complex</strong> may improve performance.  If you specify <strong>Nonconvex</strong> for a self-intersecting path, the graphics results are undefined.</p></li>
    </ul>
  </blockquote>
  
  <p>I am having performance problems with fill <code>XFillPolygon</code> and, as the man page suggests, the first step I want to take is to specify the correct shape of the polygon. I am currently using <strong>Complex</strong> to be on the safe side.</p>
  
  <p>Is there an efficient algorithm to determine if a polygon (defined by a series of coordinates) is convex, non-convex or complex?</p>