Was eine einfache Möglichkeit, eine konkave PathGeometry zu füllen, um konvex zu sein (Finden der konkaven Scheitelpunkte & Entfernen von ihnen)?

Question

Ich habe eine PathGeometry (Polygon), die aus LineSegments auf einer PathFigure besteht, und ich möchte sicherstellen, dass sie konvex ist. Ich habe eine Methode mit dem CrossProduct, um festzustellen, ob die Geometrie Convex ist, ich war davon ausgegangen, dass ich nur zurück eine Liste von Punkten, die es konkav machen, wenn es falsch ist und entfernen Sie diese Punkte, 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 Kontrolle 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 in eine konvexe Geometrie wie diese umwandeln:

Answer 1

Ich berechne die konvexe Hülle (auch: NTS ) und entfernen alle Scheitelpunkte auf der Innenseite des resultierenden konvexen Hüllenpolygons (unter Verwendung einer Punkt-in-Polygon Test).

Answer 2

Sie durchlaufen jedes Tripel benachbarter Scheitelpunkte (ABC, BCD, CDE, usw.). Für jede Dreiergruppe 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, geht man zum nächsten Tripel über. Liegt er außerhalb, ersetzt man die 2 Segmente, die das Triplett verbinden, durch das eine Segment, das die Extremitäten verbindet (d.h. man entfernt den Mittelpunkt). So geht es weiter, bis keine Ersetzungen mehr möglich sind.

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

Wenn ich mich nicht irre, kann man die Zugehörigkeit eines Punktes zu einem Polygon mit Polygon.HitTestCore .