title: Whats an easy way to fill a Concave PathGeometry to be Convex (finding the concave vertices & removing them)?
body: <p>I've got a PathGeometry (polygon) built up of LineSegments on one PathFigure and I'd like to ensure that it's Convex.  I have a method using the CrossProduct to determine whether the geometry is Convex, I was assuming that I could just return back a list of points that make it concave when it's false and remove those points to fill the polygon but it's not working quite right.  </p>
  
  <p>Here's the code I've got:</p>
  
  <pre><code>    public static bool IsConvexPolygon(this IList&lt;Point&gt; polygon, out List&lt;Point&gt; concavePoints)
      {
          int n = polygon.Count;
          List&lt;double&gt; result = new List&lt;double&gt;();
          concavePoints = new List&lt;Point&gt;();
          for (int i = 0; i &lt; n; i++)
          {
              result.Add(polygon[i].CrossProduct(polygon[i.RotateNext(n)]));
              if (result.Last() &lt; 0.0)
              {
                  concavePoints.Add(polygon[i.RotateNext(n)]);
              }
          }
          return (result.All(d =&gt; d &gt;= 0.0));
      }
  
      public static double CrossProduct(this Point p1, Point p2)
          {
              return (p1.X * p2.Y) - (p1.Y * p2.X);
          }
  
      public static int RotateNext(this int index, int count)
          {
              return (index + 1) % count;
          }
  
      public static PointCollection ExtractPoints(this Geometry geometry)
          {
              PointCollection pc = new PointCollection();
              if (geometry is LineGeometry)
              {
                  var lg = (LineGeometry)geometry;
                  pc.Add(lg.StartPoint);
                  pc.Add(lg.EndPoint);
                  return pc;
              }
              else if (geometry is PathGeometry)
              {
                  var pg = (PathGeometry)geometry;
                  if (pg.Figures.Count &gt; 0)
                  {
                      List&lt;Point&gt; points;
                      if ((pg.Figures[0].Segments.Count &gt; 0) &amp;&amp; (pg.Figures[0].Segments[0] is PolyLineSegment))
                          points = ((PolyLineSegment)pg.Figures[0].Segments[0]).Points.ToList();
                      else
                          points = pg.Figures[0].Segments.Select(seg =&gt; (seg as LineSegment).Point).ToList();
  
                      pc.Add(pg.Figures[0].StartPoint);
                      foreach (Point p in points)
                          pc.Add(p);
                      return pc;
                  }
              }
              else if (geometry is RectangleGeometry)
              {
                  var rg = (RectangleGeometry)geometry;
                  var rect = rg.Rect;
                  pc.Add(rect.TopLeft);
                  pc.Add(rect.TopRight);
                  pc.Add(rect.BottomRight);
                  pc.Add(rect.BottomLeft);
                  return pc;
              }
              return pc;
          }
  
  public static Geometry CreateGeometryFromPoints(this List&lt;Point&gt; pts)
  {
      if (pts.Count &lt; 2)
          return null;
  
      PathFigure pFig = new PathFigure() { StartPoint = pts[0] };
      for (int i = 1; i &lt; pts.Count; i++)
      {
          pFig.Segments.Add(new LineSegment(pts[i], true));
      }
      pFig.IsClosed = true;
  
      PathGeometry pg = new PathGeometry(new List&lt;PathFigure&gt;() { pFig });
      return pg;
  }
  public static Path CreatePolygonFromGeometry(this Geometry geo, Brush fillBrush)
          {
              Path path = new Path() { Stroke = Brushes.Black, StrokeThickness = 1, Fill = fillBrush };
              path.Data = geo;
              return path;
          }
  </code></pre>
  
  <p>And Here's where I making the check and correcting the polygon:</p>
  
  <pre><code>        List&lt;Point&gt; outstuff;
          if (geo1.ExtractPoints().IsConvexPolygon(out outstuff) == false)
          {
              // Got to fill it in if it's concave
              var newpts = geo1.ExtractPoints().Except(outstuff).ToList();
              var z = newpts.CreateGeometryFromPoints().CreatePolygonFromGeometry(Brushes.Purple);
              z.MouseRightButtonDown += delegate { canvas.Children.Remove(z); };
              canvas.Children.Add(z);
          }
  </code></pre>
  
  <p>Ultimately I'd like to be able to make my Concave Geometry into a Convex one like this:</p>
  
  <p><a href="https://i.stack.imgur.com/u5zoE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/u5zoE.png" alt="alt text"></a>
  </p>