Was ist eine einfache Möglichkeit, eine konkave Pfadgeometrie konvex zu füllen (die konkaven Eckpunkte zu finden und sie zu entfernen)?

Question

Ich habe eine Pfadgeometrie (Polygon), die aus Liniensegmenten auf einer Pfadfigur aufgebaut ist, und ich möchte sicherstellen, dass sie konvex ist.Ich ging davon aus, dass ich einfach eine Liste von Punkten zurückgeben könnte, die sie konkav machen, wenn sie falsch ist, und diese Punkte entfernen könnte, um das Polygon zu füllen, aber es funktioniert nicht ganz richtig.

Hier ist der Code, den ich habe:

    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;
        }

Und hier mache ich die Überprüfung und korrigiere das Polygon:

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

Letztendlich möchte ich meine konkave Geometrie so konvex machen können:

Answer 1

Ich würde den konvexer Hull (auch: Point-In-Polygon Test).

Answer 2

Sie durchlaufen jedes Triplett benachbarter Eckpunkte (ABC, BCD, CDE usw.).Für jedes Triplett berechnen Sie den Mittelpunkt des Segments, das den ersten und den dritten Scheitelpunkt verbindet (Sie verbinden A-C in ABC, B-D in BCD usw.).Wenn der Mittelpunkt innerhalb des Polygons liegt, gehen Sie zum nächsten Triplett.Wenn es draußen ist, ersetzen Sie die 2 Segmente, die das Triplett verbinden, durch das eine Segment, das die Extreme verbindet (dh Sie entfernen den Mittelpunkt).Sie machen so lange weiter, bis keine Auswechslungen mehr möglich sind.

Wenn Sie es auf Papier versuchen, erhalten Sie genau das Ergebnis, das Sie beschreiben.

Wenn ich mich nicht irre, können Sie testen, ob ein Punkt zu einem Polygon gehört mit Polygon.HitTestCore.