Какой простым способом заполнить вогнутую путю, чтобы быть выпуклым (нахождение вогнутых вершин и удаление их)?

Question

У меня есть путяпина (многоугольник), застроенная из линейныхментов на одном пути, и я хотел бы убедиться, что это выпуклый.У меня есть метод, использующий CrossProduct, чтобы определить, является ли геометрия выпуклости, я предполагал, что я мог бы просто вернуть обратно список точек, которые делают его вогнутым, когда он ложь и удаляет эти точки для заполнения многоугольника, но он не работает совсем так.

Вот код, который у меня есть:

    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 ) и удалить любые вершины на интерьереИз полученного выпуклого полигона корпуса (с использованием Point-In-Polygon Тест).

Answer 2

Вы циклически через каждую триплет соседних вершин (ABC, BCD, CDE и т. Д.).Для каждого триплета вы рассчитываете среднюю точку сегмента, связывающего первую и третью вершину (подключаете A-C в ABC, B-D в BCD и т. Д.).Если средняя точка находится внутри полигона, вы идете на следующий триплет.Если он снаружи, вы замените 2 сегмента, связывающие триплет с одним сегментом, связывающим крайности (то есть вы удаляете среднюю точку).Вы продолжаете до тех пор, пока не возможны дополнительные замены.

Если вы попробуете его на бумаге, вы получаете именно тот результат, который вы описываете.

Если я не ошибаюсь, вы можете проверить, если точка принадлежит многоугольнику с Polygon.HitTestCore.