Ce qui est un moyen facile de remplir un Concave PathGeometry Convexe (trouver le concave sommets et retrait de mer)?

Question

J'ai un PathGeometry (polygone), construit de LineSegments sur un PathFigure et je tiens à vous assurer qu'il est Convexe.J'ai une méthode à l'aide de la CrossProduct pour déterminer si la géométrie est Convexe, j'ai été en supposant que je puisse vient de revenir une liste de points qui font qu'il est concave lorsque c'est faux et supprimer les points de remplissage du polygone, mais il ne fonctionne pas tout à fait droit.

Voici le code que j'ai obtenu:

    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 c'est Là que j'ai prise de la vérification et de 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 de mon Concave de la Géométrie dans un Convexe comme ceci:

Answer 1

Je calculerais le coque convexe (aussi: NTS ) et supprimez tous les sommets à l'intérieurdu polygone convexe résultant de la coque convexe (à l'aide d'un Test de point in-polygone ).

Answer 2

Parcourir chaque triplet de sommets adjacents (ABC, BCD, FAC, etc).Pour chaque triplet permet de calculer le point milieu du segment reliant le premier et le troisième sommet (vous vous connectez A à C de l'ABC, B-D en BCD, etc).Si le point milieu est à l'intérieur du polygone, vous allez à la prochaine triplet.Si à l'extérieur, vous remplacer les 2 segments reliant le triplet avec l'un segment reliant les extrêmes (qui est, vous supprimez le point milieu).Vous allez jusqu'à ne plus les substitutions sont possibles.

Si vous l'essayez, sur le 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.