Quel est un moyen facile de remplir un PathGeometry concave pour être Convex (trouver les sommets concaves et les supprimer)?

Question

J'ai un PathGeometry (polygone) construit de LineSegments sur un PathFigure et je voudrais m'assurer que c'est Convex. J'ai une méthode utilisant le CrossProduct pour déterminer si la géométrie est convexe, je supposais que je pouvais simplement retourner une liste de points qui la rende concave quand elle est fausse et supprimer ces points pour remplir le polygone mais ça ne fonctionne pas correctement.

Voici le code que j'ai:

public static bool IsConvexPolygon(this IList<Point> polygon, out List<Point> concavePoints) 
    { 
     int n = polygon.Count; 
     List<double> result = new List<double>(); 
     concavePoints = new List<Point>(); 
     for (int i = 0; i < n; i++) 
     { 
      result.Add(polygon[i].CrossProduct(polygon[i.RotateNext(n)])); 
      if (result.Last() < 0.0) 
      { 
       concavePoints.Add(polygon[i.RotateNext(n)]); 
      } 
     } 
     return (result.All(d => d >= 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 > 0) 
       { 
        List<Point> points; 
        if ((pg.Figures[0].Segments.Count > 0) && (pg.Figures[0].Segments[0] is PolyLineSegment)) 
         points = ((PolyLineSegment)pg.Figures[0].Segments[0]).Points.ToList(); 
        else 
         points = pg.Figures[0].Segments.Select(seg => (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<Point> pts) 
{ 
    if (pts.Count < 2) 
     return null; 

    PathFigure pFig = new PathFigure() { StartPoint = pts[0] }; 
    for (int i = 1; i < pts.Count; i++) 
    { 
     pFig.Segments.Add(new LineSegment(pts[i], true)); 
    } 
    pFig.IsClosed = true; 

    PathGeometry pg = new PathGeometry(new List<PathFigure>() { 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; 
     } 

Et voici où je faire la vérification et la correction du polygone:

 List<Point> 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); 
     } 

En fin de compte, je voudrais être en mesure de faire mon Concave géométrie dans un Convex un comme celui-ci:

alt text http://i28.tinypic.com/34zhjzm.png

Answer 1

je calculer la convex hull (aussi: NTS) et supprimer tous les sommets à l'intérieur du polygone de contour convexe résultant (à l'aide d'un test point-in-polygon).

Answer 2

Vous parcourez chaque triplet de sommets adjacents (ABC, BCD, CDE, etc.). Pour chaque triplet, vous calculez le point central du segment reliant le premier et le troisième sommet (vous connectez A-C dans ABC, B-D dans BCD, etc.). Si le point central est à l'intérieur du polygone, vous passez au triplet suivant. Si c'est à l'extérieur, vous substituez les 2 segments reliant le triplet au segment reliant les extrêmes (c'est-à-dire que vous enlevez le point central). Vous continuez jusqu'à ce qu'il n'y ait plus de substitutions possibles.

Si vous l'essayez sur papier, vous obtenez exactement le résultat que vous décrivez. Si je ne me trompe pas, vous pouvez tester si un point appartient à un polygone avec Polygon.HitTestCore.