ما هي طريقة سهلة لملء مسار مقعرالهندسة لتكون محدبة (إيجاد القمم المقعرة وإزالتها)?

Question

لقد حصلت على باثجوميتري (المضلع) التي بنيت من لينيسيغمنتس على باثفيغرام واحد وأود أن تأكد من أنه محدب.لدي طريقة باستخدام كروسبرودوكت لتحديد ما إذا كانت الهندسة محدبة ، كنت أفترض أنه يمكنني فقط العودة إلى قائمة من النقاط التي تجعلها مقعرة عندما تكون خاطئة وإزالة تلك النقاط لملء المضلع ولكنها لا تعمل بشكل صحيح تماما.

وهنا رمز لقد حصلت:

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

وهنا حيث أنا جعل الاختيار وتصحيح المضلع:

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

في النهاية ، أود أن أكون قادرا على تحويل هندستي المقعرة إلى هندسة محدبة مثل هذا:

Answer 1

سأحسب محدب هال (أيضا: nts ) وإزالة أي certexes على الداخليةمن مضلع هال المحدبة الناتج (باستخدام نقطة مضللة اختبار).

Answer 2

يمكنك دورة من خلال كل ثلاثة توائم من القمم المجاورة (أبك ، بسد ، سدي ، الخ).لكل ثلاثة توائم تقوم بحساب النقطة الوسطى للجزء الذي يربط الرأس الأول والثالث (تقوم بتوصيل أ-ج في أبك ، ب-د في بسد ، الخ).إذا كانت النقطة الوسطى داخل المضلع ، فانتقل إلى الثلاثي التالي.إذا كان خارج ، يمكنك استبدال شرائح 2 ربط الثلاثي مع شريحة واحدة تربط النقيضين (وهذا هو ، يمكنك إزالة النقطة الوسطى).تستمر حتى لا تكون هناك بدائل أخرى ممكنة.

إذا جربته على الورق ، فستحصل بالضبط على النتيجة التي تصفها.

إذا لم أكن مخطئا ، يمكنك اختبار ما إذا كانت نقطة تنتمي إلى مضلع مع Polygon.HitTestCore.